Exact linear algebra is a different discipline from numerical linear algebra
Over a field, Gaussian elimination solves systems, computes determinants and finds kernels in cubic time. Over ℤ or over a polynomial ring the same algorithm is correct but disastrous: entries grow exponentially unless divisions are managed. Fraction-free elimination keeps every intermediate an integer with a provable size bound, and modular methods sidestep growth entirely by computing modulo several primes and reconstructing.
Learning objectives
- Perform exact Gaussian elimination with correct pivoting.
- Explain intermediate expression swell and the Bareiss remedy.
- Choose between fraction-free and modular determinant algorithms.
- Compute a characteristic polynomial without symbolic determinant expansion.
- Compute kernels and images over a field.
Section 01Elimination and pivoting
Elimination reduces a matrix to echelon form by row operations. Over an exact field the only requirement on the pivot is that it be non-zero — there is no numerical stability concern, because there is no rounding.
Numerical linear algebra chooses the largest pivot to limit rounding. Exact linear algebra chooses the smallest non-zero pivot, or the sparsest row, because the objective is to limit coefficient growth and fill-in. Importing a numerical pivoting strategy into exact code is a common and costly mistake.
| Operation | Cost | Notes |
|---|---|---|
| Solve a square system | O(n3) | Elimination then back-substitution |
| Determinant | O(n3) | Product of pivots, with a sign from row swaps |
| Inverse | O(n3) | Rarely needed; solving is almost always preferable |
| Kernel | O(n3) | Reduced echelon form, then read off free variables |
| Characteristic polynomial | O(n3) | Via Hessenberg reduction; naive symbolic expansion is far worse |
Section 02Coefficient growth and fraction-free elimination
Applied over ℤ, ordinary elimination produces rationals whose numerators and denominators grow at every step; the number of digits can double repeatedly. The Bareiss one-step algorithm avoids this by dividing each new entry by the previous pivot — a division that is provably exact.
Every intermediate entry is a minor of the original matrix, so Hadamard's bound applies: entries never exceed the size of an n×n minor. Growth is controlled, not merely reduced.
Single-pass, deterministic, entries bounded by Hadamard. Best for small to medium dense integer matrices and when the exact intermediate structure is wanted.
Compute modulo several word-size primes and reconstruct by CRT. All arithmetic is single-precision and trivially parallel. Best for large matrices; needs an a priori bound and must detect unlucky primes.
Section 03Determinants and characteristic polynomials
The determinant of an integer matrix is best obtained by whichever of the two strategies above fits the size. Hadamard's bound supplies the number of primes needed in the modular case:
The characteristic polynomial must not be computed by expanding det(xI − A) symbolically — the intermediate polynomials are dense and the cost is prohibitive. Two practical routes exist.
Hessenberg reduction
Reduce to upper Hessenberg form by similarity transformations, then apply the recurrence for the characteristic polynomial of a Hessenberg matrix. Cubic and numerically clean.
Interpolation
Evaluate det(xiI − A) at n+1 integer points and interpolate. Each evaluation is an ordinary determinant; the method parallelises and combines well with modular arithmetic.
Krylov / Danilevsky
Build a Krylov sequence to reach a companion-form similarity. Fast but requires care when the sequence degenerates.
Section 04Kernel, image and rank
Reduced echelon form yields all three at once. The pivot columns of the original matrix form a basis of the image; the free columns parameterise the kernel; the number of pivots is the rank.
A matrix of full rank over ℚ can drop rank modulo an unlucky prime. Modular rank computations therefore give a lower bound on the true rank, correct with high probability but not with certainty. When rank must be certified, either verify with a second prime or work over ℤ directly.
Over ℤ the correct notion is not the echelon form but the Hermite normal form, which respects the module structure rather than merely the linear span. Kernels of integer matrices should be computed by HNF or by LLL, never by clearing denominators after rational elimination.
ReferenceFrequently asked questions
Why not just use floating point?
Because the results feed algorithms that require exactness. A determinant that is nearly zero is not the same as a determinant that is zero, and a rank determined by a numerical threshold is a guess. In this domain the input is exact and the output must be too.
When is the matrix inverse actually needed?
Almost never. Solving Ax = b directly is faster and better conditioned than forming the inverse and multiplying. Explicit inverses are justified only when the same matrix is applied to very many right-hand sides that are not available together.
How large can integer matrices get before modular methods win?
It depends on entry size as much as dimension, so the crossover must be measured. As a rough guide, once the product of dimension and entry bit length pushes intermediate entries past a few machine words, the multi-modular approach starts to dominate.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.