Row Echelon Form — Gaussian Elimination Explained

Row Echelon Form (REF)

A matrix is in Row Echelon Form when:

1. All zero rows are at the bottom
2. The first non-zero entry in each row (the pivot) is to the right of the pivot in the row above
3. All entries below a pivot are zero

Gaussian Elimination Algorithm

To achieve REF, perform these elementary row operations:

1. Swap two rows
2. Multiply a row by a non-zero scalar
3. Add a multiple of one row to another

Example

Start:  | 2  1  -1 |  3 |
        | 4  3   1 |  7 |
        | 2  1   3 |  5 |

R2 = R2 - 2*R1:
        | 2  1  -1 |  3 |
        | 0  1   3 |  1 |
        | 2  1   3 |  5 |

R3 = R3 - R1:
        | 2  1  -1 |  3 |
        | 0  1   3 |  1 |
        | 0  0   4 |  2 |

This is now in REF. We can read off the rank (3) and solve by back substitution.

Reduced Row Echelon Form (RREF)

RREF goes further: each pivot is 1, and all entries above and below each pivot are zero. RREF is unique for a given matrix, while REF is not.

Computational Complexity

Gaussian elimination runs in O(n^3) time for an n x n matrix, making it practical for matrices of moderate size. It is more efficient than cofactor expansion for computing determinants (O(n!) for cofactors).