ON THE MINIMAL POLYNOMIAL OF A MATRIX
Thanh Minh Hoang, Thomas Thierauf · International Journal of Foundations of Computer Science · 2004
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 AC0(C=L), the AC0-closure ofC=L.