3 Matrices 3.9 Row reduced echelon form 3.11 Solving RREF systems

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.