The Steinitz exchange lemma is a theorem in linear algebra concerning bases, dimensionality of a vector space, stating that for any set smaller than a spanning set, there is a set of vectors in the spanning set but missing from the smaller set that can be added to the smaller set to make that set spanning as well. It can be used, for example, to show that any two bases for a finite-dimensional vector space have the same number of elements. The result is named after the German mathematician Ernst Steinitz. The result is often called the Steinitz–Mac Lane exchange lemma, also recognizing the generalization by Saunders Mac Lane of Steinitz's lemma to matroids.
Statement Let U {\displaystyle U} and W {\displaystyle W} be finite subsets of a vector space V {\displaystyle V} . If U {\displaystyle U} is a set of linearly independent vectors, and W {\displaystyle W} spans V {\displaystyle V} , then: 1. | U | ≤ | W | {\displaystyle |U|\leq |W|} ; 2. There is a set W ′ ⊆ W {\displaystyle W'\subseteq W} with | W ′ | = | W | − | U | {\displaystyle |W'|=|W|-|U|} such that U ∪ W ′ {\displaystyle U\cup W'} spans V {\displaystyle V} .
Proof Suppose U = { u 1 , … , u m } {\displaystyle U=\{u_{1},\dots ,u_{m}\}} and W = { w 1 , … , w n } {\displaystyle W=\{w_{1},\dots ,w_{n}\}} . We wish to show that m ≤ n {\displaystyle m\leq n} , and that after rearranging the w j {\displaystyle w_{j}} if necessary, the set { u 1 , … , u m , w m + 1 , … , w n } {\displaystyle \{u_{1},\dotsc ,u_{m},w_{m+1},\dotsc ,w_{n}\}} spans V {\displaystyle V} . We proceed by induction on m {\displaystyle m} . For the base case, suppose m {\displaystyle m} is zero. In this case, the claim holds because there are no vectors u i {\displaystyle u_{i}} , and the set { w 1 , … , w n } {\displaystyle \{w_{1},\dotsc ,w_{n}\}} spans V {\displaystyle V} by hypothesis. For the inductive step, assume the proposition is true for m − 1 {\displaystyle m-1} . By the inductive hypothesis we may reorder the w i {\displaystyle w_{i}} so that { u 1 , … , u m − 1 , w m , … , w n } {\displaystyle \{u_{1},\ldots ,u_{m-1},w_{m},\ldots ,w_{n}\}} spans V {\displaystyle V} . Since u m ∈ V {\displaystyle u_{m}\in V} , there exist coefficients μ 1 , … , μ n {\displaystyle \mu _{1},\ldots ,\mu _{n}} such that
… excerpt ends here. Continue reading the full article.
