Results 1 to 3 of 3

Math Help - Gauss-Jordan Elimination and Row Operations

  1. #1
    Newbie
    Joined
    Jun 2008
    Posts
    5

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Reckoner's Avatar
    Joined
    May 2008
    From
    Baltimore, MD (USA)
    Posts
    1,024
    Thanks
    75
    Awards
    1

    Smile

    Quote Originally Posted by Mantissa View Post
    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 ith 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}<br />
4a &+& 2b &-& 3c &+& 12d &=& 32\\<br />
2a &+& 5b &&&+& 7d &=& 19\\<br />
a &+& 2b &+& 3c &+& 4d &=& -10\\<br />
-a &+& 4b &+& c &-& d &=& 4<br />
\end{array}\right.

    Let's put this system in matrix form:

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

    which is, in augmented form,

    \left[\begin{array}{cccc|c}<br />
4 & 2 & -3 & 12 & 32\\<br />
2 & 5 & 0 & 7 & 19\\<br />
1 & 2 & 3 & 4 & -10\\<br />
-1 & 4 & 1 & -1 & 4<br />
\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}<br />
1 & 2 & 3 & 4 & -10\\<br />
2 & 5 & 0 & 7 & 19\\<br />
4 & 2 & -3 & 12 & 32\\<br />
-1 & 4 & 1 & -1 & 4<br />
\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}<br />
1 & 2 & 3 & 4 & -10\\<br />
0 & 1 & -6 & -1 & 39\\<br />
0 & -6 & -15 & -4 & 72\\<br />
0 & 6 & 4 & 3 & -6<br />
\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}<br />
1 & 2 & 3 & 4 & -10\\<br />
0 & 1 & -6 & -1 & 39\\<br />
0 & 0 & -51 & -10 & 306\\<br />
0 & 0 & -11 & -1 & 66<br />
\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}<br />
1 & 2 & 3 & 4 & -10\\<br />
0 & 1 & -6 & -1 & 39\\<br />
0 & 0 & 1 & \frac{10}{51} & -6\\<br />
0 & 0 & -11 & -1 & 66<br />
\end{array}\right]

    Now we do R_4 + 11R_3\rightarrow R_4

    \left[\begin{array}{cccc|c}<br />
1 & 2 & 3 & 4 & -10\\<br />
0 & 1 & -6 & -1 & 39\\<br />
0 & 0 & 1 & \frac{10}{51} & -6\\<br />
0 & 0 & 0 & \frac{59}{51} & 0<br />
\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}<br />
 1 & 2 & 3 & 4 & -10\\<br />
 0 & 1 & -6 & -1 & 39\\<br />
 0 & 0 & 1 & \frac{10}{51} & -6\\<br />
 0 & 0 & 0 & 1 & 0<br />
 \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}<br />
 1 & 2 & 3 & 0 & -10\\<br />
 0 & 1 & -6 & 0 & 39\\<br />
 0 & 0 & 1 & 0 & -6\\<br />
 0 & 0 & 0 & 1 & 0<br />
 \end{array}\right]

    R_2 + 6R_3\rightarrow R_2

    R_1 - 3R_3\rightarrow R_1

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

    R_1 - 2R_2\rightarrow R_1

    \left[\begin{array}{cccc|c}<br />
 1 & 0 & 0 & 0 & 2\\<br />
 0 & 1 & 0 & 0 & 3\\<br />
 0 & 0 & 1 & 0 & -6\\<br />
 0 & 0 & 0 & 1 & 0<br />
 \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}<br />
 1 & 0 & 0 & 0\\<br />
 0 & 1 & 0 & 0\\<br />
 0 & 0 & 1 & 0\\<br />
 0 & 0 & 0 & 1<br />
 \end{matrix}\right]<br />
\!\!\left[\begin{matrix}<br />
a\\b\\c\\d<br />
\end{matrix}\right]<br />
=<br />
\left[\begin{matrix}<br />
2\\3\\-6\\0<br />
\end{matrix}\right]

    and thus we have

    \left\{\begin{array}{rcl}<br />
a & = & 2\\<br />
b & = & 3\\<br />
c & = & -6\\<br />
d & = & 0<br />
\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}<br />
4\cdot2 &+& 2\cdot3 &-& 3\cdot-6 &=& 32&\text{\quad\color{red}Yes!}\\<br />
2\cdot2 &+& 5\cdot3 && &=& 19&\text{\quad\color{red}Good!}\\<br />
2 &+& 2\cdot3 &+& 3\cdot-6 &=& -10&\text{\quad\color{red}Uh-huh}\\<br />
-2 &+& 4\cdot3 &+& -6 &=& 4&\text{\quad\color{red}Perfect!}<br />
\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!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2008
    Posts
    5
    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!!!)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 12th 2011, 10:03 PM
  2. Replies: 1
    Last Post: February 16th 2011, 03:06 PM
  3. Gauss-Jordan Elimination
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 3rd 2011, 08:19 AM
  4. Gauss-Jordan elimination
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 18th 2010, 11:42 AM
  5. Gauss-Jordan Elimination
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 1st 2009, 02:59 PM

Search Tags


/mathhelpforum @mathhelpforum