Steinitz exchange lemma

Steinitz exchange lemma   (Redirected from Exchange theorem) Jump to navigation Jump to search The Steinitz exchange lemma is a basic theorem in linear algebra 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[1] by Saunders Mac Lane of Steinitz's lemma to matroids.[2] Contents 1 Statement 2 Proof 3 Applications 4 References 5 External links Statement Let {displaystyle U} and {displaystyle W} be finite subsets of a vector space {displaystyle V} . If {displaystyle U} is a set of linearly independent vectors, and {displaystyle W} spans {displaystyle V} , then: 1. {displaystyle |U|leq |W|} ; 2. There is a set {displaystyle W'subseteq W} with {displaystyle |W'|=|W|-|U|} such that {displaystyle Ucup W'} spans {displaystyle V} .

Proof Suppose {displaystyle U={u_{1},dots ,u_{m}}} and {displaystyle W={w_{1},dots ,w_{n}}} . We wish to show that for each {displaystyle kin {0,dots ,m}} , we have that {displaystyle kleq n} , and that the set {displaystyle {u_{1},dotsc ,u_{k},w_{k+1},dotsc ,w_{n}}} spans {displaystyle V} (where the {displaystyle w_{j}} have possibly been reordered, and the reordering depends on {displaystyle k} ). We proceed by induction on {displaystyle k} .

For the base case, suppose {displaystyle k} is zero. In this case, the claim holds because there are no vectors {displaystyle u_{i}} , and the set {displaystyle {w_{1},dotsc ,w_{n}}} spans {displaystyle V} by hypothesis.

For the inductive step, assume the proposition is true for some {displaystyle k

Si quieres conocer otros artículos parecidos a Steinitz exchange lemma puedes visitar la categoría Lemmas in linear algebra.