What Elimination Must Accomplish
Row reduction is a sequence of choices: inspect columns from left to right, find a usable nonzero entry, move it into position as a pivot, and clear the entries below it. Some columns may contain no usable entry at all, and some rows may be zero. The central question is therefore not just how to carry out a typical elimination step, but why this process cannot continue indefinitely or get stuck before producing the intended shape.
Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), where \(m\) and \(n\) are finite. A leading entry of a nonzero row is its first nonzero entry, reading from left to right. A zero row has every entry equal to zero. An entry selected as a pivot is nonzero; it need not be scaled to \(1\).
The definition concerns the positions of leading entries, not whether those entries equal \(1\), and not whether entries above them are zero. The elimination procedure in this tutorial clears entries below each pivot. It does not need to clear entries above pivots to establish row echelon form.
The Pivot-Selection Procedure
Keep track of the first row not yet assigned a pivot, called the active row, and the next column to inspect. Initially these are row \(1\) and column \(1\). In the current column, search the active row and all rows below it. If every entry there is zero, the column cannot supply a pivot at this stage, so move to the next column. If some entry is nonzero, swap its row with the active row, use the resulting entry as a pivot, and clear every entry beneath it by row operations. Then move down one row and forward to the next column.
Inspect entries in the active row and the rows below it. If all are zero, skip that column; do not stop the whole procedure.
If an inspected entry is nonzero, swap its row into the active row. The pivot is the first nonzero entry of this row among the columns not yet passed.
For each row below the pivot, subtract the appropriate multiple of the pivot row to make the entry in the pivot column zero. Move to the next active row and the next column.
For instance, if the pivot is \(a_{rj}\ne0\) and the entry below it in row \(i\) is \(a_{ij}\), the clearing operation is \(R_i\to R_i-\frac{a_{ij}}{a_{rj}}R_r\). The new entry in column \(j\) is \(a_{ij}-\frac{a_{ij}}{a_{rj}}a_{rj}=0\). The operation is permitted because the pivot is nonzero, so the quotient is defined.
Worked Examples of the Procedure
Worked Example: A Zero Column Before the First Pivot
Apply elimination to the following matrix. Its first column is zero, so the first pivot cannot be in that column.
Skip column 1. In column 2, the first available entry is \(2\), in row 1, so it is the pivot. Clear the entry \(4\) below it with \(R_2\to R_2-2R_1\):
The arithmetic in the changed row is \((0,4,3,7)-2(0,2,1,3)=(0,0,1,1)\). The leading entries are \(2\) in column 2 and \(1\) in column 3, in that order; the zero row is last. Thus the result is in echelon form. The first column being zero did not prevent a pivot in a later column.
Worked Example: Moving a Nonzero Row Above a Zero Row
Here a zero row lies above a row that can provide the first pivot:
Column 1 has no nonzero entry. In column 2, the first nonzero entry among the active rows is \(3\) in row 3. Swap rows 1 and 3 to place it in the active row:
There are no entries to clear beneath the pivot in column 2. Move to row 2 and column 3: the entry \(2\) is a pivot, with zero beneath it. The resulting matrix has leading entries in columns 2 and 3, followed by a zero row. The swap moved the zero row below the nonzero rows, and the later pivot lies to the right of the first.
Check: the row swap has only exchanged rows, and no entries beneath either pivot need changing. The displayed result therefore satisfies both echelon conditions.
Worked Example: Clearing Two Entries Below a Pivot
Consider a matrix with two initial zero columns and a nonzero third column:
Columns 1 and 2 have no available nonzero entries, so both are skipped. The first pivot is \(2\) in row 1, column 3. Clear the entries beneath it using \(R_2\to R_2-2R_1\) and \(R_3\to R_3-3R_1\):
The changed rows are \((0,0,4)-2(0,0,2)=(0,0,0)\) and \((0,0,6)-3(0,0,2)=(0,0,0)\). There is one leading entry, in column 3, and the two zero rows are below it. This matrix is in echelon form even though its pivot is not in the first column.
Why the Procedure Terminates in Echelon Form
Proof. We justify both progress and the shape of the final matrix. At any stage, let \(r\) be the active row and \(j\) the next column to inspect. The key invariant is that every active row has zero entries in all columns before \(j\). Initially there are no columns before \(j=1\), so the invariant holds.
If all entries in column \(j\) from row \(r\) downward are zero, skipping the column preserves the invariant: the active rows are now zero in every column before \(j+1\). If a nonzero entry is found in one of those rows, swap its row with row \(r\). The swap leaves the active rows zero in all columns before \(j\). The new active row therefore has its first nonzero entry at column \(j\): all earlier entries are zero by the invariant, and its entry in column \(j\) is the selected nonzero pivot.
Now clear below that pivot. Each row below it has zero entries before column \(j\), and the pivot row also has zero entries there. Subtracting a multiple of the pivot row therefore keeps those earlier entries zero. The selected entry in column \(j\) becomes zero in every row below the pivot by the clearing calculation. After advancing to row \(r+1\) and column \(j+1\), every active row is zero in all columns before the new column. Thus the invariant is preserved at every step.
Each iteration advances the column by at least one: a skipped column advances it by one, and a pivot step advances it by one after clearing. There are only \(n\) columns. Consequently the procedure cannot take infinitely many iterations; it stops when the next column exceeds \(n\), or when the active row exceeds \(m\). If the columns are exhausted while active rows remain, the invariant says those rows are zero in every column, so they are zero rows. If the rows are exhausted, there are no rows left to process.
It remains to verify the echelon conditions. Every pivot row has leading entry in its selected column, as shown by the invariant. Pivot columns increase strictly: after a pivot in column \(j\), the next column inspected is \(j+1\), and skipped columns also move only to the right. Therefore the leading entries of successive nonzero rows move strictly to the right. Entries below a pivot were cleared, and any rows left after the last pivot are zero. Hence zero rows lie below the nonzero pivot rows, and the output is in row echelon form. If there are no pivots, all entries are zero by the same stopping argument, so the conclusion still holds. \(\square\)
What the Proof Says About Zero Cases
The theorem does not require that a pivot exist in every column or that a nonzero entry exist in every row. A column is skipped precisely when all entries in the active part of that column are zero. A zero row may stay among the active rows for a time, but if a later row supplies a pivot, a swap moves that nonzero row into the active position. If no later row supplies a pivot, the remaining rows are zero and belong at the bottom of the finished matrix.
The extreme cases fit the same logic. If \(\mathbf{A}\) is an all-zero matrix, every column is skipped and no pivot is selected; all rows are already zero, so the matrix is in echelon form. If \(m=0\), there are no rows to process. If \(n=0\), each row has no entries and is a zero row, so there are no pivots and the echelon conditions hold. In each case, the conclusion follows from the finite procedure, not from an assumption that some pivot must be found.
Common Mistake: Stopping at a Zero Column
A common error is to treat a column with no available pivot as the end of elimination. For example, a student might look at the first column of the following matrix, find only zeros, and incorrectly conclude that no pivot can be selected:
The first column is skipped, not the whole procedure. Column 2 has a nonzero entry in the active row, so use \(1\) as the pivot and clear the \(2\) beneath it:
The calculation \((0,2)-2(0,1)=(0,0)\) verifies the clearing step. The final matrix has its only leading entry in column 2 and its zero row below it. The correction is to distinguish “this column has no pivot” from “there are no pivots anywhere”: the search continues in later columns.
Keeping that distinction makes the algorithm reliable for rectangular matrices as well as matrices with many zero entries. The process has a built-in stopping measure—the column index continually advances—and a built-in shape check: every new pivot is to the right of the previous one, with entries below it cleared. These facts explain why elimination reaches echelon form for every finite matrix, including the cases in which some of its rows or columns contribute no pivots.
Check Your Understanding
Use the pivot search and the echelon definition to answer each question.
- What should the algorithm do if all entries in the active part of its current column are zero?
- Why is a row swap sometimes needed before clearing below a pivot?
- For \(\begin{bmatrix}0&0&3\\0&0&6\\0&0&0\end{bmatrix}\), identify the pivot position and describe the row operation that clears the entry beneath it.
- Explain why each pivot lies strictly to the right of the pivot in the row above.
- What does the algorithm conclude if it reaches the last column while active rows remain?
