Steinitz exchange lemma

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

If {v₁, ..., v_m} is a set of m linearly independent vectors in a vector space V, and {w₁, ..., w_n} span V then m ≤ n and, possibly after reordering the w_i, the set {v₁, ..., v_m, w_m + 1, ..., w_n} spans V.

Proof

Let P(k) denote the following proposition, for each k in {0, …, m}.

The set $\{v_1, \dotsc, v_k, w_{k + 1}, \dotsc, w_m\}$ spans V (where the w_j have possibly been reordered, and the reordering depends on k).

We prove by mathematical induction that for any nonnegative integer m, the proposition P(m) is true, thereby proving the lemma.

For the base case, suppose k is zero. In this case, P(k) is true because there are no vectors v_i, so the set $\{w_1, \dotsc, w_m\}$ spans V by hypothesis.

For the inductive step, assume the proposition is true for some arbitrary k less than m. Since $v_{k+1}\in V$, and $\{ v_1,\ldots, v_k,w_{k+1},\ldots,w_n\}$ spans V (by the induction hypothesis), there exist $\mu_1,\ldots,\mu_n$ such that

$v_{k+1}=\sum_{j=1}^k \mu_j v_j+\sum_{j=k+1}^n \mu_j w_j.$

At least one of $\{\mu_{k+1},\ldots,\mu_n\}$ must be non-zero, otherwise this equality would contradict the linear independence of $\{ v_1,\ldots,v_m \}$; note that this additionally implies that $k<n$. By reordering the $w_{k+1},\ldots,w_n$, we may assume that $\mu_{k+1}$ is not zero. Therefore, we have

$w_{k+1}= \frac{1}{\mu_{k+1}}\left(v_{k+1} - \sum_{j=1}^k \mu_j v_j - \sum_{j=k+2}^n \mu_j w_j\right)$

In other words, $w_{k+1}$ is in the span of $\{ v_1,\ldots, v_{k+1},w_{k+2},\ldots,w_n\}$ and so the latter must be the whole of V. We have thus shown that P(k + 1) is true, completing the inductive step.

Applications

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

References

1. Mac Lane, Saunders (1936), "Some interpretations of abstract linear dependence in terms of projective geometry", American Journal of Mathematics (The Johns Hopkins University Press) 58 (1): 236–240, doi:10.2307/2371070, JSTOR 2371070.
2. Kung, Joseph P. S., ed. (1986), A Source Book in Matroid Theory, Boston: Birkhäuser, 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 181077.

• Julio R. Bastida, Field extensions and Galois Theory, Addison–Wesley Publishing Company (1984).

External links

• Mizar system proof: http://mizar.org/version/current/html/vectsp_9.html#T19