Reducing to triangular form
Gaussian elimination solves linear equations by combining rows to eliminate variables one column at a time, leaving an upper triangular system that is easy to read off. It is the workhorse behind solving systems, inverting matrices, and computing determinants.
The two phases
- Forward elimination. Pick a pivot in each column, then subtract scaled copies of its row from the rows below to clear that column. After all columns, the matrix is triangular.
- Back substitution. Starting from the last equation, which has a single unknown, solve upward, substituting known values as you go.
Choosing the pivot with the largest magnitude in a column, called pivoting, improves numerical stability and avoids dividing by a tiny or zero entry.
Special variants
Over a modulus the same process uses modular inverses for the division steps. A row of zeros that contradicts its right side signals no solution, while a free column signals many solutions.
Key idea
Gaussian elimination clears each column below a chosen pivot to reach triangular form, then back substitutes upward, with pivoting for stability and modular inverses when working under a modulus.