The Replacement Idea
The exchange lemma compares two finite lists in a vector space: one list spans the space, while another is linearly independent. Its proof depends on a small but powerful observation. If a vector can be written as a linear combination of a spanning list, and one coefficient in that expression is nonzero, then that vector can take the place of the corresponding list vector without changing the span. Independence ensures that, at each stage, there is a nonzero coefficient available for a vector that has not yet been replaced.
Let \(V\) be a vector space over \(\mathbb{F}\), where \(\mathbb{F}\) is \(\mathbb{R}\) or \(\mathbb{C}\). For a finite list \((\mathbf{v}_1,\dots,\mathbf{v}_n)\), its span is the set of all linear combinations of its entries. The list spans \(V\) if every vector in \(V\) is such a combination. A list is linearly independent if the only linear combination equal to \(\mathbf{0}\) has all coefficients zero. We use the convention that the span of an empty list is \(\{\mathbf{0}\}\).
The nonzero condition matters because it lets us solve the displayed expression for \(\mathbf{w}_j\). The new list contains \(\mathbf{u}\) and all the other \(\mathbf{w}_i\), so that solved expression shows that the omitted vector \(\mathbf{w}_j\) can still be made from the new list.
Proof. Every entry of the new list belongs to the span of the old list: the unchanged entries already belonged to it, and \(\mathbf{u}\) is a linear combination of the old entries. Thus the new list's span is contained in the old list's span. In the other direction, solve for the replaced vector: \[ \mathbf{w}_j=\frac{1}{c_j}\left(\mathbf{u}-\sum_{i\ne j}c_i\mathbf{w}_i\right). \] This is possible because \(c_j\ne0\), and the right side is a linear combination of entries of the new list. Every old entry therefore belongs to the span of the new list. The two spans are equal, so the new list spans \(V\). \(\square\)
The Exchange Lemma
The replacement is done in order. First, express \(\mathbf{u}_1\) using the original spanning list and replace an entry whose coefficient is nonzero. Next, express \(\mathbf{u}_2\) using the current spanning list and replace one of the original entries still remaining. Continue in this way. The key point to prove is that a suitable remaining entry exists at every step.
Proof. If \(n=0\), the empty list spans \(V\), so \(V=\{\mathbf{0}\}\). No nonempty list in this space is independent: any list containing its zero vector has a nontrivial relation. Hence \(m=0\), and the conclusion holds. If \(m=0\), there is nothing to replace and \(m\le n\). It remains to consider \(n\ge1\) and \(m\ge1\).
Suppose that \(k-1\) replacements have been made, where \(1\le k\le m\), and that the current spanning list consists of \(\mathbf{u}_1,\dots,\mathbf{u}_{k-1}\) together with the \(n-k+1\) original entries not yet replaced. Denote those remaining entries, in their current order, by \(\mathbf{w}_1,\dots,\mathbf{w}_{n-k+1}\). This list spans \(V\), so it expresses \(\mathbf{u}_k\) as \[ \mathbf{u}_k=a_1\mathbf{u}_1+\cdots+a_{k-1}\mathbf{u}_{k-1} +b_1\mathbf{w}_1+\cdots+b_{n-k+1}\mathbf{w}_{n-k+1}. \] At least one of the coefficients \(b_1,\dots,b_{n-k+1}\) must be nonzero. Otherwise, \[ a_1\mathbf{u}_1+\cdots+a_{k-1}\mathbf{u}_{k-1}-\mathbf{u}_k=\mathbf{0} \] would be a nontrivial dependence relation among \(\mathbf{u}_1,\dots,\mathbf{u}_k\): the coefficient of \(\mathbf{u}_k\) is \(-1\ne0\). This contradicts independence of the full list, since any relation among its first \(k\) entries extends to the full list by giving the later entries coefficient zero.
Choose \(j\) with \(b_j\ne0\). By the replacement principle, replacing \(\mathbf{w}_j\) with \(\mathbf{u}_k\) preserves the span. This proves inductively that each replacement can be made as long as at least one original entry remains. If \(m\le n\), carrying out all \(m\) steps gives a spanning list containing \(\mathbf{u}_1,\dots,\mathbf{u}_m\) and \(n-m\) unreplaced entries.
It remains to show that \(m\le n\). If \(m>n\), carry out the first \(n\) replacements by the argument above. The resulting list consists of \(\mathbf{u}_1,\dots,\mathbf{u}_n\) and has no remaining original entries, yet it spans \(V\). Therefore \(\mathbf{u}_{n+1}\) is a linear combination of \(\mathbf{u}_1,\dots,\mathbf{u}_n\). Moving that combination to one side gives a dependence relation among \(\mathbf{u}_1,\dots,\mathbf{u}_{n+1}\) with coefficient \(-1\) on \(\mathbf{u}_{n+1}\). This contradicts independence. Thus \(m\le n\), completing the proof. \(\square\)
The proof uses only the definitions of spanning and independence, and the fact that a nonzero scalar in a field has a multiplicative inverse. It does not require a dimension for \(V\) to have been defined. The conclusion also distinguishes two parts of the lemma: the replacements preserve spanning, while independence rules out asking for more independent vectors than there are entries to replace.
Worked Replacement Steps
Worked Example: Replacing Entries in R²
Start with the spanning list \((\mathbf{e}_1,\mathbf{e}_2)\) in \(\mathbb{R}^2\), where \(\mathbf{e}_1=(1,0)\) and \(\mathbf{e}_2=(0,1)\). Use the independent list \(\mathbf{u}_1=(1,1)\), \(\mathbf{u}_2=(1,-1)\) to make two replacements.
First, the vectors are independent. If \(a\mathbf{u}_1+b\mathbf{u}_2=\mathbf{0}\), then the coordinates give \(a+b=0\) and \(a-b=0\). Adding these equations gives \(2a=0\), so \(a=0\); then \(b=0\). Also, every \((x,y)\in\mathbb{R}^2\) equals \(x\mathbf{e}_1+y\mathbf{e}_2\), so the starting list spans.
For the first replacement, write \(\mathbf{u}_1=\mathbf{e}_1+\mathbf{e}_2\). The coefficient of \(\mathbf{e}_1\) is \(1\ne0\), so replace \(\mathbf{e}_1\). The new list is \((\mathbf{u}_1,\mathbf{e}_2)\), and the old vector is recovered as \(\mathbf{e}_1=\mathbf{u}_1-\mathbf{e}_2\).
For the second replacement, express \(\mathbf{u}_2\) using the current list: \[ \mathbf{u}_2=\mathbf{u}_1-2\mathbf{e}_2, \qquad (1,-1)=(1,1)-2(0,1). \] The coefficient of \(\mathbf{e}_2\) is \(-2\ne0\), so replace \(\mathbf{e}_2\). The final list is \((\mathbf{u}_1,\mathbf{u}_2)\). To check that it still spans, recover both original vectors: \[ \mathbf{e}_2=\frac{\mathbf{u}_1-\mathbf{u}_2}{2} =\frac{(1,1)-(1,-1)}{2}=(0,1), \] \[ \mathbf{e}_1=\frac{\mathbf{u}_1+\mathbf{u}_2}{2} =\frac{(1,1)+(1,-1)}{2}=(1,0). \] Thus the final list spans the original spanning list, and hence \(\mathbb{R}^2\).
Worked Example: Replacing Entries in a Polynomial Space
In the real vector space \(P_2\) of polynomials of degree at most \(2\), start with \((1,x,x^2)\). This list spans because every element \(a+bx+cx^2\) equals \(a\cdot1+b\cdot x+c\cdot x^2\). Replace entries using \(\mathbf{u}_1=1+x\) and \(\mathbf{u}_2=x+x^2\).
These two polynomials are independent. If \(\alpha(1+x)+\beta(x+x^2)=0\), comparison of the constant coefficients gives \(\alpha=0\), and comparison of the \(x^2\) coefficients gives \(\beta=0\).
Since \(\mathbf{u}_1=1+x\), its coefficient on \(1\) is nonzero. Replace \(1\) with \(\mathbf{u}_1\), obtaining \((\mathbf{u}_1,x,x^2)\). Next, \(\mathbf{u}_2=x+x^2\) has coefficient \(1\) on the remaining entry \(x^2\), so replace \(x^2\). The new list is \((\mathbf{u}_1,x,\mathbf{u}_2)\).
Check the span by recovering each polynomial in the starting list: \[ 1=\mathbf{u}_1-x=(1+x)-x, \qquad x=x, \qquad x^2=\mathbf{u}_2-x=(x+x^2)-x. \] Each equality holds by subtracting coefficients, and all three original spanning entries are combinations of the final list. Therefore the final list spans \(P_2\).
Worked Example: A Redundant Starting List
In \(\mathbb{R}^3\), take the spanning list \((\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4)\), where \(\mathbf{v}_1=(1,0,0)\), \(\mathbf{v}_2=(0,1,0)\), \(\mathbf{v}_3=(0,0,1)\), and \(\mathbf{v}_4=(1,1,0)\). It spans because the first three entries are the standard basis. Let \(\mathbf{u}_1=(1,1,1)\) and \(\mathbf{u}_2=(1,0,1)\).
The independent-list condition holds: if \(a\mathbf{u}_1+b\mathbf{u}_2=\mathbf{0}\), the second coordinate gives \(a=0\), and the third coordinate then gives \(b=0\). For the first replacement, \[ \mathbf{u}_1=\mathbf{v}_1+\mathbf{v}_2+\mathbf{v}_3. \] The coefficient on \(\mathbf{v}_3\) is \(1\), so replace \(\mathbf{v}_3\). The current list \((\mathbf{u}_1,\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_4)\) spans.
Now write \(\mathbf{u}_2=\mathbf{u}_1-\mathbf{v}_2\), since \((1,1,1)-(0,1,0)=(1,0,1)\). The coefficient on \(\mathbf{v}_2\) is \(-1\ne0\), so replace \(\mathbf{v}_2\). The final list is \((\mathbf{u}_1,\mathbf{u}_2,\mathbf{v}_1,\mathbf{v}_4)\). To verify that the original spanning entries remain in its span, compute \[ \mathbf{v}_1=(1,0,0),\qquad \mathbf{v}_2=\mathbf{u}_1-\mathbf{u}_2=(0,1,0), \] \[ \mathbf{v}_3=\mathbf{u}_2-\mathbf{v}_1=(0,0,1),\qquad \mathbf{v}_4=(1,1,0). \] All four original entries are recovered, so the final list spans \(\mathbb{R}^3\).
Why the Nonzero Coefficient Is Essential
A coefficient equal to zero gives no way to solve for the corresponding vector. For example, \((\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3)\) spans \(\mathbb{R}^3\), and \(\mathbf{u}=\mathbf{e}_1+\mathbf{e}_2\) has the expression \[ \mathbf{u}=1\mathbf{e}_1+1\mathbf{e}_2+0\mathbf{e}_3. \] It would be wrong to replace \(\mathbf{e}_3\) using its coefficient \(0\) and conclude that \((\mathbf{e}_1,\mathbf{e}_2,\mathbf{u})\) still spans. Every vector in that new list has third coordinate \(0\), so no combination of them can equal \(\mathbf{e}_3=(0,0,1)\). The correction is to replace an entry with a nonzero coefficient, such as \(\mathbf{e}_1\): then \(\mathbf{e}_1=\mathbf{u}-\mathbf{e}_2\), and the span is preserved.
This is the logical role of independence in the exchange proof. At a given step, the new independent vector cannot be a combination of only the previously inserted independent vectors. If it were, moving terms to one side would produce a nontrivial dependence relation. Therefore its expression in the current spanning list must use at least one still-unreplaced entry with a nonzero coefficient. The replacement principle then applies to that entry—not to an arbitrary one.
When carrying out the argument, keep the current list explicit. The entries already replaced are the independent vectors inserted so far; the eligible entries are precisely those original spanning-list entries not yet replaced. This bookkeeping prevents two common errors: replacing the same original entry twice, or using a coefficient from an earlier expression after the spanning list has changed.
Check Your Understanding
For each question, identify the relevant coefficient or independence condition and verify any proposed replacement by expressing the omitted vector in the new list.
- If \(\mathbf{u}=2\mathbf{w}_1-\mathbf{w}_2+0\mathbf{w}_3\), which entries can be replaced by \(\mathbf{u}\) using the replacement principle? Explain why the third entry is not justified.
- Suppose a list \((\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3)\) spans \(V\), and \(\mathbf{u}_1=\mathbf{v}_1+\mathbf{v}_3\). Give a replacement that preserves the span and recover the replaced vector.
- In the exchange proof, why would an expression for \(\mathbf{u}_k\) using only \(\mathbf{u}_1,\dots,\mathbf{u}_{k-1}\) contradict independence?
- For the polynomial example, express each of \(1,x,x^2\) using the final list \((1+x,x,x+x^2)\).
- Why does the exchange argument rule out \(m>n\) independent vectors when the spanning list has \(n\) entries?
