Linear Algebra Algorithms
Gaussian Elimination and Linear Systems
Exact Gaussian elimination, pivoting for entry growth rather than stability, and the fraction-free Bareiss variant.
Engineering / MathematicsLinear Algebra Algorithms2 min readKV-MATH-0529
Gaussian elimination over an exact domain follows the familiar shape but is tuned for entirely different reasons. Over the reals pivoting controls rounding error; over the integers there is no rounding error, and pivoting controls entry growth instead.
The procedure
Gaussian elimination
- Select a pivotChoose a non-zero entry in the current column.
- SwapMove it to the diagonal position.
- EliminateSubtract multiples of the pivot row from the rows below to zero the column.
- RecurseRepeat on the remaining submatrix.
- Back-substituteSolve the resulting triangular system.
Pivoting for exact arithmetic
| Domain | Pivot choice | Reason |
|---|---|---|
| Floating point | Largest magnitude | Numerical stability |
| Integers | Smallest non-zero magnitude | Limits entry growth |
| Finite field | Any non-zero | No growth; choose for sparsity |
| Sparse | Fewest non-zeros in row and column | Limits fill-in |
Fraction-free elimination
Ordinary elimination over the integers introduces fractions. The Bareiss method avoids them by dividing each new entry by the previous pivot — a division that is provably exact.
Rank and consistency
Elimination determines the rank as the number of pivots found. A system is inconsistent exactly when elimination produces a row that is zero except in the constant column.
Cost
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.2.2. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.