From a Spanning List to a Basis
A spanning list may contain more vectors than are needed. Some entries can be expressed using the others, so removing them does not change the set of vectors the list can produce. The practical task is to find a subset that still spans and has no redundancy: that subset is a basis. When the listed vectors are coordinate vectors, polynomials, or matrices, row reduction gives a systematic way to identify which original entries to keep.
Throughout, the examples use real vector spaces. A basis of a vector space is an ordered list that is both linearly independent and spanning. A spanning list for a subspace \(W\) is a list whose linear combinations produce every vector in \(W\). Fix a basis for the space containing the listed vectors, and write each vector as a coordinate column relative to that basis. The resulting matrix has the listed vectors’ coordinate columns in their original order.
The distinction between the reduced matrix and the original vectors matters. Row operations transform coordinate columns; they do not, in general, transform the listed vectors into vectors from the original list. Pivot positions tell us which original list entries to keep. They do not tell us to use the columns of the reduced matrix as the basis vectors.
Why the Pivot Rule Works
We first record why row reduction preserves the coefficient relations needed for this method. Let \(\mathbf{A}\) be a coordinate matrix and let \(\mathbf{R}=\operatorname{rref}(\mathbf{A})\). Each row operation is multiplication on the left by an invertible elementary matrix. A sequence of such operations therefore gives an invertible matrix \(\mathbf{E}\) such that \(\mathbf{R}=\mathbf{E}\mathbf{A}\).
Proof. Since \(\mathbf{R}=\mathbf{E}\mathbf{A}\), the equation \(\mathbf{A}\mathbf{c}=\mathbf{0}\) implies \(\mathbf{R}\mathbf{c}=\mathbf{E}\mathbf{A}\mathbf{c}=\mathbf{E}\mathbf{0}=\mathbf{0}\). Conversely, if \(\mathbf{R}\mathbf{c}=\mathbf{0}\), then \(\mathbf{E}\mathbf{A}\mathbf{c}=\mathbf{0}\). Multiplying by \(\mathbf{E}^{-1}\) gives \(\mathbf{A}\mathbf{c}=\mathbf{0}\). This proves both directions. \(\square\)
Proof. Let \(\mathbf{R}=\operatorname{rref}(\mathbf{A})\). First consider the pivot columns of \(\mathbf{R}\). Each has a \(1\) in its pivot row and \(0\) in every other row, so these columns are linearly independent: in a linear combination equal to zero, the entry in each pivot row forces the coefficient of its pivot column to be zero. By the proposition, the same coefficient equation holds for the corresponding columns of \(\mathbf{A}\). Thus the retained coordinate columns are independent, and so are the original vectors, because coordinate representation relative to a basis is unique.
Next, every non-pivot column of \(\mathbf{R}\) is a linear combination of its pivot columns. In fact, its entries in the pivot rows give the coefficients: subtracting that combination makes every pivot-row entry zero, and all other rows of an RREF are zero rows. The resulting column is therefore zero. By the proposition, this same coefficient relation holds among the corresponding columns of \(\mathbf{A}\). Consequently, every original vector is in the span of the retained original vectors. The full list spans \(W\), so the retained vectors also span \(W\). They are both independent and spanning, and hence form a basis of \(W\). \(\square\)
This theorem also explains how to find the dependence equations. For a non-pivot column, read its entries in the pivot rows of the RREF; these are the coefficients expressing the corresponding original vector in terms of the original pivot-column vectors. The proposition guarantees that the relation read from the reduced matrix is valid for the original vectors.
Worked Examples in Three Kinds of Spaces
Worked Example: Extracting a Basis from Coordinate Vectors
Find a basis for the span of \(\mathbf{v}_1=(1,0,1)^{\top}\), \(\mathbf{v}_2=(0,1,1)^{\top}\), \(\mathbf{v}_3=(1,1,2)^{\top}\), and \(\mathbf{v}_4=(2,1,3)^{\top}\) in \(\mathbb{R}^3\).
Put the vectors in the columns, then subtract \(R_1\) from \(R_3\), followed by subtracting \(R_2\) from the new \(R_3\):
This is in RREF, with pivot columns 1 and 2. Retain the corresponding original vectors \(\mathbf{v}_1,\mathbf{v}_2\). The third column of the reduced matrix is the sum of its first and second columns; the fourth is twice the first plus the second. Thus the relations for the original vectors are \(\mathbf{v}_3=\mathbf{v}_1+\mathbf{v}_2\) and \(\mathbf{v}_4=2\mathbf{v}_1+\mathbf{v}_2\).
Check: \((1,0,1)^{\top}+(0,1,1)^{\top}=(1,1,2)^{\top}=\mathbf{v}_3\), and \(2(1,0,1)^{\top}+(0,1,1)^{\top}=(2,1,3)^{\top}=\mathbf{v}_4\). The pivot test gives independence of \(\mathbf{v}_1,\mathbf{v}_2\); the displayed relations show that all four original vectors lie in their span. They form a basis of the given span.
Worked Example: Extracting a Basis of Polynomials
Find a basis for the span in \(P_2\), the real polynomials of degree at most \(2\), of \(p_1=1+x\), \(p_2=x+x^2\), \(p_3=1+2x+x^2\), and \(p_4=1-x^2\).
Use the monomial basis \((1,x,x^2)\), so the coordinate columns are \((1,1,0)^{\top}\), \((0,1,1)^{\top}\), \((1,2,1)^{\top}\), and \((1,0,-1)^{\top}\). Subtract \(R_1\) from \(R_2\), then subtract the new \(R_2\) from \(R_3\):
The pivot columns are 1 and 2, so retain \(p_1\) and \(p_2\). Column 3 of the RREF is the sum of columns 1 and 2, and column 4 is column 1 minus column 2. These give \(p_3=p_1+p_2\) and \(p_4=p_1-p_2\).
Check: \((1+x)+(x+x^2)=1+2x+x^2=p_3\), while \((1+x)-(x+x^2)=1-x^2=p_4\). Since the pivot columns show that \(p_1,p_2\) are independent and the equations express both other polynomials using them, \((p_1,p_2)\) is a basis for the span.
Worked Example: Extracting a Basis of Matrices
Find a basis for the span in \(\mathbb{R}^{2\times2}\) of \(\mathbf{M}_1=\begin{bmatrix}1&0\\0&1\end{bmatrix}\), \(\mathbf{M}_2=\begin{bmatrix}0&1\\1&0\end{bmatrix}\), \(\mathbf{M}_3=\begin{bmatrix}1&1\\1&1\end{bmatrix}\), and \(\mathbf{M}_4=\begin{bmatrix}2&-1\\-1&2\end{bmatrix}\).
Use the natural basis \((\mathbf{E}_{11},\mathbf{E}_{12},\mathbf{E}_{21},\mathbf{E}_{22})\), where \(\mathbf{E}_{ij}\) has a \(1\) in position \((i,j)\) and zeros elsewhere. In this order, the coordinate columns are \((a_{11},a_{12},a_{21},a_{22})^{\top}\). Thus the coordinate matrix is:
Apply \(R_3\to R_3-R_2\) and \(R_4\to R_4-R_1\):
The pivot columns are 1 and 2, so retain \(\mathbf{M}_1,\mathbf{M}_2\). The third column is the sum of the first two, and the fourth is twice the first minus the second. Hence \(\mathbf{M}_3=\mathbf{M}_1+\mathbf{M}_2\) and \(\mathbf{M}_4=2\mathbf{M}_1-\mathbf{M}_2\).
Check: \(\mathbf{M}_1+\mathbf{M}_2=\begin{bmatrix}1&1\\1&1\end{bmatrix}=\mathbf{M}_3\), and \(2\mathbf{M}_1-\mathbf{M}_2=\begin{bmatrix}2&-1\\-1&2\end{bmatrix}=\mathbf{M}_4\). The two retained matrices are independent because their coordinate columns are pivot columns; the equations show they span all four listed matrices. Thus they form a basis of the span.
A Reliable Workflow and a Common Pitfall
For coordinate vectors, use their given coordinates. For polynomials or matrices, specify a basis and write each object’s coordinate column in that basis.
Keep the columns in the same order as the given list. Each column must represent one listed object.
Use the pivot positions in the RREF to identify the list entries to retain.
Keep the original objects at the pivot indices, then verify that the other listed objects can be expressed using them.
Common pitfall: using RREF columns as the basis objects. In the polynomial example, the first column of the RREF is \((1,0,0)^{\top}\), but the coordinate column of \(p_1=1+x\) is \((1,1,0)^{\top}\). Claiming that the RREF’s first column represents \(p_1\) is therefore incorrect. The RREF column is a transformed coordinate column; its pivot position tells us to retain the original first polynomial. The basis is \((p_1,p_2)\), not a list formed by treating the columns of the reduced matrix as the original polynomials.
There is also a useful check on the final selection. The number of retained vectors must match the number of pivots, and the selected vectors must be members of the given list. To establish that the selection is a basis, connect both parts of the definition to the computation: pivot columns give independence, while the dependence equations for non-pivot columns show that the retained vectors still span the original list. If the original list spans a subspace, the retained list then spans that same subspace.
Check Your Understanding
For each problem, identify the coordinates or coordinate matrix, then explain why the selected original vectors form a basis of the stated span.
- Use row reduction to extract a basis from \((1,0,1)^{\top}\), \((1,1,0)^{\top}\), and \((2,1,1)^{\top}\) in \(\mathbb{R}^3\). Find a relation for any non-pivot column.
- In \(P_2\), use the basis \((1,x,x^2)\) to find a basis for the span of \(1+x\), \(1-x\), and \(2\).
- For the matrices \(\begin{bmatrix}1&0\\0&0\end{bmatrix}\), \(\begin{bmatrix}0&1\\0&0\end{bmatrix}\), and \(\begin{bmatrix}1&1\\0&0\end{bmatrix}\), write the coordinate matrix in the natural matrix basis and identify a basis for their span.
- Why does a pivot index tell you which original object to retain, rather than instructing you to use the corresponding column of the RREF?
- State how pivot columns establish independence and how non-pivot columns establish that the retained vectors span the original list.
