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

multiply both sides of the equation by the same factor.
subtract equal quantities from both sides of an equation.

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:

2 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 found x without back-substitution if we had subtracted 3 times the first equation from the second equation, since this eliminates y.)

Gauss and Gauss-Jordan Elimination

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

First, some short-hand. A system of equations such as:

will be represented by a rectangular array of numbers called an augmented matrix:

Definitions:

The individual numbers in the matrix are called elements.
Columns run down the matrix. e.g. the 4th column contains the elements 80, 7 and 22.
Rows run across. The 3rd row contains 3, −1, 2 and 22. Note that the number of columns in an augmented matrix is always 1 more than the number of rows.
The diagonal is the set of elements that starts at the top, left corner of the matrix and runs diagonally down and to the right. The diagonal of the above matrix consists of the numbers 4, 1 and 2.
Any numbers in position D are said to be on the diagonal, any in position a are above the diagonal, and any in position b are below the diagonal.

The Elementary Row Operations

We have seen that the solution of a system of equations is not changed if we:

divide an both sides of an equation by a constant, or
subtract a multiple of one equation from another equation.

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).

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₂ − 3 · R₁ means “take the row being pointed to (row 2) and subtract 3 times row 1 from it to produce the new row 2.”

The Gauss elimination procedure is a certain sequence of E.R.O.’s which transforms the augmented matrix into Gauss form (also known as triangular echelon form):

This form is characterized by 1’s on the diagonal, 0’s below the diagonal and any numbers above the diagonal. This new 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.

The Gauss-Jordan elimination procedure is a slightly different sequence of E.R.O.’s which transforms the augmented matrix into Gauss-Jordan form (also known as row-reduced echelon form):

This form is characterized by 1’s on the diagonal, 0’s above and below the diagonal on the LHS of the vertical line, and any numbers on the RHS of the vertical line. This new 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.

The Gauss and the Gauss-Jordan Elimination Procedures

We transform one column at a time into the desired form, either Gauss or Gauss-Jordan. 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:

First, locate the diagonal element in the pivot column. This element is called the pivot. The row containing the pivot is called the pivot row. Divide every element in the pivot row by the pivot (ie. use E.R.O. #1) to get a new pivot row with a 1 in the pivot position.
The second step differs for the two procedures. In the Gauss procedure 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 (ie. by using E.R.O. #2). In the Gauss-Jordan procedure 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.

When all the columns before the vertical line have been transformed using the Gauss procedure the augmented matrix will be in Gauss form and we solve the system by back-substitution.

When all the columns before the vertical line have been transformed using the Gauss-Jordan procedure the augmented matrix will be in Gauss-Jordan form and we simply read the solution from the column to the right of the vertical line.

Example: Use Gauss 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 }.

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 row-reduced echelon form, represents the solution:

{x = 49, y = −18, z = 8}.

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.

Recognizing Redundant or 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.

Algebra Coach Exercises