Lema de intercambio de Steinitz

Extensión de vectores independientes a bases

El lema de intercambio de Steinitz es un teorema básico en álgebra lineal que se utiliza, por ejemplo, para demostrar que dos bases cualesquiera para un espacio vectorial de dimensión finita tienen el mismo número de elementos. El resultado recibe el nombre del matemático alemán Ernst Steinitz . El resultado se denomina a menudo lema de intercambio de Steinitz-Mac Lane , reconociendo también la generalización ^[1] de Saunders Mac Lane del lema de Steinitz a las matroides . ^[2]

Declaración

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

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

2. Existe un conjunto con tal que abarca . ${\displaystyle W'\subseteq W}$ ${\displaystyle |W'|=|W|-|U|}$ ${\displaystyle U\cup W'}$ ${\displaystyle V}$

Prueba

Supongamos y . Queremos demostrar que , y que después de reorganizar los si es necesario, el conjunto genera . Procedemos por inducción en . ${\displaystyle U=\{u_{1},\dots ,u_{m}\}}$ ${\displaystyle W=\{w_{1},\dots ,w_{n}\}}$ ${\displaystyle m\leq n}$ ${\displaystyle w_{j}}$ ${\displaystyle \{u_{1},\dotsc ,u_{m},w_{m+1},\dotsc ,w_{n}\}}$ ${\displaystyle V}$ ${\displaystyle m}$

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

Para el paso inductivo, supongamos que la proposición es verdadera para . Por la hipótesis inductiva podemos reordenar de modo que abarque . Como , existen coeficientes tales que ${\displaystyle m-1}$ ${\displaystyle w_{i}}$ ${\displaystyle \{u_{1},\ldots ,u_{m-1},w_{m},\ldots ,w_{n}\}}$ ${\displaystyle V}$ ${\displaystyle u_{m}\in V}$ ${\displaystyle \mu _{1},\ldots ,\mu _{n}}$

${\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 debe ser distinto de cero, ya que de lo contrario esta igualdad contradiría la independencia lineal de ; se sigue que . Si reordenamos si es necesario, podemos suponer que es distinto de cero. Por lo tanto, tenemos ${\displaystyle \mu _{j}}$ ${\displaystyle \{u_{1},\ldots ,u_{m}\}}$ ${\displaystyle m\leq n}$ ${\displaystyle \mu _{m}w_{m},\ldots ,\mu _{n}w_{n}}$ ${\displaystyle \mu _{m}}$

${\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, está en el lapso de . Como este lapso contiene cada uno de los vectores , por la hipótesis inductiva contiene . ${\displaystyle w_{m}}$ ${\displaystyle \{u_{1},\ldots ,u_{m},w_{m+1},\ldots ,w_{n}\}}$ ${\displaystyle u_{1},\ldots ,u_{m-1},w_{m},w_{m+1},\ldots ,w_{n}}$ ${\displaystyle V}$

Aplicaciones

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

Referencias

1. Mac Lane, Saunders (1936), "Algunas interpretaciones de la dependencia lineal abstracta en términos de geometría proyectiva", American Journal of Mathematics , 58 (1), The Johns Hopkins University Press: 236–240, doi :10.2307/2371070, JSTOR  2371070.
2. Kung, Joseph PS, ed. (1986), Un libro de consulta sobre teoría de matroides , Boston: Birkhäuser, doi :10.1007/978-1-4684-9199-9, ISBN 0-8176-3173-9, Sr.  0890330.
3. Página v en Stiefel: Stiefel, Eduard L. (1963). Introducción a las matemáticas numéricas (traducido por Werner C. Rheinboldt y Cornelie J. Rheinboldt de la segunda edición alemana). Nueva York: Academic Press. pp. x+286. MR  0181077.

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

Enlaces externos

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