Gaussian elimination

Summary

Gaussian elimination is an algorithm that changes a matrix into a row echelon form by elementary row operations. It works column by column, from left to right. In each column, it chooses a nonzero entry as pivot and moves its row up. Then it adds multiples of that row to the rows below, to make their entries in that column zero. Applied to the augmented matrix of a system of linear equations, it gives an equivalent system that back substitution solves. For an $n \times n$ matrix, it uses on the order of $n^3$ arithmetic operations.

Remarks

The algorithm also computes the rank of a matrix and, with a record of the row operations, its determinant. It also tests if a system is consistent: the system is inconsistent exactly when a row $(0, \dots, 0 \mid c)$ with $c \ne 0$ appears. The method was known in China in the book The Nine Chapters on the Mathematical Art, long before Gauss.

Explanations

L1 human

Gaussian elimination is the method of solving equations by removing one unknown at a time. We use the first equation to remove $x_1$ from all the other equations, then the second to remove $x_2$, and so on. At the end, the last equation has the fewest unknowns, and we solve upwards.