Finding Column-Space and Row-Space Bases

Two Spaces, Two Ways to Read Row Reduction

Row reduction is a single computation that can help find bases for two different spaces associated with a matrix. The key is that the two bases are read from different places. To find a basis for the column space, use the pivot-column indices but take the columns from the original matrix. To find a basis for the row space, take the nonzero rows of an echelon form of the matrix. These instructions are not interchangeable: row operations preserve row space, but they can change column space.

Throughout, matrices and vectors have real entries, and vectors are columns. For \(\mathbf{A}\in\mathbb{R}^{m\times n}\), its column space \(\operatorname{Col}\mathbf{A}\) is the span of its columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\) in \(\mathbb{R}^m\). Its row space \(\operatorname{Row}\mathbf{A}\) is the span in \(\mathbb{R}^n\) of its rows. A basis for either space is a list that spans that space and is linearly independent.

For the column-space method, reduce \(\mathbf{A}\) to reduced row echelon form (RREF), record the pivot-column indices, and select those same columns from \(\mathbf{A}\). Do not select them from the RREF. For the row-space method, any row echelon form will do: its nonzero rows form a basis for \(\operatorname{Row}\mathbf{A}\). The reason these two procedures work is that row operations preserve row space, while the pivot structure of the reduced matrix records how the original columns relate to one another.

Why the Column-Space Method Works

Proof. Each row operation is reversible and is left multiplication by an invertible elementary matrix. Therefore there is an invertible matrix \(\mathbf{E}\) such that \(\mathbf{R}=\mathbf{E}\mathbf{A}\). Write \(\mathbf{r}_j\) for column \(j\) of \(\mathbf{R}\), so \(\mathbf{r}_j=\mathbf{E}\mathbf{a}_j\). In RREF, the pivot columns are standard basis vectors in \(\mathbb{R}^m\), with their \(1\)s in distinct pivot rows. They are linearly independent. Every nonpivot column of \(\mathbf{R}\) is a linear combination of those pivot columns: its entries in the pivot rows give the coefficients, and its entries in all other rows are zero. Thus the pivot columns of \(\mathbf{R}\) span every column of \(\mathbf{R}\). Because \(\mathbf{E}\) is invertible, a relation among selected \(\mathbf{a}_{j_k}\) holds exactly when the same relation holds among \(\mathbf{r}_{j_k}\). The selected original columns are therefore independent. Also, for each column \(\mathbf{a}_j\), the corresponding combination expressing \(\mathbf{r}_j\) in terms of the pivot columns transfers through \(\mathbf{E}^{-1}\) to the same combination expressing \(\mathbf{a}_j\) in terms of \(\mathbf{a}_{j_1},\dots,\mathbf{a}_{j_r}\). So the selected original columns span \(\operatorname{Col}\mathbf{A}\) as well as being independent. They form a basis. \(\square\)

The proof explains why the pivot indices come from the reduced matrix but the basis vectors come from the original one. Row operations act on every column at once, changing the column vectors themselves. They preserve the coefficient relations among corresponding columns, which is what lets us transfer the pivot information back to the original matrix.

Why the Nonzero Echelon Rows Work

Proof. A row swap does not change the span of the rows. Multiplying a row by a nonzero scalar preserves that span, since the operation can be reversed by multiplying by the reciprocal. Replacing a row by itself plus a multiple of another row also preserves the span: the new row is a combination of old rows, and the old row is recovered by subtracting the same multiple of the other row. Applying these facts through the finite sequence of row operations shows that \(\mathbf{A}\) and \(\mathbf{E}\) have the same row space. The rows of \(\mathbf{E}\) span this space by the definition of row space, and its zero rows add nothing to the span. It remains to show that the nonzero rows are independent. Suppose a linear combination of them is zero and at least one coefficient is nonzero. Choose the first nonzero row, in echelon order, whose coefficient is nonzero. In the column containing that row’s leading entry, every later row has a zero, and every earlier row has coefficient zero in the proposed combination. The combination’s entry in this column is therefore the chosen coefficient multiplied by the nonzero leading entry, so it cannot be zero. This contradicts the assumed zero combination. Hence all coefficients are zero, the nonzero rows are independent, and they form a basis. \(\square\)

Using a Different Echelon Form

The column-space method uses pivot indices, which are read from the reduced form, while the row-space method can use the nonzero rows of an echelon form that is not reduced. For instance, reducing all the way to RREF may produce simpler rows, but it is not necessary for a row-space basis. Whatever echelon form is used, the zero rows must be omitted, since a list containing the zero vector is dependent and cannot be a basis.

A Reliable Procedure and a Common Mistake

Common mistake: taking pivot columns from the reduced matrix. In the first example, the pivot columns of the echelon matrix are \((1,0,0)^{\top}\) and \((0,1,0)^{\top}\). These are not a basis for the original column space. In fact, \((1,0,0)^{\top}\) is not even in that space: every vector in it has the form \(s(1,2,1)^{\top}+t(0,1,1)^{\top}=(s,2s+t,s+t)^{\top}\). To obtain \((1,0,0)^{\top}\), the first coordinate requires \(s=1\), and the second requires \(t=-2\); then the third coordinate is \(-1\), not \(0\). The correction is to keep the pivot indices 1 and 3, then select columns 1 and 3 from the original matrix.

Another distinction is that a spanning list need not be a basis. The original rows of the first example span its row space, but they are dependent: its third row equals its second row minus its first row. The nonzero echelon rows avoid this redundancy and, by the theorem, form a basis. The two procedures provide efficient ways to extract bases, while the proofs explain why they work and what each calculation preserves.