Reducing a Spanning List in Practice

From a Spanning List to a Basis

A list may span a space even when some members contribute nothing new. For example, one vector might be a combination of the others, or the list might contain a repeated vector. Reducing a spanning list means removing such redundancy without changing what the list can produce. The aim is to finish with a list that still spans the same space and is linearly independent.

For vectors in \(\mathbb{R}^n\), the practical tool is a matrix whose columns are the listed vectors. Row reduction identifies which original columns to keep. The columns to keep are not, in general, the columns of the reduced matrix: they are the columns of the original matrix in the pivot positions.

Here is the key deletion test. It applies to any vector space over \(\mathbb{R}\): removing a member preserves the span exactly when that member can already be made from the members left behind.

Proof. Write \(S\) for the span of the full list and \(S_k\) for the span after removing \(\mathbf{v}_k\). If \(\mathbf{v}_k\in S_k\), then every linear combination using \(\mathbf{v}_k\) can be rewritten using only the other vectors. Thus \(S\subseteq S_k\); also \(S_k\subseteq S\) because every remaining vector was in the original list. Hence \(S=S_k\). Conversely, if \(S=S_k\), then \(\mathbf{v}_k\in S=S_k\), so \(\mathbf{v}_k\) is a linear combination of the other members. \(\square\)

The Pivot-Column Method

Given a spanning list \((\mathbf{v}_1,\dots,\mathbf{v}_p)\) in \(\mathbb{R}^n\), form \(\mathbf{A}=\begin{bmatrix}\mathbf{v}_1&\cdots&\mathbf{v}_p\end{bmatrix}\). Row-reduce \(\mathbf{A}\) to reduced row echelon form (RREF). Keep the columns of the original \(\mathbf{A}\) whose positions contain pivots in \(\operatorname{rref}(\mathbf{A})\). The resulting list is a basis for the span of the original list.

Proof. Let \(\mathbf{R}=\operatorname{rref}(\mathbf{A})\). Row reduction consists of elementary row operations, each of which is invertible, so \(\mathbf{R}=\mathbf{E}\mathbf{A}\) for an invertible matrix \(\mathbf{E}\). A linear relation among columns of \(\mathbf{A}\) therefore holds among the corresponding columns of \(\mathbf{R}\), and conversely: multiplying a relation by \(\mathbf{E}\), or by \(\mathbf{E}^{-1}\), preserves it. In \(\mathbf{R}\), the pivot columns are linearly independent: each has a \(1\) in its own pivot row and \(0\) in the other pivot rows, so a combination of them equal to zero must have every coefficient zero. Every nonpivot column of \(\mathbf{R}\) is a combination of its pivot columns: its entries in the pivot rows give the coefficients, and the RREF form gives zero in the remaining rows. These same coefficients express the corresponding column of \(\mathbf{A}\) as a combination of the pivot columns of \(\mathbf{A}\), because \(\mathbf{E}\) is invertible. Thus the selected original columns are independent and span all columns of \(\mathbf{A}\), as required. \(\square\)

So the method gives both properties required of a basis. It also tells you how to check the result in practice: each omitted vector must be expressible using the retained vectors. When the original list is known to span a space \(V\), the retained list spans \(V\) as well.

Worked Reductions in \(\mathbb{R}^n\)

Applying the Method to Polynomials

The same procedure works for polynomials of bounded degree. For \(d\geq 0\), let \(P_d(\mathbb{R})\) be the vector space of real polynomials of degree at most \(d\), together with the zero polynomial. Its standard basis is \((1,x,\dots,x^d)\). Represent a polynomial by the column of its coefficients in this order, including zero coefficients for missing powers. Then a list of polynomials becomes a list of coordinate columns, and the pivot-column method applies without change.

Common Mistake: Keeping Reduced Columns

A frequent error is to use the pivot columns of the reduced matrix as the proposed basis vectors. Row operations change the columns, so those columns need not be members of the original list. In the first example, the RREF has first two columns \((1,0,0)^\top\) and \((0,1,0)^\top\). Claiming these are the basis vectors would be wrong: they are not the original vectors \(\mathbf{v}_1=(1,0,1)^\top\) and \(\mathbf{v}_2=(0,1,1)^\top\).

The correction is to use the RREF only to find the pivot positions, then select the original columns in those positions. Here the pivot positions are 1 and 2, so the correct basis is \((\mathbf{v}_1,\mathbf{v}_2)\). A second check is to verify that each omitted original column is a combination of the selected original columns, as shown in the example.

Another tempting but incorrect shortcut is to delete a vector because its entries look similar to another vector’s entries. Redundancy means being a linear combination of the remaining vectors, not merely resembling them. The coefficient matrix and its pivots provide a systematic test.