Echelon forms and Gaussian elimination

Why this exists

Row operations change an augmented matrix without changing the solutions of its system, but there are endless ways to apply them and most of them wander. What was missing is a target, a shape from which the solution can be read with almost no work, and a strategy that reaches it every time. The target is a staircase of zeros in the lower left: a last equation in one variable, the one above it in two, and so on.

Definition

In a nonzero row of a matrix, the leading entry is the first entry, reading from the left, that is not 0. A row of all zeros has no leading entry.

A matrix is in row echelon form (echelon form, for short) when

• every row of all zeros sits below every nonzero row, and
• each leading entry lies in a column strictly to the right of the leading entry of the row above it.

It follows that every entry below a leading entry is 0. The position of a leading entry is a pivot, and its column a pivot column.

A matrix is in reduced row echelon form when, in addition,

• every leading entry is 1, and
• each leading 1 is the only nonzero entry in its column.

For an augmented matrix, the whole row, constant included, is read from left to right.

Gaussian elimination brings a matrix to echelon form: work through the columns from left to right, choose a pivot in each, and clear every entry below it with replacements R_i + cR_j \to R_i. Back-substitution then solves the system from the bottom row up. Going on to scale each pivot to 1 and clear above it as well is Gauss-Jordan elimination, and it ends in the reduced form.

Intuition

A line drawn under each leading entry and down beside the next one forms a staircase. Each step goes down one row and right by one column or more, and everything below the line is 0. Read as equations, each step down the staircase drops at least one variable, so the bottom nonzero row has the fewest and is solved first.

Gaussian elimination builds the staircase one step at a time. Clearing below the first pivot finishes the first column; the rows beneath are then a smaller matrix of the same kind, and the work repeats there. The reduced form goes further: each row names one variable alone, and the solution stands in the column right of the bar.

Results

Worked examples

Boundaries

• A shape, not a solution. Systems with no solution or infinitely many also have echelon forms. This lesson keeps to a pivot in every variable column, which means exactly one solution; the other cases are read in Solving a system by row reduction: one, none or infinitely many solutions.
• A pivot is never 0. A zero in the pivot position is dealt with by a swap. If the column is 0 from the pivot row down, it has no pivot and the staircase steps further right.
• Conventions differ. Some books also require leading 1s in echelon form; here that belongs to the reduced form only.
• Exact arithmetic. A calculator working in decimals rounds, and an entry that should be 0 can appear as a tiny pivot.

Where this goes next

Solving a system by row reduction: one, none or infinitely many solutions reads one, none or infinitely many solutions from the final rows, and Solving a system by row reduction: one, none or infinitely many solutions describes columns with no pivot. The reduced form is studied in its own right in Reduced row echelon form, and counting pivots gives the rank. Gaussian elimination is the organized form of the work in Systems in three variables.

Exercises

Recognizing the forms

For exercises 1 to 6, classify the matrix as reduced row echelon form, row echelon form but not reduced, or neither, and give the reason.

1. \begin{bmatrix} 1 & 5 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}
2. \begin{bmatrix} 4 & 1 & 2 \\ 0 & 0 & 3 \\ 0 & 6 & 1 \end{bmatrix}
3. \begin{bmatrix} 1 & 0 & -5 \\ 0 & 1 & 6 \\ 0 & 0 & 5 \end{bmatrix}
4. \begin{bmatrix} 0 & 0 & 0 \\ 1 & 2 & 5 \\ 0 & 0 & 1 \end{bmatrix}
5. \begin{bmatrix} 1 & 6 & 0 & -2 \\ 0 & 0 & 1 & 3 \end{bmatrix}
6. \begin{bmatrix} 1 & -5 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}

Back-substitution

Solve the system with each augmented matrix.

7. \left[\begin{array}{cc|c} 1 & -3 & 7 \\ 0 & 2 & -4 \end{array}\right]
8. \left[\begin{array}{ccc|c} 1 & 2 & -1 & 4 \\ 0 & 1 & 3 & 5 \\ 0 & 0 & 2 & 4 \end{array}\right]
9. \left[\begin{array}{ccc|c} 3 & -1 & 2 & 1 \\ 0 & -2 & 1 & 3 \\ 0 & 0 & 4 & -4 \end{array}\right]

Gaussian elimination

Reduce to echelon form, naming each operation, and back-substitute.

10. x + 3y = -1, 4x + 5y = 3
11. 3x + 2y = 1, x - y = 2
12. x + y - z = 2, 2x + 3y + z = 7, -x + 2y + 3z = 0
13. x + 2y + z = 1, 2x + 4y + 3z = 4, x + 3y - z = -4
14. 2y + z = 1, x + y + z = 2, 3x - y + 2z = 3

All the way to reduced form

15. Take \left[\begin{array}{ccc|c} 1 & -2 & 1 & -2 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & 1 & 2 \end{array}\right] to reduced row echelon form and read off the solution.
16. Take the augmented matrix of 2x + 6y = 8, 3x + 7y = 4 to reduced row echelon form and read off the solution.
17. Wekesa buys 15 sheets of cover material for the bindery: buckram (a stiff cloth) at 10 dollars a sheet, linen at 30 dollars and leather at 40 dollars, 360 dollars in all, with twice as many buckram sheets as leather. Write the augmented matrix in the order b, n, h (buckram, linen, leather), reduce it, and find each count.

Reasoning

18. For x + y = 5, 2x + 4y = 14, Togzhan reaches \left[\begin{array}{cc|c} 1 & 1 & 5 \\ 0 & 2 & 4 \end{array}\right] and Wekesa reaches \left[\begin{array}{cc|c} 2 & 4 & 14 \\ 0 & -1 & -2 \end{array}\right]. Show that each is an echelon form reached by row operations, and that both have the same reduced form.
19. Explain why, in an echelon form, every entry below a leading entry is 0.
20. In Gaussian elimination, the second pivot row is used to clear column 2. Explain why this cannot undo the zeros already made in column 1.
21. Tyyne says a square matrix in reduced row echelon form with a pivot in every column must be the identity matrix. Explain why she is right.