Finding the Pivots in an Echelon Form
Row reduction organizes a matrix so that its leading entries move to the right as we move down the nonzero rows. Those leading entries mark the pivot positions. Their column indices tell us which columns play a leading role; columns without pivots are the free columns. Keeping track of these indices matters because row operations change the entries of a matrix, but the pivot columns of an echelon form refer back to particular columns of the original matrix.
We use matrices over \(\mathbb{R}\), with columns representing vectors. A list of columns is linearly independent if the only linear combination of them equal to \(\mathbf{0}\) has all coefficients zero. A linear relation among columns is a linear combination equal to \(\mathbf{0}\). These ideas will help explain why pivot indices survive row reduction.
Recall that echelon form has its nonzero rows above any zero rows, and the leading entry of each successive nonzero row lies strictly to the right of the leading entry in the row above. In particular, a zero row has no pivot. A pivot need not equal \(1\), and entries to its right in the same row need not be zero; those extra conditions belong to reduced row echelon form.
When the matrix is a coefficient matrix for variables \(x_1,\dots,x_n\), column \(j\) corresponds to \(x_j\). A pivot in column \(j\) makes \(x_j\) a pivot variable; a column without a pivot makes its variable free. If the matrix is augmented, the final column represents the right-hand side, not a variable. Thus the free-variable terminology applies to nonpivot columns of the coefficient matrix, not to the augmented right-hand-side column.
Reading Pivot Positions and Free Columns
Worked Example: Locate Pivots in an Echelon Matrix
Identify all pivot positions and free columns in the following echelon matrix:
In row 1, the first nonzero entry is \(1\), in column 1, so the first pivot position is \((1,1)\). In row 2, the entries in columns 1 and 2 are zero and the entry in column 3 is \(3\), so the next pivot position is \((2,3)\). In row 3, the first nonzero entry is \(5\), in column 5, giving \((3,5)\). Row 4 is zero and contributes no pivot.
Therefore the pivot columns are columns 1, 3, and 5. The nonpivot columns are columns 2 and 4. If this is a coefficient matrix for \(x_1,\dots,x_5\), then \(x_2\) and \(x_4\) are the free variables. The row leading entries move strictly right, from column 1 to column 3 to column 5, as required for echelon form.
It is important to inspect rows, not to search each column separately for its first nonzero entry. A pivot is the leading entry of a nonzero row. Also, the columns of the echelon matrix are generally not the same vectors as the columns of the original matrix: row operations alter column entries. The column indices, however, can be tracked back. The next result explains why.
To prove this, we will compare the dependence relations among corresponding columns. First, define the rank of a finite list of columns to be the largest number of linearly independent columns that can be selected from that list. For each \(k\), the first \(k\) columns form a prefix of the matrix; the rank of that prefix is the largest number of independent columns among those first \(k\) columns. The rank of the empty prefix is \(0\).
Proof. Let \(\mathbf{A}\) and \(\mathbf{B}\) be row-equivalent matrices with the same number of columns. Each elementary row operation has an inverse row operation. Applying a row operation to a linear combination of columns applies that same operation to the resulting column vector. Consequently, a linear combination of columns of \(\mathbf{A}\) equals \(\mathbf{0}\) if and only if the combination with the same coefficients of corresponding columns of \(\mathbf{B}\) equals \(\mathbf{0}\): one direction follows by applying the row operation, and the other by applying its inverse. The two matrices therefore have exactly the same linear relations among corresponding columns. In particular, for every \(k\), their first \(k\) columns have the same rank, say \(q_k\).
Now consider either matrix in echelon form. Suppose its nonzero rows have leading entries in columns \(p_1,\dots,p_r\), with \(p_1<\cdots<p_r\). For a fixed prefix ending at column \(k\), let \(s\) be the number of these pivot indices that are at most \(k\). The \(s\) pivot columns in that prefix are independent: in a linear relation among them, row \(s\) forces the coefficient of pivot column \(p_s\) to be zero, since entries in that row before its leading entry are zero. Then row \(s-1\) forces the coefficient of pivot column \(p_{s-1}\) to be zero, and continuing upwards forces every coefficient to be zero.
Every other column in the prefix is in the span of those \(s\) pivot columns. Indeed, if column \(j\le k\) is not a pivot column, then entries in rows below row \(s\) are zero: the leading entries of those rows lie to the right of \(j\). In the first \(s\) rows, the \(s\) pivot columns form an upper triangular matrix with nonzero diagonal. The coefficients of a combination of these pivot columns can therefore be chosen to match the first \(s\) entries of column \(j\), solving from the last row upwards. The combination has zero entries below row \(s\), so it equals column \(j\). Thus the prefix rank is exactly \(s\), the number of pivot indices at most \(k\).
It follows that column \(k\) is a pivot column exactly when the rank of the first \(k\) columns is greater than the rank of the first \(k-1\) columns: the count increases by one at a pivot and does not increase otherwise. Since these prefix ranks agree for \(\mathbf{A}\) and \(\mathbf{B}\) for every \(k\), the pivot-column indices agree. \(\square\)
This argument gives a precise way to track pivots across row reduction: look at each column index in the echelon form, and record whether the prefix rank increases there. It is not enough simply to compare whether entire prefixes are independent. A prefix may be dependent both before and after a new pivot appears; the amount of independent information in the prefix is what detects the increase.
Tracking Pivot Columns Back to the Original Matrix
Worked Example: Find the Pivot Columns of the Original Matrix
Reduce the matrix to echelon form, then identify the pivot columns of the original matrix:
Use \(R_2\to R_2-2R_1\) and \(R_3\to R_3-R_1\). The resulting rows are \((0,0,1,1)\) and \((0,0,1,1)\):
Now apply \(R_3\to R_3-R_2\):
The leading entries are in positions \((1,1)\) and \((2,3)\). Thus the pivot-column indices are 1 and 3, and columns 2 and 4 are nonpivot columns. By the theorem, columns 1 and 3 are also the pivot-column indices of the original matrix \(\mathbf{A}\); the entries in those original columns need not match the entries in the echelon matrix.
Check: In the original matrix, column 2 is twice column 1, and column 4 is the sum of columns 1 and 3: \(\mathbf{a}_2=2\mathbf{a}_1\) and \(\mathbf{a}_4=\mathbf{a}_1+\mathbf{a}_3\). Directly, \(\mathbf{a}_1=(1,2,1)^\top\), \(\mathbf{a}_2=(2,4,2)^\top\), \(\mathbf{a}_3=(0,1,1)^\top\), and \(\mathbf{a}_4=(1,3,2)^\top\), so both equalities hold entry by entry. The pivot columns are consistent with these relations: columns 2 and 4 add no new independent column to the first three columns.
The pivot columns of the original matrix are determined by their indices in an echelon form, not by treating the transformed columns as if they were unchanged. Row operations preserve all linear relations among corresponding columns, but they do change the column vectors themselves. This distinction lets us use the echelon form to identify which original columns to select without confusing the two matrices.
Worked Example: Compare Two Echelon Forms
Consider the matrix
Apply \(R_2\to R_2-2R_1\), giving
The pivot positions of \(\mathbf{E}\) are \((1,2)\), \((2,3)\), and \((3,4)\). Thus columns 2, 3, and 4 are pivot columns; column 1 is free. To see the same indices in a different echelon form, scale row 3 by \(\tfrac13\), then apply \(R_2\to R_2-R_3\):
The leading entries of \(\mathbf{F}\) are again in columns 2, 3, and 4. The matrices \(\mathbf{E}\) and \(\mathbf{F}\) have different entries but the same pivot-column indices, as the theorem requires. Column 1 of \(\mathbf{A}\) is the zero column, so it is dependent on the other columns and cannot be a pivot column.
Check: Each step is reversible: the first reduction is undone by \(R_2\to R_2+2R_1\); scaling row 3 by \(\tfrac13\) is undone by scaling it by \(3\); and \(R_2\to R_2-R_3\) is undone by \(R_2\to R_2+R_3\). Thus the displayed matrices are row-equivalent, and the pivot indices read from both echelon forms agree.
A Common Mistake: Looking Down Columns for Pivots
A common incorrect procedure is to choose the first nonzero entry in each column and call it a pivot. For example, consider this echelon matrix:
Looking down column 2 gives the entry \(2\) in row 1, and looking down column 3 gives the entry \(1\) in row 1. The mistaken conclusion would be that there are two pivots in row 1. But a pivot is the leading entry of a row: row 1 has leading entry \(2\) in column 2, while row 2 has leading entry \(3\) in column 3. The actual pivot positions are \((1,2)\) and \((2,3)\), and column 1 is free.
Another error is to call a column free merely because it has no leading entry in the original matrix before reduction. Pivot positions are read from an echelon form. Once they are identified there, their column indices determine the pivot columns of the original matrix. Conversely, row-reducing the original matrix does not mean that the entries in its pivot columns stay fixed.
For a coefficient matrix, the practical process is to locate each row's leading entry from top to bottom, record its column, and then mark every remaining coefficient column as free. Use the resulting column indices—not the altered entries in the echelon matrix—to refer to columns of the original matrix.
Check Your Understanding
For each question, identify the relevant leading entries or column indices and explain your conclusion.
- In an echelon matrix with leading entries in positions \((1,2)\), \((2,4)\), and \((3,6)\), which columns are pivot columns and which columns are free?
- Can a pivot entry be a number other than \(1\)? State what feature of a row determines its pivot.
- Why do row-equivalent matrices have the same linear relations among corresponding columns?
- Explain why the prefix ranks determine the pivot-column indices, even when a prefix is dependent both before and after a pivot column is added.
- If the coefficient matrix has a pivot in every variable column, are there any free variables? Explain using the definition of a free column.
