MATH 110: Course Materials - gaussian elimination

COLLEGE ALGEBRA MATH 110		Southwestern Adventist University
Distance Education	Lawrence E. Turner, Jr., Ph.D.

course syllabus

assignments

materials

request a test

proctor form
grade report form

MATH 110 home

Turner home

ADP Home

Gaussian Elimination

We have seen that there are three Rules for manipulating or transforming an augmented matrix that leave the values of the solution set unchanged.

1.	Any two rows can be exchanged.	R_i ⇔ R_k
2.	Any row may be multiplied (or divided) by a non-zero constant.	c·R_i → R_i
3.	A multiple of any row can be added to any other row.	c·R_i + R_k → R_k

We can illustrate the use of these Rules on our original augmented matrix.

We start with the set of simultaneous linear equations:

2x − 3y − 4z = 0

x + 2y + z = 4

3x + y + 3z = 2

And transform this to an augmented matrix:

Let us look at a possible end of our path to a solution. An augmented matrix that is of the form:

Translates back to the set of equations:

x = 1

y = 2

z = −1

We have a solution!

Now the big question is:

Can we by using the three Rules for manipulating the augmented matrix transform the original into the final form?

The answer is an emphatic yes!!

The key is to use these in the right order. We will proceed column by column, left to right. In each column we will first change one element to a 1 (generally using Rule #2). The particular element will be in the same row as the column we are working on; this is, the first element of the first column, the second element down (in the second row) in the second column, etc. After manipulating the augmented matrix to get a 1, then we will use that row to put 0's in the other positions in the column (using Rule #3). This process is called Gaussian Elimination for the mathematician Carl Gauss.

We need to make certain that we proceed in the correct order. The following augmented matrix shows the order in which we get our final values (and the parentheses show what we want at each step):

If we had a set of four simultaneous linear equations in four unknowns, the augmented matrix would have five columns (four on the left from the coefficients of the variables and 1 on the right from the constants) and four rows. We would have a total of 16 values to change (four to 1's and twelve to 0's), and as a consequence, the right-hand column will change into the solution set!

In reality, once we get a 1 in a particular column, it does not matter in which order we get 0's in the rest of the column. That is, as an example, we could invert steps 2 and 3 above. However, it is probably best to follow the order given.

Our first step is to concentrate on the top element of the first column. We want a 1 at that location. For this augmented matrix, there are two ways to get this:

Use Rule #2 and multiply Row 1 by 1/2.
Use Rule #1 and exchange Row 1 and Row 2.

Both of these are correct. However, using Rule #2 will result in fractions appearing (eg. the top value in the second column will become −3/2). Working with fractions by paper and pencil is harder that dealing with integers and more prone to arithmetic errors. If no mistakes are made, the answers will be identical. The intermediate results will be somewhat messy. (alternative).

We can take advantage of the coincidence that a 1 already appears in the first column in the second row, and get our desired 1 in the top element of the left-most column by Rule 1.

To make the first element a 1, we will exchange Row 1 and Row 2 (apply Rule #1) R₁ ⇔ R₂:

Now that we have a 1 in the first row of the first column, we will use this row and use Rule #3 to change the other values in the first column to 0's. If we multiple row 1 by −2 and add it to row 2, then the left-most value of 2 will become a 0.

Multiply Row 1 by −2 and add it to Row 2 (apply Rule #3) −2·R₁ + R₂ → R₂:

In like manner: Multiply Row 1 by −3 and add it to Row 3 (apply Rule #3) −3·R₁ + R₃ → R₃:

The first column is all finished! Notice that if we apply Rule 3 in the future, adding multiples of row 2 or row 3 to row 1, the 1 that we have established will remain untouched since we are adding multiples of zero to it! This is why the proper order is so important. While we are fixing column 1, we let the other columns become whatever they might. When we work on column 2, column 1 will stay in its final form, whereas the other two columns will change. When we deal with column 3, the first two columns will not be affected, and the final (the extra column to make the augmented matrix) will be changed into the solution set!

We are now ready to work on the second column. We want to put a 1 in the middle; that is, in the second row of the second column. We normally would apply Rule #2 and multiply row 2 by −1/7. This is correct, but it will introduce fractions. If we look at row 3, we see we can put a 1 in the second column by multiplying row 3 by −1/5 and the other values in the row will be integers. Unfortunately, this 1 is in the wrong row. Fortunately, we can use Rule #1 to exchange row 2 and row 3 and get the 1 in the proper position!

First, multiply Row 3 by −1/5 (apply Rule #2) (−1/5)·R₃ → R₃:

Now exchange Rows 2 and 3 (apply Rule #1) R₃ ⇔ R₃:

Now, we will use row 2 and its 1 to place 0's in the top and bottom locations of column 2 by applying Rule 3.

Multiply Row 2 by −2 and add it to Row 1 (apply Rule #3) −2·R₃ + R₁ → R₁:

Multiply Row 2 by 7 and add it to Row 3 (apply Rule #3) 7·R₂ + R₃ → R₃:

Now the first two columns are all finished. Note that in fixing up column 2 there were no changes to column 1. The only thing we have left to do is fix up the third column. We want to put a 1 in the third position in the third row with 0's in the other two positions in that column.

The first thing to do with the third column is to apply Rule #2 to get a 1 in the third (or bottom) row.

Multiply Row 3 by −1/6 (apply Rule #2) (−1/6)·R₃ → R₃:

We already have a 0 in the second row, so we do not need to do anything with that row. We want a 0 in row 1.

Multiply Row 3 by −1 and add it to Row 1 (apply Rule #3) −1·R₃ + R₁→ R₁:

And there we have it! We have transformed the original augmented matrix into one from which we can read off the solution set:

x = 1,

y = 2,

z = −1

Several observations:

Regardless, solving a large set of equations takes many oprtations. For the 3x3 example above we needed to change 9 elements in the original to 1's and 0's. This requires 9 applications of the Rules. For a 4x4, it will take 16 applications. For a 5x5 it will take 25 applications. And each application must operate on a larger set of numbers!
We did make some creative use of Rule #1, exchange two rows, to avoid having fractions. Sometimes this cannot be avoided. It is never wrong to work the problem using fractional values. The arithmetic is harder for a human, and it is easier to make an arithmetic error.
It is not rare to make an arithmetic error even without fractions. Fortunately, it is relatively easy to check the solution by substituting the final values back into the original equations.
If the only reason we need Rule #1 is to avoid fractions, then we really do not need it. However, as an example, we do need it in a situation like:

If we are just starting, working on column 1, we want to put a 1 in the upper-left corner. We cannot apply Rule #2 as we would normally since multiplying the first row by any value still leaves a 0. Now we must use Rule # 1 to exchange the top row with either of the others. Then we can proceed normally.
Rule #1 should only be applied to exchange a row where we want a 1 with a row below it.
This process seems rather cumbersome − why go to all this trouble when other methods can be used to solve the set of simultaneous linear equations? The answer is that for small systems, there are probably faster methods, but for large systems (with 4 or more variables) this becomes one of the more efficient methods, and it can be incorporated into a computer program.

Gaussian Elimination Calculator

Enjoy!