Linear Algebra Algorithms
Determinant Computation Strategies
Computing exact determinants by fraction-free elimination, modular methods with Hadamard bounds, and how to choose between them.
Engineering / MathematicsLinear Algebra Algorithms2 min readKV-MATH-0531
The determinant is needed for discriminants, lattice volumes and index computations. Computing it exactly is a good illustration of the tension between operation count and coefficient growth.
Three strategies
| Strategy | Approach | Best when |
|---|---|---|
| Fraction-free elimination | Bareiss; the final pivot is the determinant | Small matrices, moderate entries |
| Modular with CRT | Compute modulo several primes, reconstruct | Larger matrices; entries bounded by Hadamard |
| Characteristic polynomial | Constant term of the characteristic polynomial | When the polynomial is wanted anyway |
The Hadamard bound
Modular reconstruction needs to know in advance how many primes are required. Hadamard's inequality bounds the determinant by the product of the Euclidean norms of the rows.
The modular method
Modular determinant computation
- BoundCompute the Hadamard bound and double it.
- Choose primesSelect primes whose product exceeds the bound.
- Reduce and eliminateCompute the determinant modulo each prime by ordinary elimination — no growth.
- ReconstructApply CRT and map to the signed range.
Singular and unlucky cases
Applications
Determinants appear as the discriminant of an order, via the discriminant computation; as the volume of a lattice, via the lattice determinant; and as the index of one module in another, which is how maximality is verified in the Round 2 algorithm.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.2.3. 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.