Lema de intercambio de Steinitz

El lema de intercambio de Steinitz es un teorema del álgebra lineal relativo a las bases y la dimensionalidad de un espacio vectorial , que establece que para cualquier conjunto menor que un conjunto generador, existe un conjunto de vectores en el conjunto generador pero ausentes en el conjunto menor que se pueden agregar a este último para que también sea un conjunto generador.

Se puede utilizar, por ejemplo, para demostrar que cualesquiera dos bases para un espacio vectorial de dimensión finita tienen el mismo número de elementos. El resultado recibe su nombre del matemático alemán Ernst Steinitz . A menudo se le denomina lema de intercambio de Steinitz-Mac  Lane , reconociendo también la generalización ^{[ 1 ]} realizada por Saunders Mac Lane del lema de Steinitz a los matroides . ^{[ 2 ]}

Dejar${\displaystyle U}$y${\displaystyle W}$sean subconjuntos finitos de un espacio vectorial${\displaystyle V}$. Si${\displaystyle U}$es un conjunto de vectores linealmente independientes , y${\displaystyle W}$abarca${\displaystyle V}$, entonces:

1.${\displaystyle |U|\leq |W|}$;

2. Hay un conjunto${\displaystyle W'\subsetequ W}$con${\displaystyle |W'|=|W|-|U|}$de tal manera que${\displaystyle U\cup W'}$abarca${\displaystyle V}$.

Suponer${\displaystyle U=\{u_{1},\dots ,u_{m}\}}$y${\displaystyle W=\{w_{1},\dots,w_{n}\}}$. Deseamos demostrar que${\displaystyle m\leq n}$y que después de reorganizar el${\displaystyle w_{j}}$Si es necesario, el conjunto${\displaystyle \{u_{1},\dotsc ,u_{m},w_{m+1},\dotsc ,w_{n}\}}$abarca${\displaystyle V}$. Procedemos por inducción sobre${\displaystyle m}$.

Para el caso base, supongamos que...${\displaystyle m}$es cero. En este caso, la afirmación es válida porque no hay vectores.${\displaystyle u_{i}}$y el conjunto${\displaystyle \{w_{1},\dotsc,w_{n}\}}$abarca${\displaystyle V}$por hipótesis.

Para el paso inductivo, suponga que la proposición es verdadera para${\displaystyle m-1}$. Mediante la hipótesis inductiva podemos reordenar el${\displaystyle w_{i}}$de modo que${\displaystyle \{u_{1},\ldots ,u_{m-1},w_{m},\ldots ,w_{n}\}}$abarca${\displaystyle V}$. Desde${\displaystyle u_{m}\in V}$, existen coeficientes${\displaystyle \mu _{1},\ldots ,\mu _{n}}$de tal manera que

${\displaystyle u_{m}=\sum _ {i=1}^{m-1}\mu _ {i}u_ {i}+\sum _ {j=m}^{n}\mu _ {j}w_ {j}}$.

Al menos uno de los${\displaystyle \mu _{j}}$para${\displaystyle j\geq m}$debe ser distinto de cero, ya que de lo contrario esta igualdad contradiría la independencia lineal de${\displaystyle \{u_{1},\ldots ,u_{m}\}}$; esto también demuestra que, en efecto${\displaystyle m\leq n.}$Al reordenar${\displaystyle \mu _{m}w_{m},\ldots ,\mu _{n}w_{n}}$Si es necesario, podemos asumir que${\displaystyle \mu _{m}}$es distinto de cero. Por lo tanto, tenemos

${\displaystyle w_{m}={\frac {1}{\mu _{m}}}\left(u_{m}-\sum _{j=1}^{m-1}\mu _{j}u_{j}-\sum _{j=m+1}^{n}\mu _{j}w_{j}\right)}$.

En otras palabras,${\displaystyle w_{m}}$está en el lapso de${\displaystyle \{u_{1},\ldots ,u_{m},w_{m+1},\ldots ,w_{n}\}}$Dado que este intervalo contiene cada uno de los vectores${\displaystyle u_{1},\ldots ,u_{m-1},w_{m},w_{m+1},\ldots ,w_{n}}$, por la hipótesis inductiva contiene${\displaystyle V}$.

El lema de intercambio de Steinitz es un resultado básico en matemáticas computacionales , especialmente en álgebra lineal y en algoritmos combinatorios . ^{[ 3 ]}

• Julio R. Bastida, Extensiones de campo y teoría de Galois , Addison–Wesley Publishing Company (1984).

• Prueba del sistema Mizar : http://mizar.org/version/current/html/vectsp_9.html#T19