How Successive Exchanges Work
A spanning list may contain vectors that are not needed to produce its span. This gives us room to replace some of its vectors with vectors that matter for a different purpose. The key is to choose each replacement carefully: the vector being removed must actually contribute to a representation of the new vector. If that contribution is nonzero, we can solve for the vector being removed and show that the span has not changed.
Here a list keeps track of positions: two equal vectors in different positions are still two entries. A list \((\mathbf{v}_1,\dots,\mathbf{v}_m)\) in a real vector space \(V\) is spanning if every vector in \(V\) is a linear combination of its entries. It is linearly independent if the only solution to \(c_1\mathbf{v}_1+\cdots+c_m\mathbf{v}_m=\mathbf{0}\) is \(c_1=\cdots=c_m=0\). A basis is a list that is both spanning and linearly independent.
The exchange method uses two related facts. From a spanning list, we can insert successive vectors from an independent list while preserving the span. If the starting list is a basis, each exchange also preserves independence, so every intermediate list remains a basis. In both cases the inserted vectors must be independent; that condition ensures that the next vector to insert cannot be produced using only the earlier inserted vectors.
One Exchange Preserves the Span
Proof. The new list spans every vector in the original list: it contains all \(\mathbf{v}_i\) for \(i\ne j\), and the displayed equation can be rearranged as \[ \mathbf{v}_j=\frac{1}{a_j}\left(\mathbf{u}-\sum_{i\ne j}a_i\mathbf{v}_i\right). \] Thus \(\mathbf{v}_j\) is in the span of the new list, and so is every linear combination of the original list. In the other direction, \(\mathbf{u}\) is a linear combination of the original list, and every other entry of the new list is an original entry. Therefore the new list is contained in the span of the original list. The two spans are equal. \(\square\)
The theorem supplies the local step. To use it repeatedly, we also need to know that at each stage there is an entry available to replace. The independence of the incoming list supplies that guarantee.
Proof. We describe the \(i\)th exchange, assuming the first \(i-1\) exchanges have been made. The current list still spans \(V\), and it contains \(\mathbf{u}_1,\dots,\mathbf{u}_{i-1}\) in the positions already exchanged. Since it spans \(V\), write \(\mathbf{u}_i\) as a linear combination of its entries. At least one coefficient on an entry not yet exchanged must be nonzero. Otherwise that representation would put \(\mathbf{u}_i\) in \(\operatorname{span}\{\mathbf{u}_1,\dots,\mathbf{u}_{i-1}\}\). This would give a nontrivial linear relation among \(\mathbf{u}_1,\dots,\mathbf{u}_i\), contradicting their independence. Choose an unexchanged entry with nonzero coefficient and replace it by \(\mathbf{u}_i\). The single exchange theorem shows that the span is unchanged. This argument applies successively for \(i=1,\dots,k\), proving the claim. \(\square\)
This result preserves the span; it does not claim that the full list stays independent. If the starting list is already a basis, however, independence is preserved too.
Proof. Suppose the first \(i-1\) exchanges have produced a basis containing \(\mathbf{u}_1,\dots,\mathbf{u}_{i-1}\) and the as-yet unreplaced entries of the original basis. A basis gives each vector a unique representation: two representations would subtract to give a linear relation among the basis entries, which must have all coefficients zero. Represent \(\mathbf{u}_i\) in this current basis. Some coefficient on an unreplaced entry must be nonzero. If all those coefficients were zero, \(\mathbf{u}_i\) would be in the span of the earlier \(\mathbf{u}\)'s, contrary to the independence of \((\mathbf{u}_1,\dots,\mathbf{u}_k)\). Replace an unreplaced basis entry with nonzero coefficient by \(\mathbf{u}_i\). The single exchange theorem shows that the new list spans \(V\).
To check independence, suppose a linear combination of the new list is \(\mathbf{0}\). If the coefficient of \(\mathbf{u}_i\) is zero, the relation involves only entries from the previous basis, so all its coefficients are zero by that basis's independence. If the coefficient of \(\mathbf{u}_i\) is nonzero, the relation expresses \(\mathbf{u}_i\) as a combination of the previous basis entries other than the one removed. That is impossible: its unique representation in the previous basis has a nonzero coefficient on the removed entry. Thus the new list is independent as well as spanning, so it is a basis. Repeating this argument proves the theorem. \(\square\)
Worked Exchanges in \(\mathbb{R}^3\)
Worked Example: Insert Two Vectors into a Basis
Start with the standard basis \((\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3)\) of \(\mathbb{R}^3\), and insert \(\mathbf{u}_1=(1,1,0)\) and \(\mathbf{u}_2=(0,1,1)\). First check that the incoming list is independent. If \(a\mathbf{u}_1+b\mathbf{u}_2=\mathbf{0}\), then \((a,a+b,b)=(0,0,0)\). The first and third coordinates give \(a=0\) and \(b=0\).
For the first exchange, \(\mathbf{u}_1=\mathbf{e}_1+\mathbf{e}_2\), so the coefficient of \(\mathbf{e}_1\) is nonzero. Replace \(\mathbf{e}_1\) with \(\mathbf{u}_1\), giving \((\mathbf{u}_1,\mathbf{e}_2,\mathbf{e}_3)\). To insert \(\mathbf{u}_2\), use \[ \mathbf{u}_2=0\mathbf{u}_1+1\mathbf{e}_2+1\mathbf{e}_3. \] Replace \(\mathbf{e}_2\), whose coefficient is \(1\). The resulting list is \((\mathbf{u}_1,\mathbf{u}_2,\mathbf{e}_3)\).
Check: For arbitrary \((x,y,z)\in\mathbb{R}^3\), the first list represents it uniquely: \[ (x,y,z)=x\mathbf{u}_1+(y-x)\mathbf{e}_2+z\mathbf{e}_3. \] The final list also represents it uniquely: \[ (x,y,z)=x\mathbf{u}_1+(y-x)\mathbf{u}_2+(z-y+x)\mathbf{e}_3. \] The formulas show that both lists span \(\mathbb{R}^3\); uniqueness follows because the coefficients are determined by \(x,y,z\). Each is therefore a basis.
Worked Example: Exchange from a Redundant Spanning List
Consider the spanning list \((\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3,\mathbf{e}_1+\mathbf{e}_2)\) in \(\mathbb{R}^3\). Insert \(\mathbf{u}_1=(1,1,0)\) and \(\mathbf{u}_2=(1,0,1)\). These two vectors are independent: if \(a\mathbf{u}_1+b\mathbf{u}_2=\mathbf{0}\), then \((a+b,a,b)=(0,0,0)\), which forces \(a=b=0\).
For the first exchange, \(\mathbf{u}_1=\mathbf{e}_1+\mathbf{e}_2\). Replace the first entry \(\mathbf{e}_1\), whose coefficient is \(1\), to obtain \((\mathbf{u}_1,\mathbf{e}_2,\mathbf{e}_3,\mathbf{e}_1+\mathbf{e}_2)\). Now \[ \mathbf{u}_2=\mathbf{u}_1-\mathbf{e}_2+\mathbf{e}_3. \] The coefficient of \(\mathbf{e}_3\) is \(1\), so replace that entry. The resulting list is \((\mathbf{u}_1,\mathbf{e}_2,\mathbf{u}_2,\mathbf{e}_1+\mathbf{e}_2)\).
Check: The first exchange preserved the span because \(\mathbf{e}_1=\mathbf{u}_1-\mathbf{e}_2\). The second preserved it because \(\mathbf{e}_3=\mathbf{u}_2-\mathbf{u}_1+\mathbf{e}_2\). Thus the final list has the same span as the original, namely \(\mathbb{R}^3\). It is still redundant: its first and fourth entries are equal, so their difference gives a nontrivial relation. This example shows why the general spanning-list theorem promises preserved span, not a basis.
Exchanging in a Polynomial Space
Worked Example: Insert Polynomials into a Basis
In the real vector space \(P_2\) of polynomials of degree at most \(2\), start with the basis \((1,x,x^2)\). Insert \(u_1=1+x\) and \(u_2=x+x^2\). The incoming list is independent: if \(a(1+x)+b(x+x^2)=0\), comparing the constant, \(x\), and \(x^2\) coefficients gives \(a=0\), \(a+b=0\), and \(b=0\), hence \(a=b=0\).
Since \(u_1=1+x\), replace \(1\) by \(u_1\). In the resulting list, \(u_2=0u_1+1x+1x^2\), so replace \(x\) by \(u_2\). The final list is \((1+x,x+x^2,x^2)\).
Check: For an arbitrary polynomial \(\alpha+\beta x+\gamma x^2\), the coefficients in the final list are determined by \[ \alpha+\beta x+\gamma x^2 =\alpha(1+x)+(\beta-\alpha)(x+x^2)+(\gamma-\beta+\alpha)x^2. \] Indeed, the constant coefficient is \(\alpha\), the coefficient of \(x\) is \(\alpha+\beta-\alpha=\beta\), and the coefficient of \(x^2\) is \(\beta-\alpha+\gamma-\beta+\alpha=\gamma\). The representation is unique because its coefficients are fixed by \(\alpha,\beta,\gamma\). The final list is a basis.
Choosing the Entry to Replace
An exchange is not permission to remove any entry. The coefficient condition identifies the entries that can be removed while preserving the span. For a spanning list, a representation of the incoming vector may not be unique; it is enough to find a representation with a nonzero coefficient on an entry not previously replaced. The successive-exchange theorem guarantees such an entry when the incoming list is independent.
A practical way to keep the argument organised is to record, at every stage, (1) which incoming vectors have been inserted, (2) which original entries remain, and (3) the representation that justifies the next replacement. If the starting list is a basis, also check that each selected coefficient is nonzero in its basis representation; this is what ensures the new list remains independent.
Common Pitfall: Replacing an Entry with Zero Coefficient
Suppose the spanning list in \(\mathbb{R}^2\) is \((\mathbf{e}_1,\mathbf{e}_2)\), and the vector to insert is \(\mathbf{u}=\mathbf{e}_1\). Its representation is \(\mathbf{u}=1\mathbf{e}_1+0\mathbf{e}_2\). Replacing \(\mathbf{e}_2\) because it is an entry in the list is a wrong exchange: the result is \((\mathbf{e}_1,\mathbf{e}_1)\), whose span contains only multiples of \(\mathbf{e}_1\), not \(\mathbf{e}_2\). The correction is to replace \(\mathbf{e}_1\), whose coefficient is \(1\). Then the list \((\mathbf{u},\mathbf{e}_2)\) still spans \(\mathbb{R}^2\). The single-exchange proof explains the difference: solving for the removed vector requires division by its coefficient, so a zero coefficient cannot justify a replacement.
Check Your Understanding
For each question, identify the representation or independence condition that justifies your conclusion.
- In \(\mathbb{R}^2\), start with \((\mathbf{e}_1,\mathbf{e}_2)\) and insert \((1,2)\). Which entry can be replaced, and what is the resulting basis?
- Explain why an independent incoming list ensures that its \(i\)th vector is not in the span of the first \(i-1\) incoming vectors.
- In the spanning list \((\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_1+\mathbf{e}_2)\), replace one entry with \((2,1)\) while preserving the span. Give a representation with a nonzero coefficient on the entry you remove.
- For the polynomial list \((1+x,x+x^2,x^2)\), write the coordinates of \(3+2x+5x^2\) in that list.
- Why does the exchange method not imply that a list obtained from a redundant spanning list is a basis?
