From a Spanning List to a Basis
A finite list may span a space even though some of its entries add nothing to the span. If one entry can be expressed as a linear combination of the others, it is redundant: every vector that was obtainable before its removal remains obtainable afterward. Repeating this deletion can turn a spanning list into a basis, a list that both spans the space and is linearly independent.
Let \(V\) be a finite-dimensional vector space over a field \(\mathbb{F}\), and let \((\mathbf{v}_1,\dots,\mathbf{v}_p)\) be an ordered finite list in \(V\). The span of this list consists of all linear combinations \(c_1\mathbf{v}_1+\cdots+c_p\mathbf{v}_p\), with coefficients \(c_i\in\mathbb{F}\). The span of the empty list is defined to be \(\{\mathbf{0}\}\). The order and the individual positions in a list matter: two equal vectors at different positions are still two entries that can be considered separately.
For a finite list, dependence guarantees that at least one entry is redundant. The key point is that a nontrivial dependence relation has at least one nonzero coefficient, and that coefficient can be divided out in a field. Once an entry is known to be redundant, deleting it preserves the span.
Why a Redundant Entry Can Be Deleted
Proof. Write \(S\) for the span of the full list and \(S_k\) for the span after deleting \(\mathbf{v}_k\). If \(\mathbf{v}_k\in S_k\), then every entry of the full list belongs to \(S_k\): the entries other than \(\mathbf{v}_k\) belong by the definition of \(S_k\), and \(\mathbf{v}_k\) belongs by assumption. Therefore every linear combination in \(S\) belongs to \(S_k\), so \(S\subseteq S_k\). Every combination of the shorter list is also a combination of the full list, with coefficient \(0\) on \(\mathbf{v}_k\), so \(S_k\subseteq S\). Hence \(S=S_k\). Conversely, if deleting \(\mathbf{v}_k\) preserves the span, then \(\mathbf{v}_k\in S=S_k\), since \(\mathbf{v}_k\) is itself in the span of the full list. Thus \(\mathbf{v}_k\) is a combination of the other entries. \(\square\)
The deletion criterion describes exactly when a deletion is safe. It is not enough that a dependence relation involves several entries: to delete a particular entry, that entry must be expressible using the others. In practice, a nonzero coefficient in a dependence relation identifies an entry that can be isolated.
Worked Example: Removing a Redundant Vector in R³
Consider the list
Since \(\mathbf{v}_3=\mathbf{v}_1+\mathbf{v}_2\), the third entry is a combination of the others. Delete it. The remaining list \((\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_4)\) spans \(\mathbb{R}^3\): for any \(a,b,c\in\mathbb{R}\),
To check independence, suppose \(a\mathbf{v}_1+b\mathbf{v}_2+c\mathbf{v}_4=\mathbf{0}\). Comparing coordinates gives \((a,b,c)=(0,0,0)\). Thus the shorter list is independent as well as spanning, so it is a basis. The span has not changed: the removed vector was already \(\mathbf{v}_1+\mathbf{v}_2\), and every vector previously expressed using it can instead use those two entries.
Why the Process Must Stop
Proof. Start with the given spanning list, which has some finite number \(p\) of entries. If the current list is independent, it is already a basis because it still spans \(V\). If it is dependent, there are coefficients \(c_1,\dots,c_q\), not all zero, such that \(c_1\mathbf{w}_1+\cdots+c_q\mathbf{w}_q=\mathbf{0}\), where \((\mathbf{w}_1,\dots,\mathbf{w}_q)\) is the current list. Choose an index \(k\) with \(c_k\ne0\). Because \(\mathbb{F}\) is a field, \(c_k\) has an inverse, and rearranging gives \(\mathbf{w}_k=-c_k^{-1}\sum_{j\ne k}c_j\mathbf{w}_j\). Thus \(\mathbf{w}_k\) is a combination of the other entries. By the deletion criterion, removing it preserves the span. Each such step reduces the number of entries by one, so after at most \(p\) deletions the process must stop. It can stop only when the current list is independent, because any dependent current list permits another deletion by the argument just given. The final list is therefore independent and still spans \(V\), hence is a basis. If \(V=\{\mathbf{0}\}\), deleting all zero entries leaves the empty list, whose span is \(\{\mathbf{0}\}\) and which is independent because it has no coefficients that could form a nontrivial relation. \(\square\)
This proof explains both parts of the method. A deletion preserves the original span, and finiteness prevents an endless sequence of deletions. The final list is not merely shorter; it has no redundant entries. This argument works over any field: the only division is by a coefficient already chosen to be nonzero.
If the current list is dependent, write a nontrivial relation among its entries.
Its entry can be isolated as a combination of the other entries.
The deletion criterion guarantees that the span is unchanged.
Since the list is finite and loses one entry at each deletion, this ends with a basis.
Two Further Reductions
Worked Example: Two Deletions in R²
Start with the list \((\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3,\mathbf{u}_4)\) in \(\mathbb{R}^2\), where
First, \(\mathbf{u}_3=\mathbf{u}_1+\mathbf{u}_2\), so delete \(\mathbf{u}_3\). In the shorter list, \(\mathbf{u}_4=2\mathbf{u}_1+\mathbf{u}_2\), so delete \(\mathbf{u}_4\) as well. The remaining list is \((\mathbf{u}_1,\mathbf{u}_2)\).
For any \((a,b)^{\top}\in\mathbb{R}^2\), \(a\mathbf{u}_1+b\mathbf{u}_2=(a,b)^{\top}\), so the remaining list spans. If \(c\mathbf{u}_1+d\mathbf{u}_2=\mathbf{0}\), then \((c,d)^{\top}=(0,0)^{\top}\), so it is independent. As a direct check on the deletions, the removed vectors are exactly \((1,1)^{\top}=(1,0)^{\top}+(0,1)^{\top}\) and \((2,1)^{\top}=2(1,0)^{\top}+(0,1)^{\top}\). Each is recovered from the final list, which remains a basis of \(\mathbb{R}^2\).
Worked Example: Reducing a Spanning List of Polynomials
Work over \(\mathbb{R}\) in the polynomial space \(P_2\), consisting of all polynomials of degree at most \(2\). Consider the list
There are two useful relations:
Delete \(p_3\), then delete \(p_5\). The remaining list is \((p_1,p_2,p_4)\). To verify that it spans, let \(q=a+bx+cx^2\) be any element of \(P_2\). Then
To verify independence, suppose \(\alpha p_1+\beta p_2+\gamma p_4=0\). Comparing the constant, \(x\), and \(x^2\) coefficients yields \(\alpha=0\), \(\alpha+\beta+\gamma=0\), and \(\beta=0\). The first and third equations give \(\alpha=\beta=0\), and then the second gives \(\gamma=0\). Thus the remaining list is independent and spans \(P_2\). The displayed relations also check both deletions directly: substituting \(p_1=1+x\), \(p_2=x+x^2\), and \(p_4=x\) gives \(p_3=1+x^2\) and \(p_5=1\).
Common Pitfall: The Zero Coefficient
A dependence relation only licenses deletion of an entry whose coefficient in that relation is nonzero. For a concrete example in \(\mathbb{R}^2\), let \(\mathbf{v}_1=(1,0)^{\top}\), \(\mathbf{v}_2=(0,1)^{\top}\), and \(\mathbf{v}_3=(1,0)^{\top}\). The relation \(\mathbf{v}_1-\mathbf{v}_3=\mathbf{0}\) has coefficient \(0\) on \(\mathbf{v}_2\). It proves that \(\mathbf{v}_1\) can be recovered from \(\mathbf{v}_3\), and that \(\mathbf{v}_3\) can be recovered from \(\mathbf{v}_1\). It does not prove that \(\mathbf{v}_2\) can be recovered from the other two.
The wrong deletion is \(\mathbf{v}_2\): after deleting it, the remaining vectors are both \((1,0)^{\top}\), and every combination has second coordinate \(0\). In particular, \((0,1)^{\top}\) is no longer in their span, so the span has changed. The correction is to isolate an entry with a nonzero coefficient. In the displayed relation, either \(\mathbf{v}_1\) or \(\mathbf{v}_3\) can be deleted safely. This distinction is valid over every field, including fields in which some nonzero integers represent zero; the argument uses only a coefficient that is nonzero in the field.
What the Reduction Achieves
The method preserves the span, not the particular appearance or order of a list. Different choices of dependence relation can lead to different final bases. What is guaranteed is that every removed entry was recoverable from entries retained at that step, and the final list has no nontrivial dependence relation. If the original list had \(p\) entries, the final basis has at most \(p\) entries because the procedure only deletes entries. The reduction does not require a preferred choice of which redundant entry to remove; it requires only that the chosen entry have a nonzero coefficient in a dependence relation.
For the zero vector space, a spanning list can consist entirely of zero vectors. Each such entry is redundant if any other entries remain, and the final empty list spans the zero space by convention. In a nonzero space, the empty list cannot span, since its span is only \(\{\mathbf{0}\}\). Thus the same finite deletion principle covers both the ordinary case and the boundary case without treating the empty list as an exception to the definition of a basis.
Check Your Understanding
For each question, identify the entries being deleted and verify that the final list has the required properties.
- If \(\mathbf{v}_3=2\mathbf{v}_1-\mathbf{v}_2\), which entry can be deleted from a spanning list without changing its span?
- Suppose a dependence relation has coefficient \(0\) on \(\mathbf{v}_k\). What additional information is needed before \(\mathbf{v}_k\) can be deleted?
- Why does each deletion in the reduction process preserve the span?
- Why can a finite list not undergo infinitely many successive deletions?
- What is the span and independence status of the empty list when \(V=\{\mathbf{0}\}\)?
