Steinitz exchange lemma

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:

1. m ≤ n;

2. possibly after reordering the w_i, the set {v₁, ..., v_m, w_m + 1, ..., w_n} spans V.

Proof

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

k ≤ n and the set { v 1 , … , v k , w k + 1 , … , w n } 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, and the set { w 1 , … , w n } spans V by hypothesis.

For the inductive step, assume the proposition is true for some arbitrary k less than m. Since v k + 1 ∈ V , and { v 1 , … , v k , w k + 1 , … , w n } spans V (by the induction hypothesis), there exist μ 1 , … , μ n such that

v k + 1 = ∑ j = 1 k μ j v j + ∑ j = k + 1 n μ j w j .

At least one of { μ k + 1 , … , μ n } must be non-zero, otherwise this equality would contradict the linear independence of { v 1 , … , v m } ; note that this additionally implies that k + 1 ≤ n . By reordering the μ k + 1 w k + 1 , … , μ n w n , we may assume that μ k + 1 is not zero. Therefore, we have

w k + 1 = 1 μ k + 1 ( v k + 1 − ∑ j = 1 k μ j v j − ∑ j = k + 2 n μ j w j ) .

In other words, w k + 1 is in the span of { v 1 , … , v k + 1 , w k + 2 , … , w n } . The latter span therefore contains each of the vectors v 1 , … , v k , w k + 1 , w k + 2 , … , w n , and hence must contain the span of these latter vectors as a subset. But since the latter span is V (by the induction hypothesis), this simply means that the span of { v 1 , … , v k + 1 , w k + 2 , … , w n } contains V as a subset (thus is 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.