Thanh Minh Hoang and Thomas Thierauf
Abstract:
We investigate the complexity of

computing the characteristic polynomial, the minimal polynomial,
and all the invariant factors of an integer matrix,
and of

verifying them, when the coefficients are given as input.
It is known that each coefficient of the characteristic polynomial
of a matrix A is computable in GapL,
and the constant term, the determinant of A,
is complete for GapL.
We show that the verification
of the characteristic polynomial is complete for complexity class C=L
(exact counting logspace).
We show that each coefficient of the minimal polynomial of a matrix A
can be computed in AC^{0}(GapL)
the AC^{0}closure of GapL,
and there is a coefficient which is hard for GapL.
Furthermore,
the verification of the minimal polynomial
is in AC^{0}(C=L) and is hard for C=L.
The hardness result extends to
(computing and verifying) the system of
all invariant factors of a matrix.