On the minimal polynomial of a matrix
We investigate the complexity of the degree and the constant term of the minimal polynomial of a matrix. We show that the degree of the minimal polynomial is computationally equivalent to the matrix rank. We compare the constant term of the minimal polynomial with the constant term of the characteristic polynomial. The latter is known to be computable in the logspace counting class GapL. We show that if this holds for the minimal polynomial as well, then the exact counting in logspace class C=L is closed under complement. Whether C=L is closed under complement is one of the main open problems in this area. As an application of our techniques we show that the problem of deciding whether a matrix is diagonalizable is complete for AC(0)(C=L), the AC(0)-closure of C=L.
minimal polynomial logspace counting class linear algebra