Uniqueness of Reduced Row Echelon Form

Why a Reduced Form Is Unique

Row reduction can follow different paths. One calculation might scale a row before eliminating an entry, while another eliminates first and scales later. The intermediate matrices can differ, but if the starting matrices are row-equivalent, the final reduced row echelon form is always the same. This is a uniqueness claim: it says that there cannot be two different reduced forms at the end of valid row operations.

We will establish that claim using the homogeneous solution set alone. The key idea is that a reduced form records enough information to determine which vectors solve its homogeneous system. We then prove, by induction on the number of columns, that two matrices in reduced row echelon form with the same homogeneous solution set must be identical. Throughout, matrices and scalars are over \(\mathbb{R}\).

For a matrix \(\mathbf{A}\) with \(n\) columns, its homogeneous solution set is \(\{\mathbf{x}\in\mathbb{R}^n:\mathbf{A}\mathbf{x}=\mathbf{0}\}\). An elementary row operation does not change this set. Swapping two rows only reorders equations; multiplying a row by a nonzero scalar preserves exactly the same equation; and replacing one row by itself plus a multiple of another preserves the solutions because the operation can be reversed by subtracting that multiple. Consequently, row-equivalent matrices have the same homogeneous solution set.

The Induction Principle Behind Uniqueness

We prove a slightly focused statement: among matrices of the same size that are already in reduced row echelon form, the homogeneous solution set determines the matrix. The number of rows can be any nonnegative integer, so the argument also covers the smaller matrices that arise during induction.

Proof. We use induction on \(n\). If \(n=0\), a matrix with zero columns has no entries, so there is only one such matrix for a given number of rows. Therefore \(\mathbf{R}=\mathbf{S}\).

Now let \(n\geq 1\), and assume the statement holds for matrices with \(n-1\) columns. Let \(\mathbf{R}\) and \(\mathbf{S}\) satisfy the theorem’s hypotheses. Write \(\mathbf{e}_1=(1,0,\dots,0)^\top\in\mathbb{R}^n\). The first column of a reduced row echelon matrix is either zero or is its first pivot column. In the latter case, that column has a \(1\) in its pivot row and zeros in every other row. Thus \(\mathbf{e}_1\) belongs to the homogeneous solution set exactly when the first column is zero. Since the two solution sets are equal, the first columns of \(\mathbf{R}\) and \(\mathbf{S}\) are either both zero or both pivot columns.

First suppose both first columns are zero. Delete the first column from each matrix, obtaining \(\mathbf{R}'\) and \(\mathbf{S}'\). These are still in reduced row echelon form. For every \(\mathbf{y}\in\mathbb{R}^{n-1}\), the vector \((0,\mathbf{y})^\top\) solves the homogeneous system for \(\mathbf{R}\) exactly when \(\mathbf{y}\) solves the system for \(\mathbf{R}'\); the same statement holds for \(\mathbf{S}\) and \(\mathbf{S}'\). The original solution sets are equal, so the solution sets for \(\mathbf{R}'\) and \(\mathbf{S}'\) are equal. The induction hypothesis gives \(\mathbf{R}'=\mathbf{S}'\). Putting back their identical zero first columns gives \(\mathbf{R}=\mathbf{S}\).

Now suppose the first column is a pivot column in both matrices. In reduced row echelon form it is the first row’s pivot column, so write the matrices in block form as

Here \(\mathbf{a}\) and \(\mathbf{d}\) are rows with \(n-1\) entries, and \(\mathbf{B}\) and \(\mathbf{C}\) have \(n-1\) columns. The lower blocks are in reduced row echelon form. A vector \((x_1,\mathbf{y})^\top\) solves the system for \(\mathbf{R}\) precisely when \(\mathbf{B}\mathbf{y}=\mathbf{0}\) and \(x_1=-\mathbf{a}\mathbf{y}\). Therefore the set of all possible tails \(\mathbf{y}\) of solutions is exactly the homogeneous solution set for \(\mathbf{B}\). The same reasoning shows that the possible tails for \(\mathbf{S}\) are the solutions for \(\mathbf{C}\). Equality of the full solution sets implies equality of these sets of tails. By the induction hypothesis, \(\mathbf{B}=\mathbf{C}\).

