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 by Saunders Mac Lane of Steinitz's lemma to matroids.

Statement

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

1. ;
2. There is a set with such that U \cup W' spans V.

Proof

Suppose and. We wish to show that m \le n, and that after rearranging the w_j if necessary, the set spans V. We proceed by induction on m. For the base case, suppose m is zero. In this case, the claim holds because there are no vectors u_i, and the set spans V by hypothesis. For the inductive step, assume the proposition is true for m-1. By the inductive hypothesis we may reorder the w_i so that spans V. Since u_{m}\in V, there exist coefficients such that At least one of the \mu_j must be non-zero, since otherwise this equality would contradict the linear independence of ; it follows that m \le n. By reordering if necessary, we may assume that \mu_{m} is nonzero. Therefore, we have In other words, w_{m} is in the span of. Since this span contains each of the vectors, by the inductive hypothesis it contains V.

Applications

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