Proof of uniqueness of RREF

Consider a $m\times n$ matrix $A$. Say, through some finite sequence of row operations, we obtain two RREFs of $A$.

$$\begin{array}{rl}{E}_1{E}_2\dots E_{a}A& =R_1\\ E_1^{\prime }{E}_2^{\prime }\dots E_b^{\prime }A& =R_2,\end{array}$$

where $R_1$ and $R_2$ are in reduced row echelon form. Since performing row operations does not change the solution set of a given system, $A\mathbf{x}=0$, $R_1\mathbf{x}=0$ and $R_2\mathbf{x}=0$ must have the SAME solutions. We first consider the case when $R_1$ and $R_2$ have different pivot variables.

Different positions of pivot columns

Let $\mathbf{x}=(x_1,x_2,\dots x_n)$. Let column $p$ be a pivot column in $R_1$, but not a pivot column in $R_2$. In other words, $x_p$ is a fixed variable in $R_1$, and a free variable in $R_2$. Note that free variables can be assigned any value without constraint, while pivot variables are determined (or “fixed”) on fixing the free variables. Particularly, observe that since all entries to the left of a pivot variable are zero, a pivot variable’s value is fixed when we assign values to all the free variables to the right of it.

Observe: If we set all free variables to the right of a pivot variable to 0, the pivot variable is forced to be 0.

Consider the equation $R_2\mathbf{x}=0$. Consider all the free variables $x_i$, $i\ge p$. Since these are free variables, we can set them to be anything we wish. So, set all $x_i$, $i>p$ to be $0$. Notice that by doing so, we also force all pivot variables to the right of $x_p$ to be zero. Set $x_p=\alpha$ for some non zero $\alpha$, which we can do since $x_p$ is a free variable in $R_2$. Thus, we have a solution where $x_p\ne 0$, and $x_i=0\forall i>p$ (the other variables can do whatever; we don’t care). We will show that no solution of this form can satisfy $R_1\mathbf{x}=0$. If all free variables to the right of $x_p$ are set to $0$ (which forces the fixed variables to be zero too), then $x_p$, being a pivot variable in $R_1$, is forced to be zero. Contradiction!

Hence, the positions of pivot columns must be the same.

Different values of cells that appear after a pivot variable in a row

Now that we have established that the positions of the pivot variables are the same in $R_1$ and $R_2$, the only difference than can exist between $R_1$ and $R_2$ is in the values of cells that occur to the right of the pivot in their respective rows, and are not in a pivot column. Such cells are boxed in this example:

$$\left[\begin{array}{cccccc}1& \boxed{2}& 0& \boxed{0}& 0& \boxed{1}\\ 0& 0& 1& \boxed{5}& 0& \boxed{2}\\ 0& 0& 0& 0& 1& \boxed{3}\end{array}\right]$$

Say such a cell, $R_{1_{r,s}}$ is different from $R_{2_{r,s}}$. Let the pivot variable for row $r$ be located in column $p$. In $R_1$, set $x_s$ to be 1, and all the other free variables to the right of the pivot to be 0. This forces $x_p$ to be $-R_{1_{r,s}}$. Do the same in $R_2$, forcing $x_p$ to be $-R_{2_{r,s}}$. Thus, $R_1\mathbf{x}=0$ and $R_2\mathbf{x}=0$ do not have the same solution set. Contradiction.