It remains to show \(\mathbf{a}=\mathbf{d}\). For every \(\mathbf{y}\) solving \(\mathbf{B}\mathbf{y}=\mathbf{0}\), the full solution sets agree, so the first coordinate of the solution with tail \(\mathbf{y}\) agrees in both systems. The first coordinate is unique in each system, as the first equation gives \(x_1=-\mathbf{a}\mathbf{y}\) or \(x_1=-\mathbf{d}\mathbf{y}\). Hence \((\mathbf{a}-\mathbf{d})\mathbf{y}=0\) for every such \(\mathbf{y}\).

In columns of \(\mathbf{B}\) that contain pivots, both \(\mathbf{a}\) and \(\mathbf{d}\) have zero entries: these columns are pivot columns of the full matrices too, and their pivots must be the only nonzero entries in their columns. For any column \(k\) of \(\mathbf{B}\) without a pivot, set its free variable to \(1\) and all other free variables to \(0\). In the homogeneous system for \(\mathbf{B}\), each pivot variable is then determined by its pivot equation. This produces a solution \(\mathbf{y}\) whose free coordinates are zero except for \(y_k=1\). Since \((\mathbf{a}-\mathbf{d})\mathbf{y}=0\), and the entries of \(\mathbf{a}-\mathbf{d}\) in pivot columns are zero, it follows that \(a_k-d_k=0\). This holds for every nonpivot column; the entries in pivot columns already agree because they are both zero. Thus \(\mathbf{a}=\mathbf{d}\), and consequently \(\mathbf{R}=\mathbf{S}\). The induction is complete. \(\square\)

Using the Result for Row-Equivalent Matrices

The theorem compares matrices already in reduced row echelon form. To apply it to row-equivalent matrices, let \(\mathbf{A}\) and \(\mathbf{D}\) be row-equivalent, and let \(\mathbf{R}\) and \(\mathbf{S}\) be their respective reduced row echelon forms. Elementary row operations preserve homogeneous solution sets, so \(\mathbf{R}\) has the same solution set as \(\mathbf{A}\), and \(\mathbf{S}\) has the same solution set as \(\mathbf{D}\). Since \(\mathbf{A}\) and \(\mathbf{D}\) are row-equivalent, those two sets are equal. The theorem therefore gives \(\mathbf{R}=\mathbf{S}\). This establishes uniqueness without needing to compare the sequences of row operations used to reach the forms.

Common Mistake: Confusing Echelon Form with Reduced Echelon Form

A tempting but incorrect counterexample to uniqueness is to call both \(\begin{bmatrix}1&2\\0&1\end{bmatrix}\) and \(\begin{bmatrix}1&0\\0&1\end{bmatrix}\) reduced row echelon forms. They are different, and they are row-equivalent, so this might seem to contradict the theorem. The error is that the first matrix is not in reduced row echelon form: its second column has a pivot in row 2 but also has the nonzero entry \(2\) above that pivot.

Correctly reduce the first matrix by replacing row 1 with row 1 minus twice row 2:

Both systems have only the zero solution: the second equation gives \(x_2=0\), and then the first gives \(x_1=0\). The correct conclusion is not that there are two reduced forms, but that the first matrix was not reduced. Uniqueness applies only after all the defining conditions of reduced row echelon form have been checked.

The proof also shows why the homogeneous solution set is enough. If the first column is zero, deleting it leaves a smaller reduced-form problem with the same solution data. If the first column is a pivot, the remaining equations determine the possible tails of solutions, while the first equation determines their first coordinates. Induction identifies the lower rows, and the possible tails then identify the first row. No choice of row-operation path can change that data.