The Unapologetic Mathematician

Row Echelon Form

For now, I only want to focus on elementary row operations. That is, transformations of matrices that can be effected by multiplying by elementary matrices on the left, not on the right.

Row echelon form is a (non-unique) simplification of the form of a matrix that can be reached by elementary row operations. A matrix is in row echelon form if all the empty (all-zero) rows are below all the nonzero rows, and the leftmost nonzero entry in a given row is to the right of the leftmost nonzero entry in the row above it. For example, an upper-triangular matrix is in row echelon form. We put a matrix into row echelon form by a method called “Gaussian elimination”, which always moves a matrix closer and closer to row echelon form.

First, we look at the first column. If it’s empty we leave it alone and move on the next column. If there are any nonzero entries, there must be only one of them at the top of the column, or the matrix can’t be in row echelon form. So, if this isn’t the case then we pick one of the nonzero entries and call it our “pivot”. Swap its whole row up to the top row, and then use shears to eliminate all the other nonzero entries in the column before moving on to the second column.

Before we continue, I’ll point out that the pivot is now the leading entry on a nonzero row at the top of the matrix. We’ll regard it as fixed, so whenever I say “all rows” I mean all the rows that we haven’t locked down yet.

Now that we’ve moved on to the next column, we again look for any nonzero entries. If there are none, we can move on. But if there are, we choose one to be a pivot, swap it to the top (below the previously locked rows) and use shears to remove all the other nonzero entries in the column (other than the locked rows). We continue like this, choosing pivots where there are nonzero entries to deal with, moving them to the top, and eliminating all the other nonzero entries below them, until we’ve locked down all the rows or run out of columns.

Let’s look at this method applied to the matrix

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

in the first column we have the nonzero value $2$ in the first row, so we may as well leave it where it is. We add $\frac{3}{2}$ times the first row to the second to eliminate the $-3$ there, and add the first row to the third to eliminate the $-2$ there. At this point our matrix looks like

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

Now in the second row we have $\frac{1}{2}$ at the top (since the very top row is finished). We leave it where it is and add $-4$ times the second row to the third to eliminate the $2$ there. Now the matrix looks like

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

now there are no empty rows, so “all” of them are below all the nonzero rows. Further, within the nonzero rows the leading entries move from left to right as we move down the rows. The matrix is now in row echelon form.

Now let’s try this one:

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

Again, we’ll start with using the upper-left $2$ as our first pivot. We use shears to eliminate the rest of the entries in the first column and get

$\displaystyle\begin{pmatrix}2&1&-1&8\\{0}&0&0&5\\{0}&2&-1&-10\\{0}&-2&1&5\end{pmatrix}$

Now there are nonzero entries in the second column, but none of them are at the top. So we swap the second and third rows to bring a pivot to the top

$\displaystyle\begin{pmatrix}2&1&-1&8\\{0}&2&-1&-10\\{0}&0&0&5\\{0}&-2&1&5\end{pmatrix}$

and eliminate using a shear

$\displaystyle\begin{pmatrix}2&1&-1&8\\{0}&2&-1&-10\\{0}&0&0&5\\{0}&0&0&-5\end{pmatrix}$

the third column has no nonzero entries (other than the two locked-in entries at the top), so we skip it. In the fourth column we use $5$ as a pivot and eliminate, getting

$\displaystyle\begin{pmatrix}2&1&-1&8\\{0}&2&-1&-10\\{0}&0&0&5\\{0}&0&0&0\end{pmatrix}$

Now the empty row is on the bottom, and the leading entries of the other rows move from left to right as we move down the rows. Thus, the matrix is now in row echelon form.

Advertisements

September 1, 2009 - Posted by | Algebra, Linear Algebra

2 Comments »

1. […] Equations with Gaussian Elimination The row echelon form of a matrix isn’t unique, but it’s still useful for solving systems of linear […]

Pingback by Solving Equations with Gaussian Elimination « The Unapologetic Mathematician | September 2, 2009 | Reply

2. […] Row Echelon Form Let’s take row echelon form and push it a little further into a form that is unique: reduced row echelon […]

Pingback by Reduced Row Echelon Form « The Unapologetic Mathematician | September 3, 2009 | Reply