Steinitz exchange lemma

(Redirected from Exchange theorem)

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]

Statement

edit

Let   and   be finite subsets of a vector space  . If   is a set of linearly independent vectors, and   spans  , then:

1.  ;

2. There is a set   with   such that   spans  .

Proof

edit

Suppose   and  . We wish to show that  , and that after rearranging the   if necessary, the set   spans  . We proceed by induction on  .

For the base case, suppose   is zero. In this case, the claim holds because there are no vectors  , and the set   spans   by hypothesis.

For the inductive step, assume the proposition is true for  . By the inductive hypothesis we may reorder the   so that   spans  . Since  , there exist coefficients   such that

 .

At least one of the   must be non-zero, since otherwise this equality would contradict the linear independence of  ; it follows that  . By reordering   if necessary, we may assume that   is nonzero. Therefore, we have

 .

In other words,   is in the span of  . Since this span contains each of the vectors  , by the inductive hypothesis it contains  .

Applications

edit

The Steinitz exchange lemma is a basic result in computational mathematics, especially in linear algebra and in combinatorial algorithms.[3]

References

edit
  1. ^ Mac Lane, Saunders (1936), "Some interpretations of abstract linear dependence in terms of projective geometry", American Journal of Mathematics, 58 (1), The Johns Hopkins University Press: 236–240, doi:10.2307/2371070, JSTOR 2371070.
  2. ^ Kung, Joseph P. S., 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.
  3. ^ Page v in Stiefel: Stiefel, Eduard L. (1963). An introduction to numerical mathematics (Translated by Werner C. Rheinboldt & Cornelie J. Rheinboldt from the second German ed.). New York: Academic Press. pp. x+286. MR 0181077.
edit