Gaussian elimination

When a system has many equations and many unknowns, ad-hoc trickery becomes hopeless and you want a procedure that always works. Gaussian elimination is that procedure: a systematic way to row-reduce a linear system into a simple staircase shape, then read the answer off easily. Named for Carl Friedrich Gauss, it is the workhorse behind solving linear systems by hand and by computer.

The method uses three allowed moves, called elementary row operations: swap two equations, multiply an equation by a nonzero number, and add a multiple of one equation to another. None of these changes the solution set. You apply them to introduce zeros below the diagonal, reaching an upper-triangular form where the last equation involves just one unknown.

Once in that triangular form, you finish by back-substitution — solve the bottom equation, feed that value upward, and recover each variable in turn. The same algorithm tells you honestly when a system has no solution (a row reading 0 = nonzero) or infinitely many (a row of all zeros). In matrix language, you carry these operations out on an augmented matrix, which is just the equations stripped of their variable names.