7.3 - The Elimination Method

Click here if you want instructions on using the Algebra Coach to carry out the elimination method.

In this section we explain the elimination method. This method makes use of the fact that the solution of an equation is not changed if we This means that we can take one equation and subtract a multiple of another equation from it without changing the solution of the equations.

The elimination method uses this fact to solve a system of linear equations. Suppose we start with a system of n equations in n unknowns. Pick the first equation and subtract suitable multiples of it from the other n − 1 equations. In each case the multiple is chosen so that the subtraction cancels or eliminates the same variable, say x. The result is that the n − 1 equations contain only n − 1 unknowns (x no longer appears).

We repeat this elimination process until we get 1 equation in 1 unknown, which is then easily solved.

The final step is to back-substitute the solution already obtained for the 1 unknown into the previous equations to find the values of all the other unknowns.




Example: Solve this system of equations by elimination:
Solution: Let’s take twice the first equation, namely:
x + 2 y = 8
and subtract it from the second equation, like this:
The result is one equation in the one unknown, y. The other unknown, x, has been eliminated. Solving this equation yields y = 0.4.

It remains to find x. If we back-substitute y = 0.4 into either of the original equations we get x = 3.6. Thus the solution is:
{ x = 3.6, y = 0.4 }.
(Note that we could have instead found x without back-substitution if we had subtracted 3 times the first equation from the second equation, since this eliminates y.)




The Augmented Matrix

We have explained the essence of elimination. For larger systems we need a systematic procedure to avoid getting mixed up. Gaussian elimination and Gauss-Jordan elimination are two such procedures.

Before we describe them, we introduce some short-hand. A system of equations such as:
will be represented by a rectangular array of numbers called an augmented matrix:


Definitions: Keep in mind the following:


The Elementary Row Operations

We have seen that the solution of a system of equations is not changed if we: These same operations can be applied to the rows of an augmented matrix, since each row just represents an equation. They are then called Elementary Row Operations.



The Elementary Row Operations (E.R.O.’s) are:
  • E.R.O.#1: Choose a row of the augmented matrix and divide (every element of) the row by a constant.

  • E.R.O.#2: Choose any row of the augmented matrix and subtract a multiple of any other row from it (element by element).

  • E.R.O.#3: It is sometimes useful to swap two rows. This is a valid operation because the order of the equations is immaterial.
You may apply these E.R.O.’s to an augmented matrix as often as you like without changing the solution of the equations represented by the matrix.



Example: This example shows how we apply E.R.O.#1 and the notation we use to indicate it. We will divide the first row of the augmented matrix on the left by 2 to produce the new augmented matrix on the right:
Note:   ← ÷ by 2   means “divide the row being pointed to by 2 to produce the new matrix”.



Example: This example shows how we apply E.R.O.#2 and the notation we use to indicate it. In the augmented matrix on the left we will take the second row and from it subtract 3 times the first row to produce the new augmented matrix on the right:
Note:   ← R 2 − 3 · R 1 means “take the row being pointed to (row 2) and subtract 3 times row 1 from it to produce the new row 2.



Example: This example shows how we apply E.R.O.#3 and the notation we use to indicate it. In the augmented matrix on the left we swap rows 1 and 2 to produce the new augmented matrix on the right:
Note:   R 1R 2 means “swap rows 1 and 2.



Gaussian Elimination

The Gaussian elimination procedure is a certain sequence of E.R.O.’s that transforms the augmented matrix into Gauss form (also known as row echelon form) This form is characterized by 1’s on the diagonal, 0’s below the diagonal and any numbers above the diagonal. Here is an example:
This augmented matrix represents the system of equations:
It is solved by back-substitution. Plugging z = 3 into the second equation gives y = 5. Then plugging both z = 3 and y = 5 into the first equation gives x = 7.




Algorithm for Gaussian Elimination

