El lema de intercambio de Steinitz es un teorema básico en álgebra lineal que se utiliza, por ejemplo, para mostrar que dos bases cualesquiera de un espacio vectorial de dimensión finita tienen el mismo número de elementos. El resultado lleva el nombre del matemático alemán Ernst Steinitz . El resultado se denomina a menudo lema de intercambio Steinitz-Mac Lane , reconociendo también la generalización [1] de Saunders Mac Lane del lema de Steinitz a matroides . [2]
Declaración
Si es un conjunto de vectores linealmente independientes en un espacio vectorial, y lapso , luego:
1. ;
2. Hay un conjunto con tal que tramos .
Prueba
Supongamos que tenemos los conjuntos de vectores indicados. Deseamos mostrar que para cada, tenemos eso , y que el set tramos (donde el posiblemente se hayan reordenado, y el reordenamiento depende de ). Procedemos por inducción en.
Para el caso base, suponga es cero. En este caso, la afirmación es válida porque no hay vectores, y el set tramos por hipótesis.
Para el paso inductivo, suponga que la proposición es verdadera para algunos . Desde, y tramos (por la hipótesis de inducción), existen coeficientes tal que
- .
Al menos uno de debe ser distinto de cero, ya que de lo contrario esta igualdad contradeciría la independencia lineal de ; tenga en cuenta que esto implica además que. Al reordenar el, podemos asumir que no es cero. Por lo tanto, tenemos
- .
En otras palabras, está en el lapso de . Por tanto, el último tramo contiene cada uno de los vectores, y por lo tanto debe contener el intervalo de estos últimos vectores como un subconjunto. Pero dado que el último lapso es (por la hipótesis de inducción), esto simplemente significa que el lapso de contiene como un subconjunto (así es ). Por lo tanto, hemos demostrado que nuestra afirmación es cierta de, completando el paso inductivo.
Así hemos demostrado que para cada , tenemos eso , y que el set tramos (donde el posiblemente se hayan reordenado, y el reordenamiento depende de ).
El hecho de que sigue de la configuración en este resultado.
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
- ^ Mac Lane, Saunders (1936), "Algunas interpretaciones de la dependencia lineal abstracta en términos de geometría proyectiva", American Journal of Mathematics , The Johns Hopkins University Press, 58 (1): 236-240, doi : 10.2307 / 2371070 , JSTOR 2371070 .
- ^ Kung, Joseph PS, ed. (1986), A Source Book in Matroid Theory , Boston: Birkhäuser, doi : 10.1007 / 978-1-4684-9199-9 , ISBN 0-8176-3173-9, MR 0890330.
- ^ Página v en Stiefel: Stiefel, Eduard L. (1963). Una 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. págs. x + 286. Señor 0181077 .
- Julio R. Bastida, Extensiones de campo y teoría de Galois , Addison-Wesley Publishing Company (1984).