Gauss Jordan Elimination Through Pivoting

A system of linear equations can be placed into matrix form. Each equation becomes a row and each variable becomes a column. An additional column is added for the right hand side. A system of linear equations and the resulting matrix are shown.

The system of linear equations ...

3x + 2y - 4z =  3
2x + 3y + 3z = 15
5x - 3y +  z = 14

becomes the augmented matrix ...

x	y	z	rhs
3	2	-4	3
2	3	3	15
5	-3	1	14

The goal when solving a system of equations is to place the augmented matrix into reduced row-echelon form, if possible.

There are three elementary row operations that you may use to accomplish placing a matrix into reduced row-echelon form.

Each of the requirements of a reduced row-echelon matrix can satisfied using the elementary row operations.

If there is a row of all zeros, then it is at the bottom of the matrix.
Interchange two rows of a matrix to move the row of all zeros to the bottom.
The first non-zero element of any row is a one. That element is called the leading one.
Multiply (divide) the row by a non-zero constant to make the first non-zero element into a one.
The leading one of any row is to the right of the leading one of the previous row.
Multiply a row by a non-zero constant and add it to another row, replacing that row. The point of this elementary row operation is to make numbers into zeros. By making the numbers under the leading ones into zero, it forces the first non-zero element of any row to be to the right of the leading one of the previous row.
All elements above and below a leading one are zero.
Multiply a row by a non-zero constant and add it to another row, replacing that row. The point of this elementary row operation is to make numbers into zero. The difference here is that you're clearing (making zero) the elements above the leading one instead of just below the leading one.

What is pivoting?

The objective of pivoting is to make an element above or below a leading one into a zero.

The "pivot" or "pivot element" is an element on the left hand side of a matrix that you want the elements above and below to be zero.

Normally, this element is a one. If you can find a book that mentions pivoting, they will usually tell you that you must pivot on a one. If you restrict yourself to the three elementary row operations, then this is a true statement.

However, if you are willing to combine the second and third elementary row operations, you come up with another row operation (not elementary, but still valid).

You can multiply a row by a non-zero constant and add it to a non-zero multiple of another row, replacing that row.

So what? If you are required to pivot on a one, then you must sometimes use the second elementary row operation and divide a row through by the leading element to make it into a one. Division leads to fractions. While fractions are your friends, you're less likely to make a mistake if you don't use them.

What's the catch? If you don't pivot on a one, you are likely to encounter larger numbers. Most people are willing to work with the larger numbers to avoid the fractions.

The Pivot Process

Pivoting works because a common multiple (not necessarily the least common multiple) of two numbers can always be found by multiplying the two numbers together. Let's take the example we had before, and clear the first column.

x	y	z	rhs
3	2	-4	3
2	3	3	15
5	-3	1	14

Helpful Hints

Although you do not have to pivot on a one, it is highly desirable. Pivoting on a one means that you're multiplying by 1 (which is easy to do).
It is nice to pivot on the main diagonal, but not absolutely necessary. Some people like to start in the upper left and work their way down to the lower right.
As long as you pivot only once per row and column, the columns which have been cleared will remain cleared.
Since the point of pivoting is to clear the pivot column, picking a column which already has zeros in it saves time because you don't have to change the row that contains the zero.

Selecting a Pivot

Pick the column with the most zeros in it.
Use a row or column only once
Pivot on a one if possible
Pivot on the main diagonal
Never pivot on a zero
Never pivot on the right hand side

Since there is no one in the first row, we have two options: Either we divide the first row by three and work with fractions, or we pivot on the three and get large numbers. That is the option I'm going to use. I'll pivot on the three in R₁C₁. Go ahead and circle that as the pivot element. Depending on your browser, you may see the pivot elements circled in red or just with a * in front of it.

x	y	z	rhs
*3	2	-4	3
2	3	3	15
5	-3	1	14

The idea is to make the boxed (yellow) numbers into zero. Using the combined row operation (this is not an elementary operation), that could be done by 3R₂ - 2R₁ → R₂ and 3R₃ - 5R₁ → R₃.

The only row not being changed is the row containing the pivot element (the 3). The whole point of the pivot process is to make the boxed values into zero. Go ahead and rewrite the pivot row and clear (make zero) the pivot column.

x	y	z	rhs
*3	2	-4	3
0
0

To replace the values in row 2, each new element is obtained by multiplying the element being replaced in the second row by 3 and subtracting 2 times the element in the first row from the same column as the element being replaced.

To perform the pivot, place one finger on the pivot (circled number), and one finger on the element being replaced. Multiply these two numbers together. Now, place one finger on the boxed number in the same row as the element you're replacing and the other finger in the pivot row and the same column as the number your replacing. Multiply these two numbers together. Take the product with the pivot and subtract the product without the pivot.

x	y	z	rhs
*3	2	-4	3
2	3	3	15
5	-3	1	14

To replace the 3 in R₂C₂, you would take 3(3) - 2(2) = 9 - 4 = 5.