We transform one column at a time into row echelon (or Gauss) form. The column presently being transformed is called the pivot column. We proceed systematically, letting the pivot column be the first column, then the second column, etc. until the last column before the vertical line of the augmented matrix. For each pivot column, we do the following two steps before moving on to the next pivot column:
  1. We locate the diagonal element in the pivot column. This element is called the pivot. The row containing the pivot is called the pivot row. We divide every element in the pivot row by the pivot (i.e. we use E.R.O. #1) to get a new pivot row with a 1 in the pivot position.

  2. We get a 0 in each position below the pivot position by subtracting a suitable multiple of the pivot row from each of the rows below it (i.e. by using E.R.O. #2).
When all the columns to the left of the vertical line have been transformed using the Gaussian elimination procedure the augmented matrix will be in Gauss form and we then solve the system by back-substitution.

 

Example: Use Gaussian elimination to solve the system of equations:
Solution: Perform this sequence of E.R.O.’s on the augmented matrix:

Set the pivot column to column 1. Get a 1 in the diagonal position (in red):


Next, get 0’s below the pivot (in red):

Now, let pivot column = second column.

First, get a 1 in the diagonal position:

Next, get a 0 in the position below the pivot:

Now, let pivot column = third column. Get a 1 in the diagonal position:

This matrix, which is now in Gauss form, represents this system of 3 equations:

It is solved by back-substitution. Plugging z = 3 into the second equation we get y = 5. And plugging z = 3 and y = 5 into the first equation we get x = 7. Thus the solution is:
{ x = 7, y = 5, z = 3 }.


Gauss-Jordan Elimination

The Gauss-Jordan elimination procedure is a slightly different sequence of E.R.O.’s that transforms the augmented matrix into Gauss-Jordan form (also known as reduced row echelon form). This form is characterized by 1’s on the diagonal, 0’s above and below the diagonal on the left side of the vertical line, and any numbers on the right side of the vertical line. Here is an example:
This augmented matrix represents the system of equations:
This system is already solved: x = 7, y = 5, z = 3. Back-substitution is not required. However, about twice as many E.R.O.’s are required to produce the Gauss-Jordan form as the Gauss form.



Algorithm for Gauss-Jordan Elimination

We transform one column at a time into reduced row echelon (or Gauss-Jordan) form. The column presently being transformed is called the pivot column. We proceed systematically, letting the pivot column be the first column, then the second column, etc. until the last column before the vertical line of the augmented matrix. For each pivot column, we do the following two steps before moving on to the next pivot column:
  1. We locate the diagonal element in the pivot column. This element is called the pivot. The row containing the pivot is called the pivot row. We divide every element in the pivot row by the pivot (i.e. we use E.R.O. #1) to get a new pivot row with a 1 in the pivot position.

  2. We get a 0 in each position above and below the pivot position by subtracting a suitable multiple of the pivot row from each of the rows above and below it (i.e. by using E.R.O. #2).
When all the columns to the left of the vertical line have been transformed the augmented matrix will be in Gauss-Jordan form and we can read off the solution from the right-hand column.


Notice that the only difference from the Gauss procedure is that in the second step we get 0ís above the diagonal as well as below the diagonal. It is important to get all of these 0ís before moving on to the next pivot column.



Example: Use Gauss-Jordan elimination to solve the system of equations:
Solution: Perform this sequence of E.R.O.’s on the augmented matrix. Set the pivot column to column 1. Get a 1 in the diagonal position (in red) by using E.R.O. # 1:
Next, get 0’s below the pivot (in red) by using E.R.O. # 2:
Now, let pivot column = second column. First, get a 1 in the diagonal position by using E.R.O. # 1:
Next, get 0’s in the positions above and below the pivot (in red) by using E.R.O. # 2:
Now, let pivot column = third column. Get a 1 in the diagonal position by using E.R.O. # 1:
Next, get 0’s in the positions above the pivot (in red) by using E.R.O. # 2:
This matrix, which is now in Gauss-Jordan or reduced row echelon form, represents the solution:
{x = 49, y = −18, z = 8}.



Redundant and Inconsistent Systems

If the number of equations is greater than the number of unknowns then the systems is guaranteed to be either redundant or inconsistent. But if the number of equations is equal to or less than the number of unknowns then you will generally not recognize a system as being redundant or inconsistent until the very end of the calculation. This is especially true if the system is large.

If you are solving the system of equations by the substitution method and the system is redundant, then you will end up with a final equation that states 0 = 0. Or if the system is inconsistent, then you will end up with one that states a contradiction like 0 = 5. Something similar happens when using Gauss or Gauss-Jordan elimination. If the system is redundant, then at the end of the elimination procedure, when you have the augmented matrix in Gauss or Gauss-Jordan form, the last row of the augmented matrix will be:
This last row represents the equation 0 = 0, a useless piece of information.

If the system is inconsistent then the last row of the augmented matrix will look something like:
The last row represents the equation 0 = 5, a contradiction. Try the exercises, which contain examples of redundant and inconsistent systems of equations.



Example: Use Gaussian elimination to put this system of equations into row echelon form and interpret the result:
Solution: Perform this sequence of E.R.O.’s on the augmented matrix. Set the pivot column to column 1. There is already a 1 in the pivot position, so proceed to get 0’s in the two positions below the pivot:
Now, set the pivot column to the second column. First, get a 1 in the diagonal position:
Next, get a 0 in the position below the pivot:
Now, set the pivot column to the third column. The first thing to do is to get a 1 in the diagonal position, but there is no way to do this. In fact this matrix is already in row echelon form and represents:
This system of equations can’t be solved by back-substitution because we have no value for z. The last equation merely states that 0=0. There is no unique solution because z can take on any value.

The cause of this problem is that if we have 3 unknowns then we need 3 pieces of information (equations) about them to solve them. Mathematicians say the the equations must be linearly independent. In a redundant system some of the information just duplicates other information. In this example a bit of experimentation shows that the third equations is just twice the second equation minus the first equation.
In general, an augmented matrix which has been put into row echelon form and which contains one or more rows of zeros at the bottom of the matrix indicates a redundant system of equations.



Example: Use Gaussian elimination to put this system of equations into row echelon form and interpret the result:
Solution: Perform this sequence of E.R.O.’s on the augmented matrix. Set the pivot column to column 1. There is already a 1 in the pivot position, so proceed to get 0’s below the pivot:
Now, set the pivot column to the second column. There is already a 1 in the pivot position, so proceed to get 0’s below the pivot:
Now, set the pivot column to the third column. The first thing to do is to get a 1 in the diagonal position, but there is no way to do this. In fact this matrix is already in row echelon form and represents:
This system of equations is inconsistent and has no solution. The last equation states a contradiction, namely 0 = −50.
In general, an augmented matrix which has been put into row echelon form and which contains one or more bottom rows consisting of all zeros to the left of the vertical line and a non-zero number to the right indicates an inconsistent system of equations with no solution.



Less equations than unknowns

If the number of equations in the system is less than the number of unknowns then you will reach a point in the Gauss or Gauss-Jordan procedure where you cannot transform the pivot column because you have run out of pivot rows. Here is an example:
The third column has no pivot and no pivot row so you have to stop. This augmented matrix represents this system of equations:
In the second form we see that if a value is given for z then x and y can be expressed in terms of it. The next matrix shows that giving a value for z, say z = 5, amounts to having another row:
Try the exercises, which contain examples of systems with less equations than unknowns.




  Algebra Coach Exercises   




If you found this page in a web search you won’t see the
Table of Contents in the frame on the left.
Click here to display it.