A Practical Strategy for Extending a List
To extend an independent list to a basis, begin with the prescribed vectors and consider additional vectors one at a time. Keep a candidate precisely when adding it preserves independence; reject it when it is already in the span of the vectors kept so far. The method is practical only when the candidates are chosen appropriately: together with the prescribed vectors, they must span the whole space. This condition ensures that after every candidate has been considered, the accepted list spans the space as well as remaining independent.
All vector spaces in this tutorial are over \(\mathbb{R}\) and finite-dimensional. A basis of a vector space is an ordered list that is both linearly independent and spanning. A list spans a space if every vector in that space is a linear combination of vectors in the list. For computations in \(\mathbb{R}^n\), place the vectors as columns of a matrix. For a polynomial space, use coefficients in the standard basis \(1,x,\dots,x^m\) as the coordinate columns.
Proof. Suppose first that \(\mathbf{w}\in\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_k\}\). Then \(\mathbf{w}=a_1\mathbf{v}_1+\cdots+a_k\mathbf{v}_k\) for some scalars \(a_i\), so \(a_1\mathbf{v}_1+\cdots+a_k\mathbf{v}_k-1\mathbf{w}=\mathbf{0}\). This is a nontrivial dependence relation because the coefficient of \(\mathbf{w}\) is \(-1\). Conversely, suppose the longer list is dependent. Then there are scalars \(c_1,\dots,c_k,d\), not all zero, such that \(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k+d\mathbf{w}=\mathbf{0}\). If \(d=0\), the original list has a nontrivial dependence relation, contrary to its independence. Therefore \(d\ne0\), and rearranging gives \(\mathbf{w}=-\frac{c_1}{d}\mathbf{v}_1-\cdots-\frac{c_k}{d}\mathbf{v}_k\). Thus \(\mathbf{w}\) belongs to the span of the original list. For \(k=0\), the same argument reduces to the fact that a one-vector list is dependent exactly when its vector is zero. \(\square\)
In computations, this criterion can be applied by putting the current vectors and the candidate into a column matrix and checking whether each column is a pivot column after row reduction. A missing pivot in the candidate’s column means the enlarged list is dependent. Row operations are used to test independence, but if the task is to retain particular vectors, the accepted vectors must be chosen from the original list, not from the rows of the reduced matrix.
Extending a List in \(\mathbb{R}^3\)
Worked Example: Choose Between Two Candidates
Start with the independent vectors \(\mathbf{u}_1=(1,1,0)\) and \(\mathbf{u}_2=(0,1,1)\). Consider the candidates \(\mathbf{w}_1=(1,2,1)\) and \(\mathbf{w}_2=(1,0,0)\), in that order. Extend the prescribed list to a basis of \(\mathbb{R}^3\).
First, \(\mathbf{w}_1=\mathbf{u}_1+\mathbf{u}_2\), so it is in the span of the prescribed vectors and must be rejected. The column test gives the same conclusion:
There is no pivot in column 3. Indeed, the reduced system for a dependence relation gives \(c_1+c_3=0\) and \(c_2+c_3=0\); taking \(c_3=1\) yields \(-\mathbf{u}_1-\mathbf{u}_2+\mathbf{w}_1=\mathbf{0}\).
Now test \(\mathbf{w}_2\) together with the two prescribed vectors. The successive row operations shown below produce a pivot in every column:
The operations are, in order, \(R_2\to R_2-R_1\), \(R_3\to R_3-R_2\), \(R_1\to R_1-R_3\), and \(R_2\to R_2+R_3\), using the current rows at each step. Thus the accepted list \((\mathbf{u}_1,\mathbf{u}_2,\mathbf{w}_2)\) is independent. To check that it spans, let \((r,s,t)\in\mathbb{R}^3\). Choose \(a=s-t\), \(b=t\), and \(c=r-s+t\). Then
Every vector in \(\mathbb{R}^3\) is therefore a combination of the accepted list, so it is a basis. In particular, the three coordinates in the middle expression are \(a+c,a+b,b\), in that order.
Why the Candidate List Must Cover the Space
The candidate test explains when to accept a vector; a separate argument explains why the process ends with a spanning list. It is not enough that the candidates be independent among themselves, or merely that they look like useful additional vectors. The initial list and all the candidates together must span the ambient space. Under that hypothesis, each rejected candidate was already spanned by accepted vectors at the moment it was considered, and each accepted candidate remains in the final list.
Proof. The initial list is independent by hypothesis. At each step a candidate is appended only if the enlarged list is independent, so induction over the finite number of candidates shows that the final list is independent. It remains to prove that it spans \(V\). Consider any candidate \(\mathbf{w}\). If it was accepted, it belongs to the final list. If it was rejected, the list that existed at that step was independent, and the candidate test shows that \(\mathbf{w}\) belonged to the span of that list. Every vector in that earlier list is still in the final list, so \(\mathbf{w}\) belongs to the span of the final list. The initial vectors also belong to the final list. Hence the final list spans every vector in \(L\) and every candidate. Those vectors together span \(V\) by hypothesis, so the final list spans \(V\). Since it is both independent and spanning, it is a basis. \(\square\)
The theorem also describes a useful setup: if a familiar basis of the space is available, use its vectors as candidates. The initial list and that basis certainly span the space, so the procedure is guaranteed to succeed. Candidates may be rejected, and the final basis need not contain every candidate.
Extending Prescribed Polynomials
Let \(\mathbb{P}_2(\mathbb{R})\) denote the vector space of real polynomials of degree at most \(2\), including the zero polynomial. The list \((1,x,x^2)\) is its standard basis: a polynomial \(\alpha+\beta x+\gamma x^2\) has those coefficients, and the only way a linear combination of \(1,x,x^2\) is the zero polynomial is for all three coefficients to be zero. Thus coefficient columns in this basis give a concrete matrix test.
Worked Example: Extend a Polynomial to a Basis
Start with the prescribed polynomial \(p=1+x\). Process the candidates \(1,x,x^2\) in that order to extend the list to a basis of \(\mathbb{P}_2(\mathbb{R})\).
The prescribed one-vector list is independent because \(1+x\ne0\). With \(1\) added, the coefficient columns in the basis \((1,x,x^2)\) are \((1,1,0)^{\top}\) and \((1,0,0)^{\top}\). Their matrix reduces as follows:
The operations are \(R_2\to R_2-R_1\), then \(R_2\to -R_2\) and \(R_1\to R_1-R_2\). Both columns have pivots, so \(1\) is accepted. Next consider \(x\). The three coefficient columns are those of \(1+x,1,x\):
After \(R_2\to R_2-R_1\), scale \(R_2\) by \(-1\), then use \(R_1\to R_1-R_2\). There is no pivot in column 3, so \(x\) is rejected. The dependence is \(x=(1+x)-1\).
Finally, add \(x^2\). Its coefficient column is \((0,0,1)^{\top}\), and the matrix is
Here \(R_2\to R_2-R_1\), followed by \(R_2\to -R_2\) and \(R_1\to R_1-R_2\). The final accepted list \((1+x,1,x^2)\) is independent. It spans as well: for any \(\alpha+\beta x+\gamma x^2\),
This identity verifies spanning for arbitrary real coefficients \(\alpha,\beta,\gamma\). Therefore the accepted list is a basis of \(\mathbb{P}_2(\mathbb{R})\).
A Second Candidate List in \(\mathbb{R}^4\)
Worked Example: Scan the Standard Basis Vectors
Begin with \(\mathbf{v}_1=(1,1,0,0)\) and \(\mathbf{v}_2=(0,1,1,0)\), and process \(\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3,\mathbf{e}_4\) in order. The prescribed vectors are independent: if \(a\mathbf{v}_1+b\mathbf{v}_2=\mathbf{0}\), the first and third coordinates give \(a=0\) and \(b=0\).
The candidate \(\mathbf{e}_1\) is accepted. If \(a\mathbf{v}_1+b\mathbf{v}_2+c\mathbf{e}_1=\mathbf{0}\), the second, third, and then first coordinates give \(a+b=0\), \(b=0\), and \(a+c=0\), so \(a=b=c=0\). The next candidate is rejected because \(\mathbf{e}_2=\mathbf{v}_1-\mathbf{e}_1\). The candidate \(\mathbf{e}_3\) is also rejected, since \(\mathbf{e}_3=\mathbf{v}_2-\mathbf{v}_1+\mathbf{e}_1\).
Accept \(\mathbf{e}_4\): it cannot be a combination of the earlier accepted vectors, all of which have fourth coordinate zero, because \(\mathbf{e}_4\) has fourth coordinate one. The final list is \((\mathbf{v}_1,\mathbf{v}_2,\mathbf{e}_1,\mathbf{e}_4)\). To verify spanning, given any \((r,s,t,u)\in\mathbb{R}^4\), set \(a=s-t\), \(b=t\), \(c=r-s+t\), and \(d=u\). Then
Thus the final list spans \(\mathbb{R}^4\). Its independence also follows directly: a zero combination has first coordinate \(a+c=0\), second \(a+b=0\), third \(b=0\), and fourth \(d=0\). These imply \(b=0\), \(a=0\), \(c=0\), and \(d=0\). The list is a basis.
Common Pitfall: Matching the Coordinates in Order
When solving for coefficients, a correct-looking formula can fail if the coordinates of a combination are matched in the wrong order. In the \(\mathbb{R}^3\) example above, the combination has coordinates \((a+c,a+b,b)\). A mistaken choice \(a=t-s,\ b=s,\ c=r-t+s\) gives \((r,t,s)\), not \((r,s,t)\). For instance, with \((r,s,t)=(0,1,0)\), that choice gives \((0,0,1)\), not \((0,1,0)\). The correction is to solve the second coordinate equation \(a+b=s\) and the third equation \(b=t\), giving \(b=t\), \(a=s-t\), and then \(c=r-a=r-s+t\). Substitution yields \((a+c,a+b,b)=(r,s,t)\).
There is a second common error: treating a candidate list as if it automatically spans the space. The procedure guarantees independence of the accepted list, but spanning follows only when the initial vectors together with all candidates span the ambient space. Before scanning candidates, identify why that condition holds—for example, because the candidates include a known basis.
Check Your Understanding
For each problem, specify which candidates are accepted and justify that the final list is a basis, or explain why the candidate list does not guarantee one.
- Start with \((1,0,1)\) in \(\mathbb{R}^3\) and consider \((1,1,0),(0,1,0),(0,0,1)\) in order. Which vectors are accepted?
- In \(\mathbb{P}_2(\mathbb{R})\), start with \(1+x^2\) and consider \(1,x,x^2\). Find an accepted basis.
- For the vectors \(\mathbf{v}_1=(1,1,0)\), \(\mathbf{v}_2=(0,1,1)\), determine whether \((\mathbf{v}_1,\mathbf{v}_2,(1,2,1))\) is independent. Give a dependence relation if it is not.
- State the hypothesis on the initial list and candidate list that ensures the candidate-extension procedure ends with a basis.
- Explain why a rejected candidate belongs to the span of the final accepted list.
