# The Unapologetic Mathematician

## Reduced Row Echelon Form

Let’s take row echelon form and push it a little further into a form that is unique: reduced row echelon form.

When we were doing Gaussian elimination we saved some steps by leaving pivoted rows alone. This was fine for the purposes of solving equations, where the point is just to eliminate progressively more and more variables in each equation. We also saved steps by leaving the pivots as whatever values they started with. Both of these led to a lot of variation in the possibilities for row echelon forms. We’ll tweak the method of Gaussian elimination to give a new algorithm called “Gauss-Jordan elimination”, which will take more steps but will remedy these problems.

First of all, when we pick a pivot and swap it into place, we scale that row by the inverse of the pivot value. This will set the pivot value itself to ${1}$ (which, incidentally, helps with the shears that come next). Then we shear to eliminate not only the nonzero entries below the pivot, but the nonzero entries above the pivot as well. That leaves the pivot as the only nonzero entry in its column.

Let’s see what this looks like in terms of our usual example:

$\displaystyle\begin{pmatrix}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{pmatrix}$

We use the ${2}$ in the upper-left as a pivot and scale the top row by $\frac{1}{2}$

$\displaystyle\begin{pmatrix}1&\frac{1}{2}&-\frac{1}{2}&4\\-3&-1&2&-11\\-2&1&2&-3\end{pmatrix}$

Next, we clear out the first column with shears. Note that the shear value is now just the negative of the entry in the first column.

$\displaystyle\begin{pmatrix}1&\frac{1}{2}&-\frac{1}{2}&4\\{0}&\frac{1}{2}&\frac{1}{2}&1\\{0}&2&1&5\end{pmatrix}$

So far it’s almost the same as before, except for normalizing the pivot. But now when we choose the $\frac{1}{2}$ in the second column as the pivot we scale its row by $2$

$\displaystyle\begin{pmatrix}1&\frac{1}{2}&-\frac{1}{2}&4\\{0}&1&1&2\\{0}&2&1&5\end{pmatrix}$

and use shears to clear the column above and below this pivot

$\displaystyle\begin{pmatrix}1&0&-1&3\\{0}&1&1&2\\{0}&0&-1&1\end{pmatrix}$

Now the only choice for a pivot in the third column is $-1$. Again we normalize it and use shears to clear the column

$\displaystyle\begin{pmatrix}1&0&0&2\\{0}&1&0&3\\{0}&0&1&-1\end{pmatrix}$

This matrix is in reduced row echelon form, and I say that it is unique. Indeed, we are not allowed to alter the basis of the input space (since that would involve elementary column operations), so we can view this as a process of creating a basis for the output space in terms of the given basis of the input space.

What we do is walk down the input basis, vector by vector. At each step, we ask if the image of this basis vector is linearly independent of the images of those that came before. If so, this image is a new basis vector. If not, then we can write the image (uniquely) in terms of the output basis vectors we’ve already written down. In our example above, each of the first three input basis vectors gives a new output basis vector, and the image of the last input basis vector can be written as the column vector in the last column.

The only possibility of nonuniqueness is if we run out of input basis vectors before spanning the output space. But in that case the last rows of the matrix will consist of all zeroes anyway, and so it doesn’t matter what output basis vectors we choose for those rows! And so the reduced row echelon form of the matrix is uniquely determined by the input basis we started with.

September 3, 2009 Posted by | Algebra, Linear Algebra | 8 Comments