The Steinitz Exchange Lemma

The Exchange Lemma is the direct ancestor of the proof that all bases of a finite-dimensional vector space have the same number of elements — since a basis is simultaneously independent and spanning, applying the lemma in both directions (basis $B_1$ as the independent list against basis $B_2$ as the spanning list, and vice versa) forces $|B_1| \le |B_2|$ and $|B_2| \le |B_1|$, hence equality. This is exactly what lets us define Dimension as a single well-defined number rather than a basis-dependent artifact. Beyond linear algebra proper, the same combinatorial exchange pattern reappears as the defining axiom of a matroid in combinatorics — matroids abstract exactly this exchange property away from vector spaces, applying it to graphs (spanning trees), transcendence degree in field theory, and combinatorial optimization (greedy algorithms for finding maximum-weight independent sets rely on matroid exchange). In numerical linear algebra and data science, the idea underlies rank computations: the exchange lemma is what guarantees the row rank and column rank of a matrix, or the rank computed via any valid spanning set, is a consistent, well-defined quantity independent of the algorithm used to compute it. In coding theory, the dimension of a linear code (a subspace of $F_q^n$) is computed via generator matrices whose row space is spanned by a fixed number of independent rows, again relying on exchange-lemma consistency. In quantum information and physics, the dimension of a Hilbert space subsystem — central to counting degrees of freedom — is justified by the same invariance-of-basis-size argument. Even in economics and optimization (linear programming basic feasible solutions), the notion of a "basis" of columns providing a feasible solution, and the fact that any two bases have the same size, is this lemma in a change of clothing.

Ask the tutor: How does the Exchange Lemma get used, step by step, to prove that all bases of a finite-dimensional vector space have the same number of vectors?

Picture a spanning set as a "generating toolkit": every vector in $V$ is buildable from these tools. An independent set is a collection of vectors that carry genuinely new, non-redundant information — none is a combination of the others. The exchange lemma says you can always trade tools: take one independent vector $u_1$, express it in terms of the spanning set $w_1,\dots,w_n$, and since $u_1 \ne 0$ (independence forces this) some $w_i$ must appear with a nonzero coefficient. Solve for that $w_i$ in terms of $u_1$ and the rest of the $w$'s, and swap it out. The new list — $u_1$ together with the remaining $w$'s — still spans $V$, because you can recover the discarded $w_i$ whenever you need it. Repeat this swap for $u_2, u_3, \dots$ Each swap consumes one $w$-slot and installs one $u$-vector, while the span never shrinks. If you ever ran out of $w$'s to swap out before you finished installing all the $u$'s, you'd be stuck trying to express some later $u_k$ purely in terms of already-installed $u$'s — but that would make $u_k$ a linear combination of $u_1,\dots,u_{k-1}$, contradicting independence. So the process cannot stall early: there must be at least as many $w$'s as $u$'s.

Example 1 — a genuine size comparison in $\mathbb{R}^4$. Let $V = \mathbb{R}^4$. Consider the spanning list (we will not claim it is a basis — check it merely spans $\mathbb{R}^4$, which it does since it's exactly the standard basis reshuffled with an extra redundant vector):

This list of 5 vectors spans $\mathbb{R}^4$ (it contains the standard basis already). Now consider the independent list

Check independence: suppose $a_1u_1+a_2u_2+a_3u_3=0$. Componentwise:

From the first equation $a_1=0$; then the second gives $a_2=0$; the fourth gives $a_3=0$. So $u_1,u_2,u_3$ are independent, $m=3$. The lemma guarantees $m \le n$, i.e. $3 \le 5$ — consistent, and we can even watch the exchange happen explicitly. Step $k=0 \to 1$: Express $u_1 = (1,2,0,0) = 1\cdot w_1 + 2\cdot w_2 + 0\cdot w_3 + 0\cdot w_4 + 0\cdot w_5$. The coefficient of $w_1$ is nonzero, so exchange $w_1$ out. New spanning list:

Indeed $w_1 = u_1 - 2w_2$, recoverable, so this list still spans $\mathbb{R}^4$. Step $k=1\to 2$: Express $u_2=(0,1,3,0)$ in terms of $u_1,w_2,w_3,w_4,w_5$. Since $u_2$ has zero first coordinate and $u_1$ has first coordinate $1$, any combination $c u_1 + \cdots$ needs $c = 0$ to keep the first coordinate zero (as $w_2,w_3,w_4,w_5$ all have first coordinate $0$). So $u_2 = 0\cdot u_1 + 1\cdot w_2 + 3\cdot w_3 + 0\cdot w_4 + 0\cdot w_5$. Coefficient of $w_2$ is nonzero: exchange $w_2$ out. New list:

Step $k=2\to3$: Express $u_3 = (0,0,1,4)$: first two coordinates are $0$, and $u_1,u_2$ each contribute nonzero first/second coordinates unless their coefficients vanish, forcing coefficients of $u_1,u_2$ to be $0$ (a short direct check: writing $u_3 = c_1u_1+c_2u_2+b_3w_3+b_4w_4+b_5w_5$ and matching the first coordinate gives $c_1 = 0$; matching the second coordinate then gives $c_2 = 0$). So $u_3 = 0\cdot u_1+0\cdot u_2+1\cdot w_3+4\cdot w_4+0\cdot w_5$. Coefficient of $w_3$ nonzero: exchange $w_3$ out. Final list:

which spans $\mathbb{R}^4$ — five vectors, matching $n=5 \ge m=3$ exactly as promised.

Example 2 — using the lemma to rule out an impossible claim. Let $V = P_2(\mathbb{R})$, polynomials of degree $\le 2$, with spanning list

(this is the standard spanning set, so $n = 3$). Someone claims the following four polynomials are linearly independent:

By the Exchange Lemma, if $u_1,u_2,u_3,u_4$ were truly independent we would need $4 \le 3$, which is false. So the lemma predicts the claim must be wrong — the four polynomials must be dependent. Let's verify directly. Try

Expanding in the basis $1, x, x^2$:

• constant term: $c_1 + c_3 + 2c_4 = 0$
• $x$ term: $c_1 + c_2 + c_4 = 0$
• $x^2$ term: $-c_2 - c_3 - c_4 = 0$

This is 3 equations in 4 unknowns, so a nontrivial solution must exist (more unknowns than equations over a field guarantees a nonzero solution to a homogeneous linear system). Solve: from the third equation, $c_2 = -c_3-c_4$. Substitute into the second: $c_1 - c_3 - c_4 + c_4 = 0 \Rightarrow c_1 = c_3$. Substitute $c_1=c_3$ into the first: $c_3 + c_3 + 2c_4 = 0 \Rightarrow c_4 = -c_3$. Then $c_2 = -c_3 - (-c_3) = 0$. Take $c_3 = 1$: then $c_1 = 1, c_4 = -1, c_2 = 0$. Check:

Indeed a genuine nontrivial dependence: $u_1 + u_3 - u_4 = 0$. This confirms exactly what the lemma forced: with only 3 spanning vectors, no 4 vectors in $P_2(\mathbb{R})$ can be independent.