# Determining if a Matrix is Diagonalizable without computing Eigenvalues

Is there any simple way to determine if a matrix is diagonalizable without having to compute eigenvalues?

I'm motivated by the idea that for $\mathbb{R}^n$, to determine if a matrix is diagonalizable via an orthogonal transformation, you just need to check if it's symmetric. Also, for $\mathbb{C}^n$, to determine if a matrix is diagonalizable via a unitary transformation, you just need to check if it's normal. So I'm just curious if one can drop the orthogonal/unitary requirements while still having an easy method to check if a matrix is diagonalizable.

-
I remember trying to figure this out a while ago. In the general case the best I was able to find was that the geometric multiplicity and algebraic multiplicity of the eigenvalues must be the same. Of course you have to compute the eigenvalues for this. Unless you have some additional structure on the matrix, like symmetry, I don't think we can do better –  Wintermute Mar 29 '13 at 0:12
I disagree with mtiano. A matrix is normal if, and only if it is unitarily diagonalizable. One would think that dropping unitarily would lead to something treatable. One the other hand if there was such a (known) criteria it would surely be well known. I think I agree with mtiano after all. –  Git Gud Mar 29 '13 at 0:14
Are you looking for a numerical technique or a theoretical equivalence? –  copper.hat Mar 29 '13 at 0:17
A numerical technique –  guest Mar 29 '13 at 0:18
What are you meaning when you say numerical technique? I think guest might be saying he wants an algorithm, not actual numerical procedure. –  Git Gud Mar 29 '13 at 0:22

A matrix is diagonalizable over $\mathbb{R}$ if and only if all zeros of its minimal polynomial are simple. If the minimal polynomial is $f(t)$, its zeros are simple if and only if the gcd of $f(t)$ and its derivative $f'(t)$ is $1$.

So the problem is to compute the minimal polynomial. The obvious approach is to compute the rational canonical form (also called the Frobenius normal form). The key properties of this are that it can be computed over $\mathbb{R}$, and that it does not require any information about the eigenvalues.

-
So first find the characteristic polynomial then take gcd of that with the derivative? Sounds simple enough... definitely something that stays within the reals at least. And probably the best possibility that the OP is going to find in my opinion. –  adam W Mar 29 '13 at 0:45
Cool! Thanks for the answer! –  guest Mar 29 '13 at 0:55
Not the characteristic polynomial the minimal polynomial. –  Chris Godsil Mar 29 '13 at 3:16
Oh, talking to me. I am just trying to understand how practical calculating the minimal polynomial is. I am thinking the real answer for the OP is--it is not simple beyond the symmetric and skew symmetric cases (general normal if complex). Especially if dealing with floating point. If I am understanding correctly, precision error basically makes it very unlikely that the minimal polynomial differs form the characteristic polynomial. copper.hat's comment says as much I believe. So this answer may have been good for the OP to have something to study, but... I like their question anyway. –  adam W Mar 29 '13 at 14:54
@adam W: It's not practical to compute minimal polynomials by hand, but there is good code around for doing it. Sage has it, to give one example. I do not think there are numerical issues. Note that in computing with adjacency matrices of graphs (for example) it is quite common for the characteristic and minimal polynomials to differ. –  Chris Godsil Mar 29 '13 at 15:47