# The Row Reduction Algorithm

## (Gaussian elimination)

**The forward phase**

- Begin with the leftmost nonzero column. This is a pivot column.
The pivot position is at the top.
- Select a nonzero entry in the pivot column as a pivot. If necessary,
interchange rows to move this entry into the pivot position.
- Use row addition operations to create zeros in all positions below
the pivot.
- Cover (or ignore) the row containing the pivot position and cover all
rows, if any, above it. apply steps 1-3 to the submatrix that remains.
Repeat the process until there are no more nonzero rows to modify.

**The backward phase**

- Beginning with the rightmost pivot and working upward and to the left,
create zeros above each pivot. If a pivot is not 1, make it 1 by a scaling operation.

**Remark:** The forward phase produces a row echelon form of
the input matrix. From this echelon form the backward phase produces
the reduced row echelon form of the input matrix.