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 AC0(GapL)
the AC0-closure of GapL,
and there is a coefficient which is hard for GapL.
Furthermore,
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.