<p>You can do this in uniform NC, see:</p>

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

CC BY-SA 3.0
2013-07-17T09:11:34.200Z
2013-07-17T09:11:34.200Z
Markus Bläser
<p>Given an $n\times n$ matrix $A$ with rational entries. What's the complexity to check $A$ is diagonalizable?</p>

<p>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?</p>

<p>Any guidance/comment is welcome! Thanks. </p>

CC BY-SA 3.0
2013-07-11T13:15:27.190Z
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
CC BY-SA 3.0
2013-07-11T13:54:56.577Z
@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
CC BY-SA 3.0
2013-07-11T15:37:59.157Z
@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
CC BY-SA 3.0
2013-07-11T15:46:52.070Z
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](http://dx.doi.org/10.1016/S0024-3795(97)80005-5), by Daniel Augot and Paul Camion.
Bruno
CC BY-SA 3.0
2013-07-12T02:22:46.340Z
You can compute the Jordan canonical form of a rational matrix in polynomial time: http://www.worldscientific.com/doi/abs/10.1142/S0129054194000165
Robin Kothari
<cc.complexity-theory><linear-algebra><matrices>
What's the complexity to check whether a matrix is Diagonalizable?
amatrix
# What's the complexity to check whether a matrix is Diagonalizable?

(Asked by: username_0 on 2013-07-11)

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.

**Tags:** cc.complexity-theory, linear-algebra, matrices

> **Comments:**
> **username_1**: 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.  
> **username_2**: @username_1 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.  
> **username_1**: @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...  
> **username_1**: 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](http://dx.doi.org/10.1016/S0024-3795(97)80005-5), by Daniel Augot and Paul Camion.  
> **username_3**: You can compute the Jordan canonical form of a rational matrix in polynomial time: http://www.worldscientific.com/doi/abs/10.1142/S0129054194000165  

---

## 1 answers

### Answer by username_4 on 2013-07-17. Score: 8 | Accepted answer

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>


---

