Row Reduction

Gaussian elimination produces REF, preserving rank, row space, and null space.

The idea

Row reduction, or Gaussian elimination, is the systematic method for simplifying a matrix until its rank and the solutions of its system can be read off.

Its moves are the three elementary row operations: swap two rows, multiply a row by a nonzero number, or add a multiple of one row to another. Each row of the matrix stands for an equation, and none of the three operations changes which values solve the system, because each can be undone. Row reduction applies them in a fixed order.

Algorithm.

Algorithm: Row Reduction Input: a matrix Output: a row-echelon form of it 1. among the unfinished rows, find the leftmost column with a nonzero entry if there is none, return the matrix // the remaining rows are all zero 2. swap rows so the topmost unfinished row has a nonzero entry in that column // that entry is the row's leading entry 3. add multiples of this row to each row below it, zeroing every entry below the leading entry 4. mark the row finished; if unfinished rows remain, go to step 1 5. return the matrix // now in row-echelon form

The result is a row-echelon form: each row's leading entry lies strictly to the right of the one above it, everything below a leading entry is zero, and all-zero rows sit at the bottom.

In echelon form the answers are visible. The nonzero rows are independent — each has a leading entry in a column where the rows below it are zero — so counting them gives the rank. And because every operation is reversible, the row space, the rank and the null space of the echelon form are those of the original matrix.

Ways to work on it

• Walkthrough. Reduce a 3 × 3 matrix to row echelon form and read off its rank.
• Practice. Read the rank off a matrix in or near row echelon form.
• Hardest. Reduce an augmented matrix and classify the system's solution set.

Not sure where to start? Take the ten-question placement test.