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

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.

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

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 ${\displaystyle \{w_{1},\dotsc ,w_{n}\}}$ spans V by hypothesis.

...
Wikipedia