Thanh Minh Hoang and Thomas Thierauf
We investigate the complexity of
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).
computing the characteristic polynomial, the minimal polynomial,
and all the invariant factors of an integer matrix,
verifying them, when the coefficients are given as input.
We show that each coefficient of the minimal polynomial of a matrix A
can be computed in AC0(GapL)
the AC0-closure of GapL,
and there is a coefficient which is hard for GapL.
the verification of the minimal polynomial
is in AC0(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.