Engineering / Mathematics — Polynomial Algorithms
Computing Minimal Polynomials in Quotient Algebras
Finding the minimal polynomial of an element of a polynomial quotient algebra by linear algebra on its powers.
Executive summary
The minimal polynomial of an element is the least-degree monic polynomial annihilating it. In a finite-dimensional algebra it is found by detecting the first linear dependence among successive powers.
The direct method costs cubic time; the linearly generated sequence approach is faster and connects to Berlekamp-Massey.
Learning objectives
- Define the minimal polynomial of an algebra element.
- Compute it by linear algebra on powers.
- Compare with the sequence-based approach.
01Definition and existence
Minimal polynomial of an element
For α in a finite-dimensional F-algebra A, the minimal polynomial is the monic generator of the ideal {g ∈ F[X] : g(α) = 0}.
Existence follows from finite dimension: the powers 1, α, α², ... cannot all be independent in a space of dimension n, so a dependency appears by the n-th power at the latest. That dependency is a polynomial relation.
Degree bound
The minimal polynomial of an element of an n-dimensional algebra has degree at most n.
02The direct method
Minimal polynomial by linear algebra
element α of an n-dimensional algebrathe minimal polynomial of α- Represent 1, α, α², ... as coordinate vectors in the algebra's basis.
- Form a matrix whose rows are these vectors, adding one power at a time.
- After each addition, test whether the new row is dependent on the previous ones.
- At the first dependency, the coefficients of the linear relation are the coefficients of the minimal polynomial.
- Normalise to make it monic and return.
O(n³) field operationsIncremental elimination avoids recomputing from scratch: each new power is reduced against the existing echelon rows, and a zero result signals the dependency along with its coefficients.
03The sequence-based method
A faster route projects the powers onto a linear functional, producing a scalar sequence whose minimal linear recurrence has the same characteristic polynomial as the element with high probability.
Choose a random functional
A random linear map from the algebra to F.
Generate the sequence
Apply the functional to successive powers of α, giving scalars s₀, s₁, s₂, ...
Find the minimal recurrence
Run Berlekamp-Massey on the first 2n terms.
Verify
Check that the resulting polynomial annihilates α; if not, retry with a fresh functional.
- Direct linear algebra
O(n³)Deterministic; forms the full power matrix - Sequence method
O(n²) plus n multiplicationsRandomised; needs verification
The sequence method is randomised because a badly chosen functional can produce a recurrence of smaller degree than the true minimal polynomial. Verification is cheap — one evaluation — so a failed attempt costs little and retrying is inexpensive.
This is the same machinery as sparse linear system solving by block Wiedemann, and the same Berlekamp–Massey algorithm serves both.
04Frequently asked questions
How does the minimal polynomial differ from the characteristic polynomial?
The minimal polynomial divides the characteristic polynomial and has the same irreducible factors, but with possibly smaller multiplicities. They coincide exactly when the module is cyclic over F[X].
Why might the random functional fail?
Because the projection can lose information, producing a sequence satisfying a shorter recurrence than the element does. The probability is small for a random choice, and verification catches every failure.
What if the algebra is not commutative?
The construction still works for a single element, since the subalgebra it generates is commutative. The minimal polynomial of a matrix is exactly this construction applied in the matrix algebra.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 401-402.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.