To replace the 3 in R₂C₃, you would take 3(3) - 2(-4) = 9 +8 = 17.

To replace the 15 in R₂C₄, you would take 3(15) - 2(3) = 45 - 6 = 39.

To replace the -3 in R₃C₂, you would take 3(-3) - 5(2) = -9 - 10 = -19.

To replace the 1 in R₃C₃, you would take 3(1) - 5(-4) = 3 + 20 = 23

To replace the 14 in R₃C₄, you would take 3(14) - 5(3) = 42 - 15 = 27.

Here's how the process looks.

x	y	z	rhs
pivot row, copy 3	pivot row, copy 2	pivot row, copy -4	pivot row, copy 3
pivot column, clear 0	3(3) - 2(2) 5	3(3) - 2(-4) 17	3(15) - 2(3) 39
pivot column, clear 0	3(-3) - 5(2) -19	3(1) - 5(-4) 23	3(14) - 5(3) 27

Or, if you remove the comments, the matrix after the first pivot looks like this.

x	y	z	rhs
3	2	-4	3
0	5	17	39
0	-19	23	27

It is now time to repeat the entire process. We go through and pick another place to pivot. We would like it to be on the main diagonal, a one, or have zeros in the column. Unfortunately, we can't have any of those. But since we have to multiply all the other numbers by the pivot, we want it to be small, so we'll pivot on the 5 in R₂C₂ and clear out the 2 and -19.

x	y	z	rhs
3	2	-4	3
0	*5	17	39
0	-19	23	27

Begin by copying down the pivot row (2nd row) and clearing the pivot column (2nd column). Previously cleared columns will remain cleared.

x	y	z	rhs
	0
0	*5	17	39
0	0

Here are the calculations to find the next interation. Pay careful attention to the 3rd row where we're subtracting -19 times a value. Since we're subtracting a negative, I went ahead and wrote it as plus 19.

x	y	z	rhs
5(3) - 2(0) 15	pivot column, clear 0	5(-4) - 2(17) -54	5(3) - 2(39) -63
pivot row, copy 0	pivot row, copy 5	pivot row, copy 17	pivot row, copy 39
previously cleared 0	pivot column, clear 0	5(23) + 19(17) 438	5(27) + 19(39) 876

And the resulting matrix.

x	y	z	rhs
15	0	-54	-63
0	5	17	39
0	0	438	876

Notice that all the elements in the first row are multiples of 3 and all the elements in the last row are multiples of 438. We'll divide to reduce the rows.

x	y	z	rhs
5	0	-18	-21
0	5	17	39
0	0	1	2

That had the added benefit of giving us a 1, exactly where we want it to be to pivot. So, we'll pivot on the 1 in R₃C₃and clear out the -18 and 17. Circle your pivot and box the other numbers in that column to clear.

x	y	z	rhs
5	0	-18	-21
0	5	17	39
0	0	*1	2

Copy down the pivot row and clear the pivot column. Previously cleared columns will remain cleared as long as you don't pivot in a row or column twice.

x	y	z	rhs
	0	0
0		0
0	0	*1	2

Notice that each time, there are fewer calculations to perform. Here are the calculations for this pivot. Again, since the value in the pivot column in the first row is -18 and we're subtracting, I wrote it as + 18.

x	y	z	rhs
1(5) +18(0) 5	previously cleared 0	pivot column, clear 0	1(-21) + 18(2) 15
previously cleared 0	1(5) - 17(0) 5	pivot column, clear 0	1(39) - 17(2) 5
pivot row, copy 0	pivot row, copy 0	pivot row, copy 1	pivot row, copy 2

And the resulting matrix.

x	y	z	rhs
5	0	0	15
0	5	0	5
0	0	1	2

Notice that the first and second rows are multiples of 5, so we can reduce those rows.

x	y	z	rhs
1	0	0	3
0	1	0	1
0	0	1	2

And the final answer is x = 3, y = 1, and z = 2. You can also write that as an ordered triplet {(3,1,2)}.

Hopefully, you noticed that when I worked this example, I didn't follow the hints I gave. That's because I wanted you to see what happens if you don't pivot on a one. There was a one, on the main diagonal, in the original matrix, and it would have been better to start there.

Summary

Pick your pivot element wisely.
Picking a column with zeros in it means less pivoting.
Picking a one as the pivot makes the numbers smaller, the multiplication easier, and leaves the non-zero elements in a cleared column the same (less pivoting)
Pivoting on the main diagonal means you won't have to switch rows to put the matrix into reduced row-echelon form.
Do not pivot on a zero.
Do not pivot on the right hand side.
Only use a row or column once
Take the product with the pivot minus the product without the pivot

Special Cases

If you get a row of all zeros except for the right hand side, then there is no solution to the system.

If you get a row of all zeros, and the number of non-zero rows is less than the number of variables, then the system is dependent, you will have many answers, and you need to write your answer in parametric form.