Gaussian Elimination

Gaussian elimination transforms a matrix into row echelon form (REF) using elementary row operations to solve linear systems $A\mathbf{x} = \mathbf{b}$.

Elementary row operations:

1. Swap two rows
2. Multiply a row by a nonzero scalar
3. Add a scalar multiple of one row to another

Process:

1. Forward elimination — create zeros below each pivot (leading nonzero entry) column by column → REF
2. Back substitution — solve from bottom row upward
3. Gauss-Jordan — continue to create zeros above pivots → reduced REF (RREF), giving solution directly

Reveals:

• Rank and Null Space — number of pivots = rank
• Whether the system has 0, 1, or infinitely many solutions
• The determinant (product of pivots, with sign from row swaps)

LU decomposition: Gaussian elimination implicitly factors $A = LU$ where $L$ is lower triangular (stores the multipliers) and $U$ is upper triangular (the REF). More efficient than re-eliminating for multiple right-hand sides.

Complexity: $O(n^3)$ for an $n \times n$ system.

See also: Matrix Multiplication, Rank and Null Space