Steinitz exchange lemma

Statement

Let $F$ be a field and let $V$ be a vector space over $F$. Let $u_1, \dots, u_m \in V$ be linearly independent, and let $w_1, \dots, w_n \in V$ span $V$. Then $m \le n$. Moreover, after a renumbering of the $w_j$, the family $u_1, \dots, u_m, w_{m+1}, \dots, w_n$ spans $V$.

Remarks

The lemma follows by induction on $m$: each $u_i$ replaces one of the $w_j$ in a spanning family. A consequence is that any two finite bases of $V$ have the same number of elements. The lemma is named after Ernst Steinitz.

Explanations

L1 human

An independent family can never have more vectors than a spanning family. We can trade the vectors of the spanning family, one by one, for the independent vectors, and the family still spans. This lemma is the reason why the dimension of a space is well defined.