Gaussian Elimination

A rigorous elimination algorithm for solving linear systems, detecting consistency, and controlling pivots.

Represent → transform → verify. A linear-algebra object is represented as coordinates or a matrix, transformed through valid row or column operations, and checked against the original invariant or equation.

Precise definition

Gaussian elimination applies elementary row operations to an augmented matrix until it reaches row echelon form, then uses back substitution. Row replacement, row swap, and multiplication of a row by a nonzero scalar preserve the represented solution set.

Notation and mathematical language

A pivot is the leading nonzero entry used to eliminate entries below it. A row $[0\ \cdots\ 0\mid c]$ with $c\ne0$ signals inconsistency. Free variables occur in nonpivot columns and parameterize infinitely many solutions when the system is consistent.

Conceptual picture

Elimination combines equations to remove variables while retaining equivalence. In exact arithmetic, different legal pivot choices lead to the same solution classification. In floating-point arithmetic, partial pivoting reduces error by avoiding division by very small pivots.

Fully worked example

Interpretation and application

Elimination underlies matrix factorization and scientific solvers. For numerical data, a small residual $A\hat x-b$ checks equation fit but does not alone guarantee a small solution error when $A$ is ill-conditioned.