# Thread: Gauss-Jordan Elimination and Row Operations

1. ## Gauss-Jordan Elimination and Row Operations

Hello,

I'm currently studying Gauss-Jordan elimination, and am hung up by one thing: How on Earth do row operations work?

I've tried and tried again to make sense of them. What are the rules? As far as I can tell, the steps are entirely arbitrary. Maybe my textbook just does a bad job of explaining it.

Thank you in advance for any light that can be shed!

2. Originally Posted by Mantissa
Hello,

I'm currently studying Gauss-Jordan elimination, and am hung up by one thing: How on Earth do row operations work?

I've tried and tried again to make sense of them. What are the rules? As far as I can tell, the steps are entirely arbitrary. Maybe my textbook just does a bad job of explaining it.

Thank you in advance for any light that can be shed!
Basically, you can perform three operations (called the "elementary row operations") on the rows of a matrix without changing the solutions of the system of linear equations that it represents. These three operations are

1. Swap any two rows (denoted $R_i\leftrightarrow R_j$).
2. Multiply any row by a nonzero scalar (denoted $nR_i\rightarrow R_i$).
3. Add a multiple of one row to another row (denoted $R_i + nR_j\rightarrow R_i$).

Here $R_i$ refers to the $i$th row. The notation basically means "put the expression to the left of the arrow in the row indicated to the right of the arrow."

Your goal is to first get the matrix into row echelon form (this process is Gaussian elimination), and then to get it into reduced-row echelon form (Gauss-Jordan elimination). For a matrix to be in row echelon form means the following:

1. All rows consisting entirely of zeros are at the bottom.
2. All nonzero rows have a 1 as their first nonzero element.
3. The leading entry of any row after the first occurs to the right of the leading entry of the previous row.
4. All entries in a column below a leading 1 are zero.

Reduced-row echelon form is the same except number 4 requires zeroes above and below the leading 1s. What this is essentially saying is that your leading entries should be 1, and that they should have a "stair-step" pattern.

When performing elimination, you should start with the left-most column: do the needed operations to get a 1 with zeroes underneath. Then move onto the next column and get a 1 in the second row with zeroes underneath, and so on. You'll generally be working from top to bottom, and then from left to right.

Let's do an example. This is a big one, and I made it that way so that, as you read through it, once you start to understand the process you may try finishing it on your own, and then comparing your work with mine once you are finished.

Solve the following system of linear equations:

