6

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.

grunet
  • 163
  • 5
  • 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 00: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 00:14
  • Are you looking for a numerical technique or a theoretical equivalence? – copper.hat Mar 29 '13 at 00:17
  • A numerical technique – grunet Mar 29 '13 at 00: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 00:22
  • Note one other easy check: skew symmetry. This requires (in the real case) all zero along the diagonal (easy first check) and that $a_{ij} = -a_{ji}$ for all $i$ and $j$. This is an example of a real only matrix that is not symmetric but still normal (the only other example for real only matrices, since real symmetric and real skew symmetric are the only two examples of normal matrices that are also real). – adam W Mar 29 '13 at 00:36
  • In general, you cannot check numerically. A matrix is diagonalizable if the eigenvalues are distinct. The set of diagonalizable matrices is dense, so if your original matrix is not diagonalizable, then even a tiny amount of numerical noise will render it diagonalizable. However, there are classes of matrices (normal springs to mind) for which you can check with reasonable confidence. – copper.hat Mar 29 '13 at 00:52

1 Answers1

5

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.

Chris Godsil
  • 13,703
  • 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 00:45
  • Cool! Thanks for the answer! – grunet Mar 29 '13 at 00:55
  • Not the characteristic polynomial the minimal polynomial. – Chris Godsil Mar 29 '13 at 03: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
  • Does simple mean not-complex/does not contain i? – User Oct 25 '14 at 19:51