# What's the complexity to check whether a matrix is Diagonalizable?

Given an $n\times n$ matrix $A$ with rational entries. What's the complexity to check $A$ is diagonalizable?

I suspect that this can be done in P, but I do not know any reference. However, a more interesting question is, is there any better complexity class to capture this problem?

Any guidance/comment is welcome! Thanks.

• By computing and factoring the characteristic polynomial, you can check in polynomial time whether the matrix is diagonalizable. I do not know better bounds for this problem. – Bruno Jul 11 '13 at 13:15
• @Bruno are you assuming that a matrix is diagonalizable iff it has distinct eigenvalues? This it not true, it is a sufficent but not necessary condition. An identity matrix is a counterexample. – Tyson Williams Jul 11 '13 at 13:54
• @TysonWilliams: I was assuming the equivalent fact that a matrix is diagonalizable iff its characteristic polynomial is a product of distinct linear factors. Of course, the equivalence does not hold for the characteristic polynomial but the minimal polynomial... – Bruno Jul 11 '13 at 15:37
• To compensate my mistake, here is a reference for a polynomial time algorithm to compute the minimal polynomial, from which you easily obtain (or extract) an algorithm for checking diagonalizability: On the computation of minimal polynomials, cyclic vectors, and frobenius forms, by Daniel Augot and Paul Camion. – Bruno Jul 11 '13 at 15:46
• You can compute the Jordan canonical form of a rational matrix in polynomial time: worldscientific.com/doi/abs/10.1142/S0129054194000165 – Robin Kothari Jul 12 '13 at 2:22

You can do this in uniform NC, see:

G. Villard. Fast parallel algorithms for matrix reduction to canonical forms. AAECC 8:511-537, 1997. http://link.springer.com/article/10.1007%2Fs002000050089