Echelon Forms

(Row) Echelon Form (REF)

echelon_form_0.png

1. All nonzero rows are above all zero rows.

2. Each leading (leftmost nonzero) entry is to the right of the leading entry of the row above it.

3. All entries in a column below a leading entry are zeros. (Actually a consequence of 2.)

Reduced (Row) Echelon Form (RREF)

echelon_example_2.png

4. All leading entries are 1s.

5. Each leading 1 is the only nonzero entry in its column.

In the picture above, there is one variable (x3) without a corresponding pivot, so this variable is free and there are infinitely many solutions (with one parameter).

A couple more examples

From this structure, we can tell there is no solution:

echelon_tall_example.png

From this one, we can tell there is a unique solution:

echelon_typical_square.png reduced_echelon_typical_square.png

The Row Reduction Algorithm

Forward phase

Step 1

Begin with the leftmost nonzero column. This is a pivot column. The pivot position is at the top.

Step 2

Select a nonzero entry in the pivot column as a pivot. If necessary, swap rows to move this entry into the pivot position.

Step 3

Use elementary row operations to create zeros in all positions below the pivot.

Step 4

Ignore the row containing the pivot and all rows (if any) above it. Go back to Step 1. Continue until there are no more nonzero rows to modify.

Backward phase

Step 5

Beginning with the rightmost pivot and working upward and to the left, use elementary row operations to create zeros everywhere above each pivot. If a pivot is not 1, make it 1 by scaling the row.

Examples

General observations: miscellaneous pictures.

6 2 5 1 7 3 2
3 3 6 2 3 8 1
9 7 6 4 8 3 5
5 3 2 0 2 0 5

1 1/3 5/6  1/6   7/6    1/2    1/3
0   1 7/4  3/4  -1/4   13/4      0
0   0   1 1/17  3/17  29/17  -4/17
0   0   0    1 69/40 -43/80 -29/20

1 0 0 0   11/8 -17/16    1/4
0 1 0 0 -67/40  49/80  27/20
0 0 1 0   3/40 139/80  -3/20
0 0 0 1  69/40 -43/80 -29/20
0 0 0 0 0 2 2
0 1 1 0 1 2 0
1 1 2 2 0 0 2
2 2 2 2 2 0 1

1 1 2 2  0 0   2
0 1 1 0  1 2   0
0 0 1 1 -1 0 3/2
0 0 0 0  0 1   1

1 0 0  1  0 0  5/2
0 1 0 -1  2 0 -7/2
0 0 1  1 -1 0  3/2
0 0 0  0  0 1    1
2 0 2 1 2
0 2 1 0 0
1 2 1 0 0
1 2 1 0 0
1 0 1 2 2
0 0 2 1 2

1 0   1 1/2   1
0 1 1/2   0   0
0 0   1 1/2   1
0 0   0   1 2/3
0 0   0   0   0
0 0   0   0   0

1 0 0 0    0
0 1 0 0 -1/3
0 0 1 0  2/3
0 0 0 1  2/3
0 0 0 0    0
0 0 0 0    0
0 1 1 1 1
2 1 1 0 1
1 2 2 0 2
2 1 2 2 1
1 2 2 0 0
1 0 1 0 2

1 1/2 1/2 0 1/2
0   1   1 1   1
0   0   1 2   0
0   0   0 1   0
0   0   0 0   1
0   0   0 0   0

1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0