Gaussian elimination, also known as row reduction, is a fundamental algorithm in linear algebra used to solve systems of linear equations, determine matrix rank, compute inverses, and evaluate determinants. The method transforms a system into a simpler, equivalent form by applying a sequence of elementary row operations to its augmented matrix. The result is typically a matrix in row-echelon form, from which solutions can be obtained directly or by back substitution. For the fully reduced alternative, known as Gauss–Jordan elimination, the matrix is taken to reduced row-echelon form so that solutions are immediate.
Basic procedure and elementary operations
The standard routine has two phases: forward elimination and back substitution. Forward elimination eliminates variables in a stepwise fashion to produce an upper triangular (row-echelon) matrix. Back substitution then recovers the unknowns starting from the last equation. The three permitted elementary row operations are:
- Swap two rows.
- Multiply a row by a nonzero scalar.
- Add a scalar multiple of one row to another row.
Applied in sequence, these operations preserve the solution set of the system. In practice, one chooses a pivot entry in each column to eliminate the entries below it; if a pivot is zero, a row swap or pivoting strategy is needed. For an explicit algorithmic description see method overview or a numerical guide at numerical reference.
Variants, pivoting and numerical considerations
There are several common variants. Gauss–Jordan elimination continues elimination until each pivot is the only nonzero entry in its column, producing reduced row-echelon form. Pivoting strategies—partial (row) pivoting or complete (row and column) pivoting—are used to avoid division by small numbers and improve numerical stability when working in floating-point arithmetic. In floating-point implementations, partial pivoting is the standard compromise between cost and robustness.
Complexity and stability are important in applications: the straightforward algorithm requires on the order of n^3 arithmetic operations for an n×n system, and numerical round-off can affect accuracy. Techniques such as scaling, pivoting, iterative refinement, or using matrix factorizations like LU decomposition are often employed to control errors and reuse decomposition work for multiple right-hand sides. For relations to decompositions see related algorithms.
History and naming
The elimination ideas predate Carl Friedrich Gauss; procedures resembling Gaussian elimination appear in ancient Chinese mathematics, notably in The Nine Chapters on the Mathematical Art. The name honors Gauss because of his influential work and widespread use of the method in his writings, even though the algorithm itself was known earlier in various cultures. For historical context consult historical notes.
Applications and examples
Gaussian elimination is widely used in engineering, physics, computer science, and applied mathematics. Typical uses include solving linear systems arising from discretized differential equations, computing matrix inverses by augmenting with the identity matrix, and determining the determinant by multiplying pivot values (accounting for any row swaps). It also underpins many numerical linear algebra libraries and software.
A simple illustrative example: for a 2×2 system
- Form the augmented matrix from the coefficients and constants.
- Eliminate the lower-left entry by replacing the second row with itself minus a suitable multiple of the first.
- Use back substitution to find the unknowns.
When a system is singular, elimination reveals this by producing a row of zeros on the left with a nonzero entry on the right (inconsistent system) or a row of all zeros (dependent equations and infinitely many solutions). These outcomes make it a diagnostic tool as well as a solver. For more examples and step-by-step problems see worked examples.
Notable facts and practical tips
- Gaussian elimination and LU decomposition are closely related: Gaussian elimination without row swaps yields an LU factorization of the coefficient matrix.
- Determining rank, testing consistency, and computing nullspaces are natural extensions once the matrix is in (reduced) echelon form.
- In computational settings, specialized algorithms and hardware-aware implementations are used to improve performance for large systems.
Overall, Gaussian elimination is an essential algorithmic tool in linear algebra: conceptually simple, broadly applicable, and the foundation for more advanced numerical methods.