From a Spanning List to a Basis
A finite list may span a vector space even though some of its vectors contribute no new directions. If one vector is a linear combination of the others, removing it leaves every vector in the original span available. The spanning set reduction theorem turns this observation into a general proof: starting with any finite spanning list, we can repeatedly remove suitable redundant vectors until the remaining list is a basis.
We work over \(\mathbb{R}\). A list \(\mathbf{v}_1,\dots,\mathbf{v}_p\) in a vector space \(V\) spans \(V\) if every vector in \(V\) is a linear combination of its entries. A list is linearly independent if the equation \(c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p=\mathbf{0}\) forces every coefficient \(c_i\) to be zero. A basis is a list that is both linearly independent and spanning. The span of the empty list is taken to be \(\{\mathbf{0}\}\); if \(V=\{\mathbf{0}\}\), that list is already a basis.
We distinguish a list from the set of its entries: a list keeps track of order and repetitions, and the deletion argument removes a particular entry. The span is unchanged by reordering, but the proof will describe each deletion from the list at hand.
The Deletion Step
The key fact is that dependence identifies at least one entry that can be removed. It does not claim that every entry can be removed. The proof works by taking a nontrivial dependence relation and solving for an entry whose coefficient is nonzero.
Proof. Let \(\mathbf{v}_1,\dots,\mathbf{v}_p\) be a dependent list, where \(p\geq 1\). By the definition of dependence, there are scalars \(c_1,\dots,c_p\), not all zero, such that \(c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p=\mathbf{0}\). Choose an index \(k\) for which \(c_k\ne 0\). Since a nonzero real number has a reciprocal, we can isolate \(\mathbf{v}_k\):
Thus \(\mathbf{v}_k\) is a linear combination of the other entries. Let \(S\) be the span of the list after deleting \(\mathbf{v}_k\), and let \(T\) be the span of the original list. Every remaining entry belongs to the original list, so every linear combination of the remaining entries belongs to \(T\). Hence \(S\subseteq T\). In the other direction, every original entry other than \(\mathbf{v}_k\) belongs to \(S\), and the displayed expression shows that \(\mathbf{v}_k\) also belongs to \(S\). Therefore every linear combination of the original entries belongs to \(S\), so \(T\subseteq S\). We have \(S=T\), as required. \(\square\)
The proof also includes the case \(p=1\). If a one-entry list is dependent, its sole vector must be \(\mathbf{0}\); the relation has a nonzero coefficient, and the formula expresses that vector as the zero linear combination of the empty list. The span is still unchanged: both lists span \(\{\mathbf{0}\}\).
Proof of the Spanning Set Reduction Theorem
Proof. Start with a finite spanning list \(\mathbf{v}_1,\dots,\mathbf{v}_p\). If it is independent, it is already a basis, so no deletion is needed. If it is dependent, the lemma gives an entry whose deletion preserves the span. The shorter list therefore still spans \(V\).
Apply the same test to the resulting list. Whenever it is dependent, delete an entry supplied by the lemma; at each such step, the span remains \(V\) and the number of entries decreases by one. This process cannot continue indefinitely: the list length is a nonnegative integer initially equal to \(p\), and after at most \(p\) deletions it is zero. Thus it must stop at a list that is not dependent, which is an independent list.
Every deletion preserved the span, so the final list still spans \(V\). It is both independent and spanning, hence is a basis of \(V\). If the initial list is empty, it spans only \(\{\mathbf{0}\}\), and under the stated convention it is already a basis. This covers that case as well. \(\square\)
This proof establishes two separate requirements. The deletion lemma supplies a valid step whenever the current list is dependent; the finite decrease in list length guarantees that the steps eventually stop. Preserving the span at each step is what ensures that stopping at independence gives a basis for the original space, not merely for a smaller subspace.
Seeing the Deletion Argument in Examples
Worked Example: Removing a Redundant Vector in \(\mathbb{R}^2\)
Consider the list \(\mathbf{v}_1=(1,0)^{\top}\), \(\mathbf{v}_2=(0,1)^{\top}\), and \(\mathbf{v}_3=(1,1)^{\top}\). The relation \(\mathbf{v}_1+\mathbf{v}_2-\mathbf{v}_3=\mathbf{0}\) has a nonzero coefficient on \(\mathbf{v}_3\), and rearranging gives \(\mathbf{v}_3=\mathbf{v}_1+\mathbf{v}_2\). Delete \(\mathbf{v}_3\).
The remaining list spans \(\mathbb{R}^2\): for arbitrary \(a,b\in\mathbb{R}\), \(a\mathbf{v}_1+b\mathbf{v}_2=(a,b)^{\top}\). It is independent because \(c_1\mathbf{v}_1+c_2\mathbf{v}_2=(c_1,c_2)^{\top}=\mathbf{0}\) implies \(c_1=c_2=0\). Thus the remaining list is a basis. As a check, the deleted vector is recovered exactly: \((1,0)^{\top}+(0,1)^{\top}=(1,1)^{\top}\).
Worked Example: Two Deletions in a Polynomial Space
In the real vector space of polynomials of degree at most one, take the list \(1,x,1+x,2x\). First use the relation \(1+x=1\cdot 1+1\cdot x\) to delete \(1+x\). The list \(1,x,2x\) still has the same span, since the deleted polynomial is a combination of the retained entries. Next, \(2x=2\cdot x\), so delete \(2x\). The remaining list is \(1,x\).
Every polynomial of degree at most one has the form \(a+bx=a\cdot 1+b\cdot x\), so \(1,x\) spans the space. If \(c_1\cdot 1+c_2\cdot x\) is the zero polynomial, its constant coefficient is \(c_1=0\) and its coefficient of \(x\) is \(c_2=0\); hence the list is independent. It is a basis. Both deletions can be checked directly: \(1+x\) and \(2x\) are each in the span of \(1,x\), and \(1,x\) were entries of the original list.
Worked Example: Removing a Redundant Matrix
In the real vector space of \(2\times2\) matrices, consider \(\mathbf{E}_{11}=\begin{bmatrix}1&0\\0&0\end{bmatrix}\), \(\mathbf{E}_{12}=\begin{bmatrix}0&1\\0&0\end{bmatrix}\), \(\mathbf{E}_{21}=\begin{bmatrix}0&0\\1&0\end{bmatrix}\), \(\mathbf{E}_{22}=\begin{bmatrix}0&0\\0&1\end{bmatrix}\), and \(\mathbf{D}=\begin{bmatrix}1&0\\0&1\end{bmatrix}\). Since \(\mathbf{D}=\mathbf{E}_{11}+\mathbf{E}_{22}\), delete \(\mathbf{D}\).
To verify spanning, write an arbitrary matrix as \(\mathbf{M}=\begin{bmatrix}a&b\\c&d\end{bmatrix}\). Then \(\mathbf{M}=a\mathbf{E}_{11}+b\mathbf{E}_{12}+c\mathbf{E}_{21}+d\mathbf{E}_{22}\). To verify independence, suppose \(r_{11}\mathbf{E}_{11}+r_{12}\mathbf{E}_{12}+r_{21}\mathbf{E}_{21}+r_{22}\mathbf{E}_{22}=\mathbf{O}\). The left side is \(\begin{bmatrix}r_{11}&r_{12}\\r_{21}&r_{22}\end{bmatrix}\), so equality with the zero matrix forces each coefficient to be zero. The four remaining matrices form a basis, and the deleted matrix is checked by adding the displayed diagonal matrices.
Common Mistake: Deleting an Arbitrary Entry
Dependence proves that some entry can be removed, not that any chosen entry can be removed. For a concrete failure, consider the list \(\mathbf{e}_1=(1,0)^{\top},\mathbf{e}_2=(0,1)^{\top},2\mathbf{e}_1=(2,0)^{\top}\) in \(\mathbb{R}^2\). It is dependent because \(2\mathbf{e}_1-2\mathbf{e}_1=\mathbf{0}\), where the first term uses the first entry and the second term uses the third entry. A mistaken argument might say, “The list is dependent, so delete \(\mathbf{e}_2\).” The resulting list \(\mathbf{e}_1,2\mathbf{e}_1\) spans only vectors of the form \((t,0)^{\top}\), and cannot produce \(\mathbf{e}_2=(0,1)^{\top}\). That deletion changes the span.
The correction is to use the dependence relation to identify an entry with a nonzero coefficient and solve for that entry. Here, the relation \(2\mathbf{e}_1-1\cdot(2\mathbf{e}_1)=\mathbf{0}\) expresses the third entry as twice the first. Deleting \(2\mathbf{e}_1\) preserves the span, and the remaining \(\mathbf{e}_1,\mathbf{e}_2\) still span \(\mathbb{R}^2\). The lemma justifies the chosen deletion; dependence by itself does not justify an arbitrary one.
Why the Proof Is Useful
The theorem gives an existence guarantee without requiring that the initial spanning list have any special form. It applies whenever the list is finite, including lists with repeated vectors or a zero vector: if such an entry makes the list dependent, the proof supplies a valid deletion. Each step maintains the same span, so the final independent list still generates every vector the original list generated.
For the proof, the essential bookkeeping is simple: record which entry is removed, show it is a combination of the others, and note that the list length strictly decreases. Those details prevent two common gaps: assuming that a dependent list can lose any entry, and asserting termination without using finiteness. Together, the lemma and the decreasing-length argument establish the result for every finite spanning list.
Check Your Understanding
Use the deletion lemma and the theorem’s proof structure to answer these questions.
- In a dependence relation, why must at least one coefficient be nonzero, and how does that coefficient identify an entry that can be removed?
- Explain both inclusions needed to show that deleting a redundant entry leaves the span unchanged.
- Why does the deletion process terminate when the initial list is finite?
- In the list \((1,0)^{\top},(0,1)^{\top},(2,1)^{\top}\), which entry can be expressed using the other two? Give the expression and check it.
- What specifically fails if an entry is deleted merely because the list is dependent, without first expressing that entry as a combination of the others?
