Linear Algebra Algorithms
The Characteristic Polynomial and the Hessenberg Method
Computing the characteristic polynomial via Hessenberg reduction, and its role in producing minimal polynomials of algebraic numbers.
Engineering / MathematicsLinear Algebra Algorithms2 min readKV-MATH-0532
The characteristic polynomial of the multiplication matrix of an algebraic number is its field polynomial, from which the minimal polynomial follows. This makes the computation a routine operation in number field work rather than a specialist one.
Why not expand the determinant
Hessenberg reduction
Reduce the matrix to upper Hessenberg form — zero below the first subdiagonal — by similarity transformations, which preserve the characteristic polynomial. The polynomial of a Hessenberg matrix then satisfies a clean recurrence over the leading principal submatrices.
Characteristic polynomial by Hessenberg reduction
- Reduce to HessenbergUse similarity transformations to zero entries below the subdiagonal.
- Set up the recurrenceExpress the characteristic polynomial of each leading submatrix in terms of smaller ones.
- EvaluateRun the recurrence to obtain the coefficients.
Alternatives
Modular plus CRT
Compute the polynomial modulo several primes and reconstruct coefficientwise. Bounds on the coefficients come from Hadamard-type estimates.
Krylov methods
Build the sequence of images of a vector under repeated multiplication and solve for the dependency. Yields the minimal polynomial of the vector, which divides the minimal polynomial of the matrix.
Danilevsky
Reduce to companion form directly. Faster but breaks down when a required pivot vanishes, needing a case split.
From characteristic to minimal polynomial
For an algebraic number in a field of degree n, the characteristic polynomial of its multiplication matrix has degree n and is a power of the minimal polynomial. Dividing out the repeated factors — via squarefree factorisation — recovers the minimal polynomial.
Trace and norm
Two coefficients are individually meaningful: the trace is the negative of the coefficient one below the leading term, and the norm is the constant term up to sign. Both can be computed directly and more cheaply when the full polynomial is not required — see trace and norm.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.2.4. 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.