# 3.10 RREF existence and uniqueness

## 3.10.1 Existence and uniqueness

Here are two facts about row reduced echelon form.

###### Theorem 3.10.1.

For every matrix $A$, there is a sequence of row operations taking $A$ to a matrix in row reduced echelon form.

###### Proof.

We prove this by induction on the number of columns of $A$. When $A$ has one column, either $A$ is the zero vector (in which case it is in RREF) or it has a nonzero entry $a$. Swap $a$ to the top row, multiply the top row by $1/a$, and subtract multiples of the top row from the other rows to make all other rows 0. The result is the vector $\begin{pmatrix}1\\ 0\\ \vdots\\ 0\end{pmatrix}$ which is in RREF.

For the inductive step, suppose that $A$ is $m\times n$ and that the result is true for all matrices with $n-1$ columns. We then know that there is a series of row operations we can do to $A$ that result in a matrix $X$ whose first $n-1$ columns form a RREF matrix. Suppose the matrix formed by these $n-1$ columns has $k$ rows of zeroes at the bottom. If the final column has zeroes in its bottom $k$ entries, the matrix is in RREF. If not, swap a nonzero entry to the top of these $k$ rows, subtract multiples of this row from the others to eliminate all other nonzero entries in the final column, and multiply by a scalar so that its entry is 1. The result is in RREF. ∎

###### Theorem 3.10.2.

Let $A$ be a matrix. If $R$ and $S$ are RREF matrices that can be obtained by doing row operations to $A$, then $R=S$.

This theorem says that there is only one RREF matrix which can be obtained by doing row operations to $A$, so we are justified in calling the unique RREF matrix reachable from $A$ the row reduced echelon form of $A$.

###### Proof.

Again, the proof is by induction on the number $n$ of columns of $A$. The base case is when $A$ is an $m\times 1$ column vector. There are only two RREF height $m$ column vectors: the zero vector $\mathbf{0}_{m}$ and a vector $\mathbf{v}$ with a 1 at the top and 0s everywhere else. If there are sequences of row operations taking $A$ to $\mathbf{v}$ and also to $\mathbf{0}_{m}$ then there is a sequence of row operations taking $\mathbf{0}_{m}$ to $\mathbf{v}$. This is impossible because any row operation sends $\mathbf{0}_{m}$ to $\mathbf{0}_{m}$.

For the inductive step, suppose that $A$ is $m\times n$ and that $R$ and $S$ are RREF matrices reachable from $A$. Let $A^{\prime}$, $R^{\prime}$, and $S^{\prime}$ be the matrices formed by the first $n-1$ columns of $A$, $R$, and $S$ respectively. The matrices $R^{\prime}$ and $S^{\prime}$ are RREF matrices formed by doing row operations to $A^{\prime}$, so by induction they are equal. Suppose for a contradiction that $R\neq S$, so that there is some $j$ such that the $j$th entry $r_{jn}$ in the last column of $R$ which differs from the corresponding entry $s_{jn}$ of $S$.

Theorem 3.9.1 tells us that the equations $A\mathbf{x}=\mathbf{0}$, $R\mathbf{x}=\mathbf{0}$, and $S\mathbf{x}=\mathbf{0}$ all have exactly the same solutions.

Let $\mathbf{u}$ be any solution of $A\mathbf{x}=\mathbf{0}$. We have $R\mathbf{u}=S\mathbf{u}=\mathbf{0}$, so $(R-S)\mathbf{u}=\mathbf{0}$. Since the first $n-1$ columns of $R-S$ are all zeroes, we get $(r_{jn}-s_{jn})u_{n}=0$, so $u_{n}=0$. In other words, every solution of $A\mathbf{x}=\mathbf{0}$ has last entry zero.

The RREF matrix $R^{\prime}$ has some nonzero rows and then some zero rows. Suppose there are $k$ zero rows. We can then write $R^{\prime}$ like this

 $\begin{pmatrix}X\\ \mathbf{0}_{k\times(n-1)}\end{pmatrix}$

where $X$ has no zero rows. Then $R$ and $S$ have the form

 $R=\begin{pmatrix}X&\mathbf{r}\\ \mathbf{0}_{k\times(n-1)}&\mathbf{t}\end{pmatrix},S=\begin{pmatrix}X&\mathbf{s% }\\ \mathbf{0}_{k\times(n-1)}&\mathbf{u}\end{pmatrix}$

