Gauss-Jordan Elimination

From Echelon Form to Reduced Echelon Form

Forward elimination creates an echelon form by finding pivots and clearing entries below them. That form is enough for back substitution, but Gauss-Jordan elimination continues: each pivot is made equal to \(1\), and every other entry in its column—including entries above the pivot—is made \(0\). The result is reduced row echelon form (RREF), where the pivot columns are as simple as possible.

We work with augmented matrices for linear systems over \(\mathbb{R}\). Each row operation is applied to the entire row, including the augmented column. This matters because changing only the coefficient entries but not the right-hand side would change the system. As established in the earlier material on row operations, each elementary row operation preserves the solution set of a system.

For a system with \(n\) variables, its augmented matrix has \(n+1\) columns. In Gauss-Jordan elimination, the last column is part of the matrix being reduced. Therefore, if the coefficient columns have no available pivot but the augmented column still has a nonzero entry, that column can also have a pivot in the RREF of the full augmented matrix.

The Gauss-Jordan Procedure

The procedure builds pivot rows from top to bottom. In each step, it searches the remaining rows for a nonzero entry in the current column. If one exists, that entry is moved into the next pivot row, scaled to \(1\), and used to clear the rest of its column. If there is no such entry, the procedure moves to the next column. The choice among available nonzero entries is not important for correctness; the next tutorial studies pivot choices in more detail.

In an operation such as \(R_2\to R_2-3R_1\), the entire second row is replaced, not only the entry being cleared. Writing the intermediate matrices is a useful safeguard: it makes each arithmetic change visible and helps catch sign errors before they spread to later steps.

Proof. A row swap \(R_i\leftrightarrow R_j\) is undone by swapping the same rows again. Multiplying a row by a nonzero scalar \(c\) is undone by multiplying it by \(1/c\). Replacing \(R_i\) by \(R_i+cR_j\), with \(i\ne j\), is undone by replacing the new \(R_i\) by \(R_i-cR_j\), since row \(R_j\) was not changed. Thus each operation is reversible, and reversing a finite sequence in reverse order undoes the whole sequence. By the definition of row equivalence, the original and resulting matrices are row-equivalent. \(\square\)

Why the Procedure Produces RREF

Proof. Let the matrix have \(m\) rows and \(q\) columns. Each successful pivot step uses one row and one column, and the next pivot is sought in a row below the previous pivot row and in a column to its right. There can be at most \(\min(m,q)\) successful steps. Every unsuccessful search advances to a new column, and there are only \(q\) columns. Therefore the process terminates.

Each step is an elementary row operation, so the resulting matrix is row-equivalent to the initial matrix by the proposition. For an augmented matrix, the earlier result on why row operations preserve solutions applies to every step; hence the solution set is unchanged.

It remains to check the form of the result. Every pivot is scaled to \(1\). The procedure clears all other entries in its column, above as well as below. Later pivot rows lie below earlier ones and have zeros in earlier pivot columns: those entries were already cleared when the earlier pivots were processed. Swapping rows while searching for a later pivot only swaps rows below the previous pivot row, so it does not disturb the earlier pivot rows. Each new pivot is in a column to the right of the preceding pivot. Finally, if any rows remain after all columns have been inspected, those rows have no nonzero entry in any column, so they are zero rows at the bottom. These are precisely the conditions for RREF. \(\square\)

Worked Reductions of Augmented Matrices

Common Mistakes and Checks

Clearing only below a pivot is not Gauss-Jordan elimination. For instance, after reaching \(\begin{bmatrix}1&-1&1\\0&1&1\end{bmatrix}\) in the first example, stopping there leaves a nonzero entry above the second pivot. Calling that matrix RREF is incorrect. The correction is \(R_1\to R_1+R_2\), which produces \(\begin{bmatrix}1&0&2\\0&1&1\end{bmatrix}\).

Do not scale just the pivot entry. A row represents an equation, so scaling a pivot to \(1\) means scaling every entry in its row. In the second example, changing the \(3\) in the second row to \(1\) while leaving the augmented entry \(2\) unchanged would incorrectly produce \([0\ 0\ 1\mid2]\). The valid operation \(R_2\to\frac13R_2\) gives \([0\ 0\ 1\mid\frac23]\).

For a final check, inspect each pivot column: its pivot must be \(1\), and every other entry in that column must be \(0\). Also check that pivots move to the right as the rows move down, and that zero rows, if present, are at the bottom. If the matrix is augmented, every operation must have been applied to the right-hand-side column too.