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.