3 Matrices 3.8 Elementary matrices 3.10 RREF existence and uniqueness

3.9 Row reduced echelon form

3.9.1 Row operations don’t change the solutions to a matrix equation

Our informal method of solving linear systems is to do certain manipulations to the equations until they are in a form where the solutions are easy to read off. This method only works if the manipulations we do don’t change the set of solutions.

When we introduced row operations, it was because their effect on the augmented matrix of a linear system corresponded to the kind of manipulations we perform when solving such a linear system. We’re now going to prove that these row operations don’t change the set of solutions.

Theorem 3.9.1.

Suppose that $(A^{\prime}\mid\mathbf{b}^{\prime})$ results from $(A\mid\mathbf{b})$ by doing a sequence of row operations. Then the matrix equations $A\mathbf{x}=\mathbf{b}$ and $A^{\prime}\mathbf{x}=\mathbf{b}^{\prime}$ have the same solutions.

Proof.

If the elementary matrices corresponding to these row operations are $E_{1},\ldots,E_{k}$ then letting $E=E_{k}\cdots E_{1}$ we have

E(A\mid\mathbf{b})=(A^{\prime}\mid\mathbf{b}^{\prime})

and so (because matrix multiplication works columnwise) $EA=A^{\prime}$ and $E\mathbf{b}=\mathbf{b}^{\prime}$ . Note that $E$ is a product of invertible matrices, so by Theorem 3.5.3 is itself invertible.

We must show that a column vector $\mathbf{v}$ is a solution of $A\mathbf{x}=\mathbf{b}$ if and only if it is a solution of $A^{\prime}\mathbf{x}=\mathbf{b}^{\prime}$ . If $A\mathbf{v}=\mathbf{b}$ then multiplying on the left by $E$ gives $EA\mathbf{v}=E\mathbf{b}$ , that is, $A^{\prime}\mathbf{v}=\mathbf{b}^{\prime}$ . If $A^{\prime}\mathbf{v}=\mathbf{b}^{\prime}$ then $EA\mathbf{v}=E\mathbf{b}$ , so multiplying on the left by $E^{-1}$ gives $A\mathbf{v}=\mathbf{b}$ . ∎

3.9.2 Row reduced echelon form

We talked about manipulating equations into a simple form where the solutions could be easily read off. One possible “simple form” is called row reduced echelon form. To define that we need the notion of a leading entry.

Definition 3.9.1.

The leading entry in a row of a matrix is the first non-zero entry in that row, starting from the left.

Of course, if a row is all zeroes then it doesn’t have a leading entry. In the matrix $\begin{pmatrix}0&2\\ 0&0\end{pmatrix}$ the leading entry in the first row is the 2 in position $1,2$ while the second row has no leading entry.

Definition 3.9.2.

A matrix is in row reduced echelon form (RREF) if

1.

all leading entries are 1,
2.

any rows which are all zero are below any rows which are not all zero,
3.

all entries in the same column as a leading entry are zero, and
4.

for every $i$ , if row $i$ and $i+1$ have a leading entry then the leading entry in row $i+1$ is to the right of that in row $i$ .

Example 3.9.1.

•

$\begin{pmatrix}0&0\\ 1&0\end{pmatrix}$ isn’t in RREF: the zero row is at the top.
•

$\begin{pmatrix}2&0\\ 0&0\end{pmatrix}$ isn’t in RREF: there is a row in which the left-most non-zero entry is not 1.
•

$\begin{pmatrix}0&1\\ 1&0\end{pmatrix}$ isn’t in RREF: the left-most 1 in row 2 is not to the right of the left-most 1 in the row above it.
•

$\begin{pmatrix}1&\alpha&\beta&3\\ 0&0&1&-2\end{pmatrix}$ is in RREF if and only if $\beta=0$ : the left-most 1 in row 2 is in column 3, but it is not the only non-zero entry in column 3 unless $\beta=0$ .
•

$\begin{pmatrix}1&0&0&3\\ 0&0&1&0\\ 0&0&0&0\end{pmatrix}$ is in RREF.