4-3 Gauss-Jordan Elimination

Introduction
• we will now learn how to solve a system
• by doing row operations on its augmented matrix
• using a method known as Gauss-Jordan elimination
• to convert the augmented matrix to reduced row-echelon form (or reduced form)

Reduced row-echelon form:
(1) each row starts with an initial 1 (0’s to the left of it)
(2) each initial 1 is to the right of the one in the row above
(3) there are 0’s below and above each initial 1
(4) rows of all zeros (if any) will be at the bottom  (not shown below)
Example:

Gauss-Jordan elimination: the algorithm

The following description is an outline of the method.  The details will become clear as we work through the example to follow.

 1. Get a 1 in upper left corner (by row ops 1 and/or 2) 2. Get 0's everywhere else in its column (by row op 3) 3. Mentally delete row 1 and column 1. What remains is a smaller submatrix 4. Get 1 in upper lefthand corner of the submatrix. 5. Get 0's everywhere else in its column for the whole matrix (not just the submatrix) 6. Mentally delete row 1 and column 1 of the submatrix, forming an even smaller submatrix 7. Repeat 4, 5, 6 until you can go no further. 8. The matrix will now be in reduced row-echelon form (RREF), or just reduced form 9. Re-write the system in natural form. 10. State the solution Additional instructions: A. If you get a row of all zeros, use row op 1 to make it the last row B. If you get a row with all zeros to the left of the line, and a non-zero on the right,  STOP (no solution).

Example

2x  - 2y + z  =  3
3x +  y  -  z  = 7
x  - 3y + 2z = 0
Here's how the algorithm goes:

Forward elimination
R3 ‹– –› R1
-3R1  +  R2 –›  R
-2R1  +   R3 –›R
 `  ` `  ` `  ` `  ` `  ` `  ` `  ` `  ` `  ` `  ` `  ` `  `
Let's see if we can do these two operations
‹–
(1/10)R2–›R2
3R2 + R1 –› R1
-4R2 + R3–›R3
-5R3 –› R3
(1/10)R3 + R1 –› R1
(7/10)R3 + R2 –› R2
Reduced row-echelon form
x1 = 2, x2 = 0, x3 = -1

Variations on reduced row-echelon forms

• notice that this describes a system whose third equation is:       0x + 0y = 0
• this system (of course) will have no solution
___________________________________________

• notice that this represents a system with 3 unknowns but just 2 equations
• this system will have infinitely many solutions
• the next section explains how to state your answer in such a case

Stating the solution when there are infinitely many of them

• when there are infinitely many solutions
• "the solution" is stated parametrically
• the reduced form
• corresponds to the system:
x1 +  x3 = -3/7
x2 - 2x3 =  8/7
Here's what you do:

1. Solve each equation for its first variable:

x1 = -x3 - 3/7
x2 = 2x3 + 8/7
• the variables x1 and x2 on the left appear nowhere else
• the variable (or variables) on the right can be chosen arbitrarily ...
• to be any real numbers
• we will use the parameter t here to represent any real number
• if there were 2 variables on the right, we could use t and s, or t1 and t2 ...

for any real number t, a solution is

x3 = t                     (standing for any real number)
x2 = 2t + 8/7           (subst. t in 2nd equation above)
x1 = -t - 3/7             (subst. t in 1st equation above)
or, stating the solution as a triple:
(-t - 3/7,  2t + 8/7,  t) for any real t
(since there are infinitely many real numbers t to choose from, this represents infinitely many solutions)

For example, for t = 4/7, we have the solution ).

Try it; it works!

Graphing calculator: reduced row-echelon form

You are required to know how to do this by hand.  If "by hand" is not specified, you can use the TI-83 or TI-86 to do it.  I will demo the TI-83.  For the TI-86, click below.

TI-86

Student Solutions Manual software: reduced row-echelon form

Note:  this section to be updated to reflect current edition.  Use current content at your risk!

The Student Solutions Manual that accompanies our text has a floppy diskette containing software that can be helpful in completing some of the exercises (you can do this instead of using a graphing calculator).

By running that software and using the menus in a pretty obvious way, one can

• define a matrix
• find the reduced row-echelon form automatically
As an example, see problem 25 on page 211.  The augmented matrix for that system can be defined using the software, and by using the menus, the following screen can be brought up:

By selecting the option "Do <e>very step automatically" (enter an "e" from the keyboard), the reduced row-echelon form will be computed, and you will see this screen:

Pretty easy, huh?