$\left\{\begin{array}{rcrcrcrcr}
4a &+& 2b &-& 3c &+& 12d &=& 32\\
2a &+& 5b &&&+& 7d &=& 19\\
a &+& 2b &+& 3c &+& 4d &=& -10\\
-a &+& 4b &+& c &-& d &=& 4
\end{array}\right.$

Let's put this system in matrix form:

$\left[\begin{matrix}
4 & 2 & -3 & 12\\
2 & 5 & 0 & 7\\
1 & 2 & 3 & 4\\
-1 & 4 & 1 & -1
\end{matrix}\right]
\!\!\left[\begin{matrix}
a\\b\\c\\d
\end{matrix}\right]
=
\left[\begin{matrix}
32\\19\\-10\\4
\end{matrix}\right]$

which is, in augmented form,

$\left[\begin{array}{cccc|c}
4 & 2 & -3 & 12 & 32\\
2 & 5 & 0 & 7 & 19\\
1 & 2 & 3 & 4 & -10\\
-1 & 4 & 1 & -1 & 4
\end{array}\right]$

Now, where to start? We want a 1 in the upper-left, but simply dividing row 1 by 4 would lead to a bunch of messy fractions (when working by hand, it's usually easiest if you try to put off fractions as long as possible as they start to grow unwieldy and invite errors). Instead, let's swap rows 1 and 3:

$R_1\leftrightarrow R_3$

$\left[\begin{array}{cccc|c}
1 & 2 & 3 & 4 & -10\\
2 & 5 & 0 & 7 & 19\\
4 & 2 & -3 & 12 & 32\\
-1 & 4 & 1 & -1 & 4
\end{array}\right]$

Now, we can very easily get zeroes under the 1 in the leftmost column by adding multiples of row 1. For example, adding -2 times the first row to the second will give us a zero on the left, and the other rows are similar. I'll do this all in one step, but you may want to do things one at a time until you get the hang of it.

$R_2 - 2R_1\rightarrow R_2$

$R_3 - 4R_1\rightarrow R_3$

$R_4 + R_1\rightarrow R_4$

$\left[\begin{array}{cccc|c}
1 & 2 & 3 & 4 & -10\\
0 & 1 & -6 & -1 & 39\\
0 & -6 & -15 & -4 & 72\\
0 & 6 & 4 & 3 & -6
\end{array}\right]$

Now we work on column 2. We already have a leading 1 in our second row, so let's get zeroes underneath. We can conveniently add row 3 to row 4 to get 0 there, and a multiple of the second row will take care of row 3. Notice that we do not want to use multiples of the first row, because although $6 - 3\cdot2$ makes 0, we would end up undoing the work we did in the first column.

$R_4 + R_3\rightarrow R_4$

$R_3 + 6R_2\rightarrow R_3$

$\left[\begin{array}{cccc|c}
1 & 2 & 3 & 4 & -10\\
0 & 1 & -6 & -1 & 39\\
0 & 0 & -51 & -10 & 306\\
0 & 0 & -11 & -1 & 66
\end{array}\right]$

Now we'll probably have to introduce some fractions, but 306 is a multiple of 51, so things aren't too bad. First, to get our leading one, let's multiply everything in row 3 by minus one fifty-first:

$-\frac1{51}R_3\rightarrow R_3$

$\left[\begin{array}{cccc|c}
1 & 2 & 3 & 4 & -10\\
0 & 1 & -6 & -1 & 39\\
0 & 0 & 1 & \frac{10}{51} & -6\\
0 & 0 & -11 & -1 & 66
\end{array}\right]$

Now we do $R_4 + 11R_3\rightarrow R_4$

$\left[\begin{array}{cccc|c}
1 & 2 & 3 & 4 & -10\\
0 & 1 & -6 & -1 & 39\\
0 & 0 & 1 & \frac{10}{51} & -6\\
0 & 0 & 0 & \frac{59}{51} & 0
\end{array}\right]$

Now we have one step to get to row echelon form. We get our leading one in the bottom row by doing

$\frac{51}{59}R_4\rightarrow R_4$

$\left[\begin{array}{cccc|c}
1 & 2 & 3 & 4 & -10\\
0 & 1 & -6 & -1 & 39\\
0 & 0 & 1 & \frac{10}{51} & -6\\
0 & 0 & 0 & 1 & 0
\end{array}\right]$

At this point you could back-substitute and solve the system (this would be Gaussian elimination). To do Gauss-Jordan elimination, carry things further and put zeroes above all of the leading ones. This will put our matrix in reduced-row echelon form. This time we want to work right to left, instead of left to right (otherwise subsequent steps will tend to "undo" our previous work). Hopefully you're starting to see the basic process, so I'll just show the steps without commentary:

$R_3 - \frac{10}{51}R_4\rightarrow R_3$

$R_2 + R_4\rightarrow R_2$

$R_1 - 4R_4\rightarrow R_1$

$\left[\begin{array}{cccc|c}
1 & 2 & 3 & 0 & -10\\
0 & 1 & -6 & 0 & 39\\
0 & 0 & 1 & 0 & -6\\
0 & 0 & 0 & 1 & 0
\end{array}\right]$

$R_2 + 6R_3\rightarrow R_2$

$R_1 - 3R_3\rightarrow R_1$

$\left[\begin{array}{cccc|c}
1 & 2 & 0 & 0 & 8\\
0 & 1 & 0 & 0 & 3\\
0 & 0 & 1 & 0 & -6\\
0 & 0 & 0 & 1 & 0
\end{array}\right]$

$R_1 - 2R_2\rightarrow R_1$

$\left[\begin{array}{cccc|c}
1 & 0 & 0 & 0 & 2\\
0 & 1 & 0 & 0 & 3\\
0 & 0 & 1 & 0 & -6\\
0 & 0 & 0 & 1 & 0
\end{array}\right]$

So what does this tell us? Well, since row operations do not change the solutions of the system being represented, we can go back to equation form and we get

$\left[\begin{matrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{matrix}\right]
\!\!\left[\begin{matrix}
a\\b\\c\\d
\end{matrix}\right]
=
\left[\begin{matrix}
2\\3\\-6\\0
\end{matrix}\right]$

and thus we have

$\left\{\begin{array}{rcl}
a & = & 2\\
b & = & 3\\
c & = & -6\\
d & = & 0
\end{array}\right.$

Now, since that was a lot of work (and writing!), mistakes could have easily been made. Therefore, you should always check your work by substituting the values back into the original equations and verifying that they hold:

$\left\{\begin{array}{rcrcrcrl}
4\cdot2 &+& 2\cdot3 &-& 3\cdot-6 &=& 32&\text{\quad\color{red}Yes!}\\
2\cdot2 &+& 5\cdot3 && &=& 19&\text{\quad\color{red}Good!}\\
2 &+& 2\cdot3 &+& 3\cdot-6 &=& -10&\text{\quad\color{red}Uh-huh}\\
-2 &+& 4\cdot3 &+& -6 &=& 4&\text{\quad\color{red}Perfect!}
\end{array}\right.$

Keep in mind that there is no single way to do this. You could have done your elimination using wildly different steps and still have arrived at the same solution. Just try to keep sight of what you are trying to arrive at, and what operations you need to do to get closer to that goal. Each operation should "accomplish" something. Do I need to make this a 1? Should I try to put a 0 there? Ask yourself these questions, and then perform the operation to get it done.

Whew! That took nearly an hour and a half to type. I sure hope it helps!

3. Oh my goodness, thank you. I've printed out your explanation for easy reference. (Also, I'll donate as soon as I can! Thank you so much!!!)