Why the Length of a Spanning List Matters
A basis is both linearly independent and spanning: its vectors give enough information to produce every vector in the space, without redundancy. The exchange lemma makes a precise comparison between a basis and any other spanning list. Its consequence is a lower bound: if a space has a basis with \(n\) vectors, no list of fewer than \(n\) vectors can span it.
Throughout, vectors and scalars are over \(\mathbb{R}\), unless a space such as a polynomial space is specified. A list records both entries and their positions, so repeated vectors count more than once. A list \((\mathbf{v}_1,\dots,\mathbf{v}_k)\) spans a vector space \(V\) if every \(\mathbf{v}\in V\) can be written as \(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k\), with scalars \(c_i\in\mathbb{R}\). A basis is an ordered list that is both spanning and linearly independent.
The theorem compares the length of a spanning list with the length of a known basis. It does not say that every list of length at least \(n\) spans: having enough entries is necessary, but it is not by itself sufficient. We will prove the theorem by inserting the basis vectors into a spanning list one at a time.
The Exchange Lemma, with Its Required Condition
The exchange lemma says that a vector can replace a particular entry of a spanning list when its expression in that list has a nonzero coefficient on that entry. That condition matters. A vector with only zero coefficients in a chosen expression cannot be used to justify replacing any entry by this argument.
Proof. The replacement list spans every vector in the original list: it contains \(\mathbf{v}_i\) for \(i\ne j\), and the equation for \(\mathbf{x}\) can be rearranged because \(c_j\ne0\): \(\mathbf{v}_j=\frac{1}{c_j}\bigl(\mathbf{x}-\sum_{i\ne j}c_i\mathbf{v}_i\bigr)\). Thus every vector in the original list belongs to the span of the replacement list. Since the original list spans \(V\), the replacement list spans \(V\) as well. \(\square\)
The lemma preserves the span, not necessarily the independence of the list. Its conclusion is exactly what the main proof needs: each exchange keeps the list spanning while making room for another vector from the basis.
Worked Example: A Valid Exchange in \(\mathbb{R}^2\)
Start with the spanning list \(\mathbf{v}_1=(1,0)\), \(\mathbf{v}_2=(0,1)\), and choose \(\mathbf{x}=(2,1)\). Since \(\mathbf{x}=2\mathbf{v}_1+\mathbf{v}_2\), the coefficient of \(\mathbf{v}_1\) is nonzero. Replace \(\mathbf{v}_1\) by \(\mathbf{x}\), giving the list \(((2,1),(0,1))\).
Check directly that the replacement list spans the original vectors. The second vector is already \(\mathbf{v}_2=(0,1)\), and \(\frac12(2,1)-\frac12(0,1)=(1,0)=\mathbf{v}_1\). Since the original two vectors span \(\mathbb{R}^2\), the replacement list spans \(\mathbb{R}^2\) too.
Check: \((2,1)\) and \((0,1)\) are both in \(\mathbb{R}^2\), and the displayed equations recover \((1,0)\) and \((0,1)\). Their span therefore contains every linear combination of the standard basis vectors, which is every vector in \(\mathbb{R}^2\).
Replacing Entries Until the Count Is Forced
Here is the proof of the lower bound. Keep track of two parts of the current spanning list: the basis vectors already inserted and the entries that have not yet been replaced. The next basis vector cannot be made from the inserted ones alone, because the basis is linearly independent. Therefore, in any expression for it using the current spanning list, at least one of the unreplaced entries must have a nonzero coefficient. The exchange lemma then permits the next replacement.
Assume a list of length \(k<n\) spans \(V\). The aim is to derive a contradiction with the independence of the basis.
After \(j\) successful exchanges, the current list still spans \(V\) and contains \(\mathbf{b}_1,\dots,\mathbf{b}_j\), together with \(k-j\) of the original entries.
For \(j<k\), the vector \(\mathbf{b}_{j+1}\) is not in \(\operatorname{span}\{\mathbf{b}_1,\dots,\mathbf{b}_j\}\). Express it using the current spanning list. At least one coefficient on an unreplaced entry must be nonzero, so the exchange lemma replaces that entry by \(\mathbf{b}_{j+1}\).
After \(k\) exchanges, the list consists of \(\mathbf{b}_1,\dots,\mathbf{b}_k\) and still spans \(V\). It must then span \(\mathbf{b}_{k+1}\), contradicting independence of the basis.
Proof. Suppose that the spanning list has length \(k<n\). If \(k=0\), the empty list spans only the zero vector, whereas a basis with \(n\ge1\) contains the nonzero vector \(\mathbf{b}_1\). This is a contradiction. Now suppose \(k\ge1\). We show inductively that after \(j\) exchanges, for \(0\le j\le k\), there is a spanning list containing \(\mathbf{b}_1,\dots,\mathbf{b}_j\) and \(k-j\) unreplaced entries from the original list. For \(j=0\), this is the original spanning list. Suppose \(j<k\) and the claim holds. Since the basis is independent, \(\mathbf{b}_{j+1}\notin\operatorname{span}\{\mathbf{b}_1,\dots,\mathbf{b}_j\}\). The current list spans \(V\), so it expresses \(\mathbf{b}_{j+1}\) as a linear combination of its entries. If all coefficients on the \(k-j\) unreplaced entries were zero, this expression would put \(\mathbf{b}_{j+1}\) in \(\operatorname{span}\{\mathbf{b}_1,\dots,\mathbf{b}_j\}\), which is impossible. Some unreplaced entry therefore has a nonzero coefficient. By the exchange lemma, replacing that entry with \(\mathbf{b}_{j+1}\) preserves the span. This proves the induction step. After \(k\) exchanges, \((\mathbf{b}_1,\dots,\mathbf{b}_k)\) spans \(V\). In particular, \(\mathbf{b}_{k+1}\) is a linear combination of \(\mathbf{b}_1,\dots,\mathbf{b}_k\). Moving that combination to one side gives a nontrivial linear relation among \(\mathbf{b}_1,\dots,\mathbf{b}_{k+1}\), since the coefficient of \(\mathbf{b}_{k+1}\) is \(1\). This contradicts independence of the basis. Hence \(k\ge n\). \(\square\)
Counting Vectors in \(\mathbb{R}^n\)
The standard basis \((\mathbf{e}_1,\dots,\mathbf{e}_n)\) is a basis of \(\mathbb{R}^n\): its vectors are linearly independent and every column vector \((x_1,\dots,x_n)^\top\) equals \(x_1\mathbf{e}_1+\cdots+x_n\mathbf{e}_n\). Applying the theorem to this basis gives an immediate count.
Proof. The standard basis of \(\mathbb{R}^n\) has \(n\) vectors. The theorem therefore requires every spanning list for \(\mathbb{R}^n\) to have length at least \(n\). \(\square\)
Worked Example: Two Vectors Cannot Span \(\mathbb{R}^3\)
Consider \(\mathbf{v}_1=(1,0,1)\) and \(\mathbf{v}_2=(0,1,1)\). The count already shows that two vectors cannot span \(\mathbb{R}^3\), since the standard basis has three vectors. We can also identify a specific vector they fail to produce: \(\mathbf{e}_3=(0,0,1)\).
A general linear combination of the two vectors is \(a\mathbf{v}_1+b\mathbf{v}_2=(a,b,a+b)\). To equal \(\mathbf{e}_3\), its first coordinate would require \(a=0\), and its second coordinate would require \(b=0\). Then the third coordinate is \(a+b=0\), not \(1\). So no such coefficients exist.
Check: The coordinate equations are \(a=0\), \(b=0\), and \(a+b=1\). Substituting the first two into the third gives \(0=1\), an impossibility. Thus \(\mathbf{e}_3\) is outside the span of the two-vector list.
Worked Example: Two Polynomials Cannot Span \(P_2\)
Let \(P_2\) be the real vector space of polynomials of degree at most \(2\). Its monomial basis is \((1,x,x^2)\), which has three vectors. The theorem says that no list of two polynomials can span all of \(P_2\). For a concrete instance, take \(p_1=1+x\) and \(p_2=x+x^2\), and test whether they can produce \(x^2\).
Suppose \(a p_1+b p_2=x^2\). Expanding the left side gives \(a(1+x)+b(x+x^2)=a+(a+b)x+bx^2\). Matching coefficients of \(1,x,x^2\) with \(x^2=0+0x+1x^2\) yields \(a=0\), \(a+b=0\), and \(b=1\). The first equation gives \(a=0\); the second then gives \(b=0\), contradicting \(b=1\).
Check: The coefficient equations have no simultaneous solution, so \(x^2\) is not a linear combination of \(p_1,p_2\). This particular list does not span \(P_2\), in agreement with the count that rules out every two-polynomial spanning list.
Common Pitfall: Replacement Is Not Automatic
A tempting but incorrect version of the exchange lemma says that any vector can replace any entry of a spanning list while preserving the span. For a concrete failure, the one-entry list \((1)\) spans \(\mathbb{R}\). Replacing its entry by \(0\) gives \((0)\), whose span is just \(\{0\}\), not \(\mathbb{R}\). The expression \(0=0\cdot1\) has coefficient zero, so it does not meet the exchange lemma’s nonzero-coefficient condition.
There is a useful distinction here. The lemma does not claim that a replacement works for every expression of the added vector; it says that a replacement works when the chosen expression has a nonzero coefficient on the entry being replaced. In the main proof, the required coefficient is guaranteed: if all coefficients on the unreplaced entries were zero, the next basis vector would lie in the span of the earlier basis vectors, contradicting independence.
The count also has a one-way conclusion. A list with fewer than \(n\) vectors cannot span \(\mathbb{R}^n\), but having \(n\) or more vectors does not ensure spanning. For instance, \((1,0)\) and \((2,0)\) both lie on the horizontal axis, so every linear combination has second coordinate \(0\); the list does not span \(\mathbb{R}^2\), despite having two entries. The lower bound rules out too-short lists, but a separate argument is needed to establish that a particular list spans.
Check Your Understanding
Use the exchange lemma and the finite-basis count in your reasoning.
- A space has a basis of length \(5\). Can a list of \(4\) vectors span it? Explain.
- In the exchange lemma, why must the coefficient of the replaced entry be nonzero?
- Can three vectors span \(\mathbb{R}^4\)? State the basis-count argument.
- Why does having at least \(n\) vectors not guarantee that a list spans \(\mathbb{R}^n\)? Give an example.
- In the replacement proof, why can the next basis vector not be expressed using only the basis vectors already inserted?
