The Exchange Question
A spanning list contains enough vectors to produce every vector in a space, but it may contain redundancy. An independent list has no redundant vector, but it need not span the whole space. The exchange lemma connects these two kinds of lists: under its hypotheses, vectors from the independent list can be inserted one at a time by removing distinct vectors from the spanning list, without changing the span.
Let \(V\) be a vector space over a field \(\mathbb{F}\), where \(\mathbb{F}\) is \(\mathbb{R}\) or \(\mathbb{C}\). For a finite list \((\mathbf{v}_1,\ldots,\mathbf{v}_q)\) in \(V\), its span is the set of all linear combinations \(c_1\mathbf{v}_1+\cdots+c_q\mathbf{v}_q\), with \(c_i\in\mathbb{F}\). The list spans \(V\) if this set equals \(V\). A list is linearly independent if the equation \(c_1\mathbf{v}_1+\cdots+c_q\mathbf{v}_q=\mathbf{0}\) forces every coefficient to be zero.
The condition \(m\le n\) is part of this statement, not a conclusion being proved here. The lists are ordered: the order of the \(\mathbf{y}_k\) specifies the insertion order, while the distinct indices ensure that a spanning vector is not removed twice. When \(m=0\), there is nothing to replace and the original spanning list remains. When \(m>0\), independence ensures that no \(\mathbf{y}_k\) is the zero vector.
The key point is preservation of the span, not preservation of the original list or of its length alone. At stage \(k\), the list has \(n\) entries: \(k\) inserted vectors and \(n-k\) retained vectors. The lemma does not assert that every choice of spanning vector can be removed. It asserts that an appropriate choice can be made at each step.
Why a Nonzero Coefficient Allows Replacement
A basic calculation explains the local mechanism behind exchange. Suppose \(S=(\mathbf{x}_1,\ldots,\mathbf{x}_n)\) spans \(V\), and suppose a proposed new vector has an expression in this list. If the coefficient of the vector being removed is nonzero, we can rearrange that expression to recover the removed vector from the new list.
Proof. Solving the displayed expression for \(\mathbf{x}_j\) gives
Thus \(\mathbf{x}_j\) belongs to the span of the replacement list, since that list contains \(\mathbf{y}\) and every \(\mathbf{x}_i\) with \(i\ne j\). All the other vectors of \(S\) also belong to the replacement list. Therefore the replacement list spans every vector in \(S\), and so it spans \(V\), because \(S\) spans \(V\). Each vector in the replacement list is in \(V\), so its span is exactly \(V\). \(\square\)
This proposition gives a sufficient test for a particular replacement. The exchange lemma gives a broader existence guarantee: with an independent list to insert, a suitable choice of spanning vector can be found at each stage. The next examples make the coefficient calculation and the sequence of exchanges explicit.
Worked Example: Replacing a Vector in R²
Start with the standard basis \((\mathbf{e}_1,\mathbf{e}_2)\) of \(\mathbb{R}^2\), where \(\mathbf{e}_1=(1,0)\) and \(\mathbf{e}_2=(0,1)\). Replace \(\mathbf{e}_1\) by \(\mathbf{y}=(2,3)\), and verify that the new list spans \(\mathbb{R}^2\).
The expression \(\mathbf{y}=2\mathbf{e}_1+3\mathbf{e}_2\) has coefficient \(2\ne0\) on the vector being replaced. Rearranging gives
For an arbitrary vector \((a,b)\in\mathbb{R}^2\), use \((a,b)=a\mathbf{e}_1+b\mathbf{e}_2\) and substitute the expression for \(\mathbf{e}_1\):
So every vector in \(\mathbb{R}^2\) is a linear combination of \(\mathbf{y}\) and \(\mathbf{e}_2\). As a check, the formula gives \(\mathbf{e}_1=\tfrac12((2,3)-3(0,1))=(1,0)\), and \(\mathbf{e}_2=(0,1)\) is already in the new list. Hence the new list spans all of \(\mathbb{R}^2\).
Worked Example: Replacing a Vector in a Redundant Spanning List
Consider the spanning list \((\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3,\mathbf{x}_4)=((1,0,0),(0,1,0),(0,0,1),(1,1,0))\) in \(\mathbb{R}^3\). Replace \(\mathbf{x}_3\) by \(\mathbf{y}=(1,0,1)\).
The original list spans \(\mathbb{R}^3\), since it includes the three standard basis vectors. Also, \(\mathbf{y}=\mathbf{x}_1+\mathbf{x}_3\), so the coefficient on \(\mathbf{x}_3\) is \(1\ne0\). Solving for the removed vector gives \(\mathbf{x}_3=\mathbf{y}-\mathbf{x}_1\).
The new list is \((\mathbf{x}_1,\mathbf{x}_2,\mathbf{y},\mathbf{x}_4)\). It contains \(\mathbf{x}_1\) and \(\mathbf{x}_2\), and it recovers the missing standard vector by \(\mathbf{x}_3=(1,0,1)-(1,0,0)=(0,0,1)\). Therefore it contains, in its span, all three standard basis vectors.
Check: Any \((a,b,c)\in\mathbb{R}^3\) can be written as \(a\mathbf{x}_1+b\mathbf{x}_2+c(\mathbf{y}-\mathbf{x}_1)=(a-c)\mathbf{x}_1+b\mathbf{x}_2+c\mathbf{y}\). Thus the new list spans \(\mathbb{R}^3\), as claimed. The extra vector \(\mathbf{x}_4\) is not needed for this verification.
Replacement in a Basis
A basis is an ordered list that both spans the space and is linearly independent. In a basis, every vector has a unique coordinate representation. That uniqueness makes the replacement test exact: for a fixed basis vector, the relevant coefficient is unambiguous.
Proof. First suppose \(a_j\ne0\). The preceding proposition shows that the replacement list spans \(V\). To prove it is independent, suppose \(c\mathbf{y}+\sum_{i\ne j}c_i\mathbf{b}_i=\mathbf{0}\). Substituting the coordinates of \(\mathbf{y}\) produces a linear combination of the original basis equal to \(\mathbf{0}\). Its coefficient on \(\mathbf{b}_j\) is \(ca_j\), so independence of the original basis gives \(ca_j=0\), hence \(c=0\). The remaining coefficients \(c_i\) must then all be zero by that same independence. The replacement list is both spanning and independent, so it is a basis.
Now suppose \(a_j=0\). Then \(\mathbf{y}\) and every \(\mathbf{b}_i\) for \(i\ne j\) lie in the span of the original basis vectors other than \(\mathbf{b}_j\). The replacement list therefore lies in that span. But \(\mathbf{b}_j\) does not lie in the span of the other original basis vectors: otherwise, moving such an expression to one side would give a nontrivial dependence relation among the original basis vectors. Thus the replacement list does not span \(V\), so it cannot be a basis. This proves both directions. \(\square\)
Worked Example: Two Successive Replacements in P₂
Let \(P_2\) be the real vector space of polynomials of degree at most \(2\). Begin with the basis \((1,x,x^2)\), and consider the list \((y_1,y_2)=(1+x,x+x^2)\).
First verify that the inserted list is independent. If \(c(1+x)+d(x+x^2)=0\), comparing coefficients of \(1,x,x^2\) gives \(c=0\), \(c+d=0\), and \(d=0\). In particular, the only possible coefficients are \(c=d=0\).
For the first replacement, \(y_1=1+x\) has coefficient \(1\) on the basis vector \(1\). Replace \(1\) by \(y_1\), leaving \((1+x,x,x^2)\). The removed vector is recovered by \(1=(1+x)-x\), so the new list spans \(P_2\).
For the second replacement, express \(y_2\) in the current list: \(x+x^2=0(1+x)+1x+1x^2\). Its coefficient on \(x^2\) is \(1\), so replace \(x^2\) by \(y_2\). The resulting list is \((1+x,x,x+x^2)\). It recovers \(x^2\) from \(x^2=(x+x^2)-x\), and then recovers \(1\) from \(1=(1+x)-x\).
Check: The final list spans \(1,x,x^2\), since it produces each of them by the displayed formulas; hence it spans every polynomial \(a+bx+cx^2\). The two inserted polynomials are independent by the coefficient calculation above. The example exhibits two distinct replacements while keeping the span equal to \(P_2\) after each step.
Common Pitfall: The Replacement Vector Matters
A nonzero coefficient is tied to the particular vector being removed. It is not enough that the new vector has some nonzero coefficient in an expression using the spanning list.
For example, the basis \((\mathbf{e}_1,\mathbf{e}_2)\) spans \(\mathbb{R}^2\). Take \(\mathbf{y}=\mathbf{e}_1=(1,0)\), and incorrectly replace \(\mathbf{e}_2\) because \(\mathbf{y}\) has a nonzero coefficient on \(\mathbf{e}_1\). The resulting list is \((\mathbf{e}_1,\mathbf{e}_1)\), whose every linear combination has the form \((c+d,0)\). It cannot produce \((0,1)\), so it does not span \(\mathbb{R}^2\).
The correction is to inspect the coefficient of the vector actually being removed. In \(\mathbf{y}=1\mathbf{e}_1+0\mathbf{e}_2\), the coefficient on \(\mathbf{e}_2\) is zero, so the proposition does not justify removing \(\mathbf{e}_2\). If instead we replace \(\mathbf{e}_1\), its coefficient is \(1\), and the resulting list \((\mathbf{y},\mathbf{e}_2)=(\mathbf{e}_1,\mathbf{e}_2)\) still spans. This check is essential whenever a proposed exchange is tested by coordinates.
What the Lemma Provides
The exchange lemma is an existence statement applied successively. It does not require the initial spanning list to be independent, and it does not promise that the vectors selected for removal are unique. In a redundant spanning list, several choices may preserve the span; in a basis, the coefficient criterion tells exactly which single-vector replacements work for a specified new vector.
Its practical value is that it allows a spanning list and an independent list to be compared while keeping track of the whole space they generate. At each successful step, one vector from the independent list takes the place of one vector from the spanning list, and the span is unchanged. The coefficient calculation explains an individual exchange; the lemma guarantees that a suitable sequence of exchanges exists under its hypotheses.
Check Your Understanding
For each question, state what is being replaced and verify any proposed exchange by recovering the removed vector or by checking the resulting span.
- State the hypotheses and conclusion of the exchange lemma, including what must be true of the removed indices.
- In \(\mathbb{R}^2\), replace \(\mathbf{e}_2\) in \((\mathbf{e}_1,\mathbf{e}_2)\) by \(\mathbf{y}=3\mathbf{e}_1+2\mathbf{e}_2\). Recover \(\mathbf{e}_2\) from the new list.
- For the basis \((1,x,x^2)\) of \(P_2\), which basis vector can be replaced by \(2+x+x^2\) to retain a basis? Use its coordinates to justify your answer.
- Give a concrete reason that replacing \(\mathbf{e}_2\) by \(\mathbf{e}_1\) in \((\mathbf{e}_1,\mathbf{e}_2)\) does not preserve the span.
- Explain why the coefficient test for a basis replacement is an if-and-only-if statement, whereas the proposition for a general spanning list gives a sufficient condition.
