The Pivot Index Is Preserved; the Column Is Not
Row reduction is a powerful way to identify pivot positions, but it changes the entries in the matrix. This distinction matters when the goal is to describe the column space: the columns of the reduced matrix usually are not the vectors in the original column space. The pivot positions tell us which column indices to use; the vectors we select are the columns at those indices in the original matrix.
Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), with columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\). Its column space is \(\operatorname{Col}\mathbf{A}=\operatorname{span}\{\mathbf{a}_1,\dots,\mathbf{a}_n\}\). A pivot position is the location of a leading entry in an echelon form. Row operations preserve the solutions of \(\mathbf{A}\mathbf{x}=\mathbf{0}\), so they preserve which combinations of columns equal zero. But row operations act on the columns as vectors: they change their entries, and generally change the column space as a subset of \(\mathbb{R}^m\).
The reason this works is that a row operation applies the same invertible transformation to every column. Thus a relation among columns before reduction holds exactly when the same relation holds among the transformed columns. The transformed columns make the pivot structure easier to read, but they are not generally the original vectors we need.
Why Row Operations Preserve Column Relations
Each elementary row operation has an inverse row operation: swapping two rows is undone by swapping them again; multiplying a row by a nonzero scalar is undone by multiplying it by the reciprocal; and adding a multiple of one row to another is undone by subtracting that multiple. Therefore, if \(\mathbf{R}\) is obtained from \(\mathbf{A}\) by row operations, there is an invertible matrix \(\mathbf{E}\) such that \(\mathbf{R}=\mathbf{E}\mathbf{A}\). For each index \(j\), the \(j\)th column of \(\mathbf{R}\) is \(\mathbf{E}\mathbf{a}_j\).
Proof. Since \(\mathbf{R}\) is obtained by invertible row operations, write \(\mathbf{R}=\mathbf{E}\mathbf{A}\) with \(\mathbf{E}\) invertible. Let \(\mathbf{r}_j\) be column \(j\) of \(\mathbf{R}\). In reduced row echelon form, each pivot column \(\mathbf{r}_{p_i}\) has entry \(1\) in its pivot row and \(0\) in every other row. Every nonzero row is a pivot row, and zero rows contain only zero entries. Therefore, for every column index \(j\), \(\mathbf{r}_j=\sum_{i=1}^r r_{q_i j}\mathbf{r}_{p_i}\), where \(q_i\) is the row containing the pivot in column \(p_i\). Applying \(\mathbf{E}^{-1}\) gives \(\mathbf{a}_j=\sum_{i=1}^r r_{q_i j}\mathbf{a}_{p_i}\). Thus every original column is in the span of the original pivot columns, so those columns span \(\operatorname{Col}\mathbf{A}\).
For independence, suppose \(\sum_{i=1}^r c_i\mathbf{a}_{p_i}=\mathbf{0}\). Multiplying by \(\mathbf{E}\) gives \(\sum_{i=1}^r c_i\mathbf{r}_{p_i}=\mathbf{0}\). Looking at pivot row \(q_k\), the entry of this combination is \(c_k\), because pivot column \(p_k\) has a \(1\) in that row and all the other pivot columns have \(0\) there. Hence \(c_k=0\) for every \(k\). The original pivot columns are independent as well as spanning, so they form a basis for the column space. \(\square\)
The proof uses the reduced form to read off the coefficients expressing each transformed column through transformed pivot columns. Applying the inverse transformation carries those equalities back to the original columns. It does not assert that \(\operatorname{Col}\mathbf{A}\) and \(\operatorname{Col}\mathbf{R}\) are the same subspace. Instead, the invertible transformation \(\mathbf{E}\) carries one to the other.
Worked Examples: Tracking the Original Columns
Worked Example: A Single Pivot in a Three-Row Matrix
Find the pivot index for \(\mathbf{A}=\begin{bmatrix}1&2\\2&4\\3&6\end{bmatrix}\), and identify the corresponding original column. Show explicitly that the row operations change the columns.
Apply \(R_2\to R_2-2R_1\) and \(R_3\to R_3-3R_1\):
The only pivot is in column 1. The original columns are \(\mathbf{a}_1=(1,2,3)^{\top}\) and \(\mathbf{a}_2=(2,4,6)^{\top}\). The column to select is therefore \(\mathbf{a}_1\), not the first reduced column \((1,0,0)^{\top}\).
To verify the row operations together, their matrix is \(\mathbf{E}=\begin{bmatrix}1&0&0\\-2&1&0\\-3&0&1\end{bmatrix}\). Multiplication gives first row \((1,2)\), second row \(-2(1,2)+(2,4)=(-2,-4)+(2,4)=(0,0)\), and third row \(-3(1,2)+(3,6)=(-3,-6)+(3,6)=(0,0)\), as in the reduction. The original column relation also checks the spanning claim: \(\mathbf{a}_2=2\mathbf{a}_1\). Thus the single original pivot column spans the column space and is nonzero, so it is a basis for that space.
Check: \(2(1,2,3)^{\top}=(2,4,6)^{\top}=\mathbf{a}_2\). The reduced first column is different from \(\mathbf{a}_1\), illustrating why the pivot index, rather than the reduced column vector, is what we keep.
Worked Example: Two Pivot Indices
For \(\mathbf{A}=\begin{bmatrix}1&2&1\\2&4&3\\-1&-2&0\end{bmatrix}\), find the pivot indices and verify that the matching original columns span and are independent.
First apply \(R_2\to R_2-2R_1\) and \(R_3\to R_3+R_1\), then apply \(R_3\to R_3-R_2\):
Then \(R_1\to R_1-R_2\) gives the RREF:
The pivot indices are 1 and 3. The corresponding original columns are \(\mathbf{a}_1=(1,2,-1)^{\top}\) and \(\mathbf{a}_3=(1,3,0)^{\top}\). The remaining original column is \(\mathbf{a}_2=(2,4,-2)^{\top}=2\mathbf{a}_1\), so the selected columns span all three original columns. To check independence, suppose \(c_1\mathbf{a}_1+c_3\mathbf{a}_3=\mathbf{0}\). The third coordinate gives \(-c_1=0\), hence \(c_1=0\); the first coordinate then gives \(c_3=0\). Thus the selected columns are independent.
Check: \(2(1,2,-1)^{\top}=(2,4,-2)^{\top}=\mathbf{a}_2\), and the independence calculation forces both coefficients to vanish. These checks establish that the original columns at the pivot indices—not the reduced columns at those indices—form the required basis.
Worked Example: Reduced Pivot Columns Can Be Outside the Original Column Space
Consider \(\mathbf{A}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}\). Determine whether the pivot columns of its RREF can themselves be used as vectors in \(\operatorname{Col}\mathbf{A}\).
Applying \(R_3\to R_3-R_1-R_2\) gives
Both columns are pivot columns. The reduced pivot columns are \((1,0,0)^{\top}\) and \((0,1,0)^{\top}\), while the original columns are \(\mathbf{a}_1=(1,0,1)^{\top}\) and \(\mathbf{a}_2=(0,1,1)^{\top}\). A general vector in the original column space has the form \(s\mathbf{a}_1+t\mathbf{a}_2=(s,t,s+t)^{\top}\). To obtain \((1,0,0)^{\top}\), the first two coordinates would require \(s=1,t=0\), but then the third coordinate is \(1\), not \(0\). So the first reduced pivot column is not in the original column space. For \((0,1,0)^{\top}\), the first two coordinates require \(s=0,t=1\), again giving third coordinate \(1\), not \(0\).
Check: the row-operation matrix is \(\mathbf{E}=\begin{bmatrix}1&0&0\\0&1&0\\-1&-1&1\end{bmatrix}\), and \(\mathbf{E}\mathbf{A}=\begin{bmatrix}1&0\\0&1\\0&0\end{bmatrix}\): its third row is \(- (1,0)-(0,1)+(1,1)=(0,0)\). The computation confirms that row reduction has transformed the columns, not left them as the original vectors.
Common Pitfall: Confusing a Pivot Position with a Pivot Column Vector
A common incorrect step is to find the RREF, select its pivot columns, and call those vectors a basis for the original column space. In the last example that would select \((1,0,0)^{\top}\) and \((0,1,0)^{\top}\). But neither vector is even in \(\operatorname{Col}\mathbf{A}\), as the coordinate check showed. Those vectors are useful for recognizing the pivot positions in the transformed matrix; they are not substitutes for the original columns.
The correction is to keep track of column indices throughout the row reduction. If the pivots occur in columns \(p_1,\dots,p_r\), return to the original matrix and take \(\mathbf{a}_{p_1},\dots,\mathbf{a}_{p_r}\). The theorem proves that this list is independent and spans \(\operatorname{Col}\mathbf{A}\). In contrast, choosing arbitrary independent columns from the original matrix without checking whether they span may produce only part of the column space. Both the original matrix and the pivot indices are needed: the original entries supply the vectors, and the reduced form identifies which ones to take.
| What row reduction tells you | What it does not tell you |
|---|---|
| Which column indices contain pivots | That the reduced columns equal the original columns |
| Which original columns form a basis for \(\operatorname{Col}\mathbf{A}\) | That \(\operatorname{Col}\mathbf{A}=\operatorname{Col}\mathbf{R}\) |
| That dependencies among columns are preserved | That the column vectors themselves remain unchanged |
Check Your Understanding
For each question, distinguish the pivot index from the column vector in the original matrix.
- For \(\mathbf{A}=\begin{bmatrix}1&2\\3&6\\0&0\end{bmatrix}\), find the pivot index and name the original column to select.
- Explain why \(\mathbf{R}=\mathbf{E}\mathbf{A}\), with \(\mathbf{E}\) invertible, preserves every relation \(\mathbf{A}\mathbf{x}=\mathbf{0}\).
- For \(\mathbf{A}=\begin{bmatrix}1&0\\0&1\\2&1\end{bmatrix}\), row-reduce and determine whether its reduced pivot columns are in \(\operatorname{Col}\mathbf{A}\).
- In the theorem, why does looking at pivot row \(q_k\) force the coefficient \(c_k\) to be zero?
- State precisely which columns should be taken after identifying pivot indices in an echelon form.
