Gaussian Elimination

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.

Conditions and key results

Never scale by zero. A square system can be singular yet consistent with infinitely many solutions; elimination, unlike a determinant ratio, shows which. Rounding intermediate values may create false zeros, so retain exact fractions when feasible.

A reliable strategy

1. Write the augmented matrix with variables in a fixed column order.
2. Choose a nonzero pivot, swap if needed, and eliminate all entries below it.
3. Continue to echelon form, classify contradictory and free-variable rows, then back-substitute.
4. Express the complete solution set and substitute it into the original equations.

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.

Common mistakes

Verification and reasonableness

• Substitute the parametric solution for an arbitrary parameter.
• Count pivots and compare ranks of coefficient and augmented matrices.
• Re-run with a different pivot order or RREF for an independent exact check.

Practice

1. What row signals no solution?
2. What creates a free variable?
3. Why swap rows numerically?

Further deduction

Elimination can be organized as $PA=LU$, where $P$ records row swaps, $L$ the elimination multipliers, and $U$ an upper-triangular matrix. Once factored, many systems with the same $A$ and different right-hand sides can be solved efficiently by forward and back substitution. This is computationally preferable to recomputing an inverse.

Operation count matters: dense elimination for an $n\times n$ system uses on the order of $n^3$ arithmetic operations, while each triangular solve after an $LU$ factorization costs order $n^2$. This distinction explains why reusing a factorization for many right-hand sides is much cheaper than starting over or forming an inverse.

Related topics

• Row Reduction
• Echelon Form
• Systems and Matrices