I claim that $\mathbf{t}\neq\mathbf{0}$. Suppose for a contradiction that $\mathbf{t}=\mathbf{0}$. The first $m-k$ rows of $R$ all have leading entries. For $1\leqslant i\leqslant m-k$, let the leading entry in row $i$ of $R$ occur in column number $c_{i}$. Let $\mathbf{r}$ have entries $r_{1},\ldots,r_{m-k}$, where $m$ is the number of rows of $A$. Notice that column $c_{i}$ of $R$ has a 1 in position $i$ and zeroes everywhere else, so if we add up $r_{1}$ times column $c_{1}$, $r_{2}$ times column $c_{2}$, and so on, up to $r_{m-k}$ times column $c_{m-k}$ we get the vector

 $\begin{pmatrix}r_{1}\\ \vdots\\ r_{m-k}\\ 0\\ \vdots\\ 0\end{pmatrix}$

which is the last column of $R$. It follows that the vector with $-1$ in position $n$, with $r_{i}$ in position $c_{i}$ for $1\leqslant i\leqslant m-k$, and with zeroes elsewhere is a solution to $R\mathbf{x}=\mathbf{0}$. This contradicts every solution to $A\mathbf{x}=\mathbf{0}$ having last entry zero.

Since $R$ is in RREF, $\mathbf{t}$ must have a $1$ at the top and all other entries zero, and $\mathbf{r}=\mathbf{0}$. The same argument applies to $S$, so $\mathbf{u}=\mathbf{t}$ and $\mathbf{s}=\mathbf{0}$. This shows $R=S$. ∎

## 3.10.2 Example of putting a matrix into RREF

Let $A=\begin{pmatrix}1&2&3\\ 4&5&6\\ 7&8&9\end{pmatrix}$. We want to do a sequence of row operations to $A$ which ends up with a matrix in RREF. Row 1 has a leading entry at position $1,1$, but the other entries in column 1 aren’t 0. We use the $1,1$ entry as a pivot to eliminate the other entries in column 1. That is, we apply row operations of the form $\textbf{r}_{j}\mapsto\textbf{r}_{j}+\lambda\textbf{r}_{1}$ to make the other entries in column 1 equal to 0.

 $A\xmapsto{\textbf{r}_{2}\mapsto\textbf{r}_{2}-4\textbf{r}_{1}}\begin{pmatrix}1% &2&3\\ 0&-3&-6\\ 7&8&9\end{pmatrix}\xmapsto{\textbf{r}_{3}\mapsto\textbf{r}_{3}-7\textbf{r}_{1}% }\begin{pmatrix}1&2&3\\ 0&-3&-6\\ 0&-6&-12\end{pmatrix}$

This matrix isn’t in RREF. One reason is that the leading entry in row 2, in position $2,2$, isn’t equal to 1. To make that leading entry 1 we can use the row operation that multiplies row 2 by $-1/3$:

 $\begin{pmatrix}1&2&3\\ 0&-3&-6\\ 0&-6&-12\end{pmatrix}\xmapsto{\textbf{r}_{2}\mapsto(-1/3)\textbf{r}_{2}}\begin% {pmatrix}1&2&3\\ 0&1&2\\ 0&-6&-12\end{pmatrix}$

Now we have a leading entry in row 2, column 2 which is equal to 1, but there are other nonzero entries in that column. We use the $2,2$ entry as the next pivot to eliminate entries in column 2.

 $\displaystyle\begin{pmatrix}1&2&3\\ 0&1&2\\ 0&-6&-12\end{pmatrix}\xmapsto{\textbf{r}_{1}\mapsto\textbf{r}_{1}-2\textbf{r}_% {2}}\begin{pmatrix}1&0&-1\\ 0&1&2\\ 0&-6&-12\end{pmatrix}$ $\displaystyle\xmapsto{\textbf{r}_{3}\mapsto\textbf{r}_{3}+6\textbf{r}_{2}}% \begin{pmatrix}1&0&-1\\ 0&1&2\\ 0&0&0\end{pmatrix}$

This matrix is in RREF, so we are done.