The Complexity of the Minimal Polynomial

We show that the computation of the minimal polynomial is in AC⁰(GapL), the AC⁰-closure of the logspace counting class GapL, which is contained in NC². Our main result is that the problem is hard for GapL (under AC⁰ many-one reductions). The result extends to the verification of all invariant factors of an integer matrix.

Furthermore, we consider the complexity to check whether an integer matrix is diagonalizable. We show that this problem lies in AC⁰(GapL) and is hard for AC⁰(C=L) (under AC⁰ many-one reductions).