Gaussian Elimination Algorithm

Gaussian elimination solves a system of linear equations, or reduces a matrix to row echelon form, by applying a sequence of elementary row operations, swapping rows, scaling a row by a nonzero constant, and adding a multiple of one row to another, to systematically eliminate variables from all but one equation at a time, after which the remaining unknowns are found by back substitution. It is named for Carl Friedrich Gauss, though the underlying method for solving linear systems was known in ancient Chinese mathematics texts more than a thousand years earlier. It runs in O(n cubed) time for an n by n system and remains a standard method underlying much of numerical linear algebra.