The Extension Process
An independent list has no redundant vectors, but it may not yet describe every vector in the space. To enlarge it without creating redundancy, we need a careful rule for choosing additional vectors: add a vector only when it lies outside the span of the vectors already present. In a finite-dimensional space, we can make this rule into a finite procedure by checking the vectors in a basis one at a time.
Let \(V\) be a finite-dimensional vector space over \(\mathbb{F}\), where \(\mathbb{F}\) is either \(\mathbb{R}\) or \(\mathbb{C}\). The span of a list \((\mathbf{v}_1,\dots,\mathbf{v}_k)\) is the set of all its linear combinations. The list is linearly independent if the equation \(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k=\mathbf{0}\) implies \(c_1=\cdots=c_k=0\). A basis of \(V\) is a linearly independent list whose span is \(V\). We begin with an independent list and choose any basis \((\mathbf{b}_1,\dots,\mathbf{b}_n)\) of \(V\) as our candidate list.
The test is always relative to the current list, not just to the original one. Each accepted candidate changes the span, and a later candidate may then be in that larger span. The procedure does not require that every vector of the chosen basis be added. It requires that each one be either already accounted for by the current span or included when it is not.
Why Adding an Outside Vector Preserves Independence
Proof. Suppose \(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k+d\mathbf{w}=\mathbf{0}\). If \(d\ne0\), rearranging and dividing by \(d\) gives \(\mathbf{w}=-\frac{c_1}{d}\mathbf{v}_1-\cdots-\frac{c_k}{d}\mathbf{v}_k\), which places \(\mathbf{w}\) in the span of the original list, contrary to the hypothesis. Therefore \(d=0\). The equation becomes \(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k=\mathbf{0}\), and independence of the original list gives \(c_1=\cdots=c_k=0\). Thus the enlarged list is independent. \(\square\)
This proof explains the outside-the-span test: it is exactly what rules out a new dependence relation involving the vector being added. If the candidate is already in the span, the test tells us to skip it. In that case appending it would produce a dependent list, because its expression as a linear combination of the existing vectors would give a nontrivial relation.
Why the Procedure Ends with a Basis
There are only \(n\) candidates, so the procedure has exactly \(n\) tests and must terminate. To see why its final list spans \(V\), consider any candidate \(\mathbf{b}_i\). If it was added, it belongs to the final list. If it was skipped, it belonged to the span of the list at the time of its test. The list can only grow afterward, so \(\mathbf{b}_i\) still belongs to the span of the final list. Thus the final span contains every vector in the basis \((\mathbf{b}_1,\dots,\mathbf{b}_n)\), and therefore contains \(V\). Since it is also a subset of \(V\), it equals \(V\).
At every addition, the lemma preserves independence. A skipped candidate does not change the list, so independence is preserved then as well. Consequently, the final list is independent and spans \(V\); by the definition of basis, it is a basis. This reasoning also covers the zero-dimensional space: its basis has no vectors to check, and the only independent starting list is the empty list. The process makes no additions, and that list spans the zero space.
Proof. There are \(n\) candidates, so the procedure terminates after \(n\) tests. The starting list is independent by assumption. At each test, either no vector is added, leaving the list unchanged, or a vector outside the current span is added, in which case the lemma proves that the new list is independent. By induction over the finite sequence of tests, the final list is independent. For every \(i\), the candidate \(\mathbf{b}_i\) was either added or was in the span of the current list when tested. Since the list never shrinks, each \(\mathbf{b}_i\) lies in the span of the final list. The basis vectors span \(V\), so the final list spans \(V\). It is therefore a basis by definition. If \(n=0\), there are no tests; the same argument says the final list spans \(V=\{\mathbf{0}\}\), and independence is preserved from the assumed starting list. \(\square\)
The dimension results established earlier in the course give an additional bound on the process. If \(\dim V=n\), an independent list in \(V\) has at most \(n\) vectors. Thus, if the initial list has \(k\) vectors, at most \(n-k\) candidates can be added. This bound is consistent with the procedure, but it is not a stopping test: we still check all the chosen basis vectors to guarantee that the final list spans the space.
Worked Extensions
Worked Example: Extending a List in R³
Start with the independent list \(((1,1,0))\) in \(\mathbb{R}^3\), and test the standard basis \((\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3)\), where \(\mathbf{e}_1=(1,0,0)\), \(\mathbf{e}_2=(0,1,0)\), and \(\mathbf{e}_3=(0,0,1)\).
The vector \(\mathbf{e}_1\) is not a multiple of \((1,1,0)\), so it is not in the current span and we add it. Next, \(\mathbf{e}_2=(1,1,0)-(1,0,0)\), so it is already in the span of the current list and we skip it. The vector \(\mathbf{e}_3\) is outside that span: every combination of \((1,1,0)\) and \((1,0,0)\) has third coordinate \(0\). We add \(\mathbf{e}_3\). The resulting list is \(((1,1,0),(1,0,0),(0,0,1))\).
Check independence: If \(a(1,1,0)+b(1,0,0)+c(0,0,1)=(0,0,0)\), its coordinates give \(a+b=0\), \(a=0\), and \(c=0\). Hence \(a=b=c=0\).
Check spanning: For any \((x,y,z)\in\mathbb{R}^3\),
So the list is a basis of \(\mathbb{R}^3\), as the procedure predicts.
Worked Example: Extending a List in P₂
Let \(P_2\) be the real vector space of polynomials of degree at most \(2\). Start with \((1+x,\;x+x^2)\), and test the monomial basis \((1,x,x^2)\). The starting list is independent: if \(a(1+x)+b(x+x^2)=0\), comparing the constant and \(x^2\) coefficients gives \(a=0\) and \(b=0\).
The candidate \(1\) is outside the current span. Indeed, if \(a(1+x)+b(x+x^2)=1\), the \(x^2\) coefficient gives \(b=0\), the \(x\) coefficient then gives \(a=0\), and the constant coefficient would be \(0=1\), which is impossible. Add \(1\).
Next, \(x=(1+x)-1\), so \(x\) is already in the current span and is skipped. Finally, \(x^2=-(1+x)+(x+x^2)+1\), so \(x^2\) is also in the current span and is skipped. The final list is \((1+x,\;x+x^2,\;1)\).
Check spanning: For any \(a_0+a_1x+a_2x^2\in P_2\),
Check independence: If \(\alpha(1+x)+\beta(x+x^2)+\gamma=0\), the \(x^2\) coefficient gives \(\beta=0\), the \(x\) coefficient gives \(\alpha+\beta=0\), hence \(\alpha=0\), and the constant coefficient then gives \(\gamma=0\). Thus the final list is a basis of \(P_2\).
Worked Example: A List That Needs No Additions
In \(\mathbb{R}^2\), start with \(((1,1),(1,-1))\) and test \(\mathbf{e}_1=(1,0)\) and \(\mathbf{e}_2=(0,1)\) in that order. The initial list is independent: \(a(1,1)+b(1,-1)=(0,0)\) gives \(a+b=0\) and \(a-b=0\), so \(a=b=0\).
Both candidates are already in the current span:
Therefore neither is added. To check that the unchanged list spans \(\mathbb{R}^2\), write any \((x,y)\) as
The list remains independent and spans, so it was already a basis. An extension process may correctly add no vectors at all.
Common Mistake: Adding a Vector That Is Already in the Span
A tempting but incorrect rule is to add each candidate without checking whether it is redundant. For example, start with the independent list \(((1,0))\) in \(\mathbb{R}^2\). If we append \((2,0)\), we get the dependent list \(((1,0),(2,0))\), since
and the coefficients \(2\) and \(-1\) are not both zero. The correction is to test membership in the current span: \((2,0)=2(1,0)\), so we skip it. We must still test a candidate outside the span, such as \((0,1)\); appending it gives an independent list that spans \(\mathbb{R}^2\).
The two parts of the procedure have different jobs. The outside-the-span condition protects independence, while checking every vector in a basis ensures spanning. Adding arbitrary outside vectors could preserve independence without ever reaching all of \(V\); checking a basis supplies a finite, guaranteed set of candidates.
Check Your Understanding
For each question, justify your decision using span, independence, or both.
- In \(\mathbb{R}^3\), start with \(((1,0,1))\) and test \(\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3\) in order. Which candidates are added?
- Why does adding a vector already in the current span make the enlarged list dependent?
- In \(P_2\), express \(x^2\) as a linear combination of \(1+x\), \(x+x^2\), and \(1\).
- Which part of the procedure guarantees independence, and which part guarantees spanning?
- What happens when the space has dimension zero, and why does the procedure still terminate with a basis?
