13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bruno Jul 11 '13 at 13:15
  • 7
    $\begingroup$ @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. $\endgroup$ – Tyson Williams Jul 11 '13 at 13:54
  • $\begingroup$ @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... $\endgroup$ – Bruno Jul 11 '13 at 15:37
  • 4
    $\begingroup$ 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. $\endgroup$ – Bruno Jul 11 '13 at 15:46
  • 3
    $\begingroup$ You can compute the Jordan canonical form of a rational matrix in polynomial time: worldscientific.com/doi/abs/10.1142/S0129054194000165 $\endgroup$ – Robin Kothari Jul 12 '13 at 2:22
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.