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.

By Theorem 3.8.3, there is an invertible matrix $E$ such that

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

and so (because matrix multiplication works columnwise, Theorem 3.2.3) $EA=A^{\prime}$ and $E\mathbf{b}=\mathbf{b}^{\prime}$ .

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}$ . Conversely 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. The simple form we will use is called row reduced echelon form. To define it we need the notion of a leading entry.

Definition 3.9.1.

The leading entry in a nonzero 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, violating condition 2
•

$\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 which breaks condition 1.
•

$\begin{pmatrix}0&1\\ 1&0\end{pmatrix}$ isn’t in RREF because of condition 4: 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 (as required by condition 3) unless $\beta=0$ .
•

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