System of linear equations solver

How it works

A system of linear equations is written as an augmented matrix $[A \mid b]$: one row per equation, the coefficients of the variables, then the right side. Row operations do not change the set of solutions, so Gaussian elimination can bring the matrix to echelon form, where the answer can be read off.

Three things can happen. A row $0 = c$ with $c \ne 0$ is a contradiction: no solution. Otherwise, if every variable has a pivot, there is exactly one solution, found by back substitution (here done on the matrix, by clearing the columns above the pivots). If some columns have no pivot, their variables are free: they can take any value, the others are expressed in terms of them, and the solutions form a line, a plane or a higher dimensional family. The number of free variables is the number of variables minus the rank.

Modulo a prime $p$ the same method works, because every non-zero number has an inverse; a family with $f$ free variables then has exactly $p^f$ solutions. Linear systems over $\mathbb{Z}_p$ appear in cryptanalysis everywhere, from breaking the Hill cipher with known plaintext to the linear algebra step of factoring algorithms.