Gaussian elimination

Solving a system by substitution works with two or three unknowns but quickly becomes unmanageable. Gaussian elimination, which Gauss used for astronomical computations and which already appears in ancient Chinese texts, organizes the work: the first equation is used to eliminate the first unknown from all the others, then the second to eliminate the second, and so on until a staircase system is obtained that is easy to solve from the bottom up.

The three elementary operations (swapping rows, scaling a row, adding a multiple of one row to another) are reversible, which is why they do not change the solutions: the final system is equivalent to the original. Each pivot is the first nonzero entry of a row; if a pivot is zero at some step, rows are swapped. If a row \((0\ \cdots\ 0\mid b)\) with \(b\neq0\) appears, the system is inconsistent; if some unknowns have no pivot, they are free variables and there are infinitely many solutions.

A guiding example: from \(\left[\begin{array}{cc|c}1&1&3\\2&-1&0\end{array}\right]\), subtracting twice row 1 from row 2 gives \(-3y=-6\), so \(y=2\) and \(x=1\). A common mistake is to forget to apply the operation to the right-hand-side column as well. Later we will see that each step amounts to multiplying by an elementary matrix. The elementary row operations (swapping two rows, multiplying one by a nonzero scalar, adding a multiple of one row to another) do not change the solution set.