Condition for degenerate eigenvalues for a matrix

Given a diagonalizable matrix $M$ (that is, a normal matrix), can we determine whether the matrix has degenerate eigenvalues without explicitly calculating all the eigenvalues and eigenvectors?

1) An example that came to my mind is that $M$ is square of a skew-Hermitian matrix since a skew-symmetric matrix always has pairs of pure imaginary eigenvalues $\pm i \lambda_i$. Similarly, a matrix that is square of a matrix that has pairs of eigenvalues with different signs such as $\lambda_1,-\lambda_1,\dots$ is such a case. However, these things require sorts of decomposition of the matrix $M$, which is another problem!

2) Another way is calculating the characteristic polynomial $det(M-\lambda I)=0$ and factorize it, then check the degrees of each terms. But this amounts to calculating all the eigenvalues already.

Do we have other (simple) criteria or ways to determine the degeneracy of eigenvalues of a matrix $M$?

• Do you know a way to determine if a polynomial has degenerate roots? – DisintegratingByParts May 9 '14 at 2:44
• Good question! If the determinant of $A - \lambda I$ is sufficiently easy to compute, then there are several criteria for root multiplicity. For example a polynomial $p(x) \in F \left[ x \right]$ ($F$ being a field) has a multiple root if and only if $p(x)$ and $p'(x)$ (being the derivative) have a nontrivial common factor. This among other criteria could help one determine degeneracy, but only if we desire to compute the characteristic polynomial. I would love to know if there are general ways of determining this without doing so. – o0BlueBeast0o May 9 '14 at 3:34

Eneron, you speak about repeated eigenvalues. That has nothing to do with normal matrices. Moreover a normal matrix is a matrix that is diagonalizable in an ORTHONORMAL basis, that is a very important detail, because a generic complex matrix is "always" diagonalizable but is "never" normal !

Of course, ooBlue gave a good answer. The calculation of $P=\chi_A$, the characteristic polynomial of $A$, has complexity in $O(n^3)$. After, you calculate $Q=gcd(P,P')$. If $degree(Q)\geq 1$ then we have at least one repeated eigenvalue ; note that, along the calculation, we remain in the base field of the entries of $A$. In fact, there is eventually a problem ; the calculation of a polynomial $gcd(P,P')$ is very unstable and, eventually, we can be faced with calculations involving many digits.

EDIT: Hi guys, I see that you read my post ; it's funny. For the sake of brevity, enzotib and Nicholas are over the real field and I am over the complex field.

Now we do mathematics (seriously). The OP speaks about a normal matrix with a reference to wikipedia ; if you read this reference (do it), then you see that $A$ is a COMPLEX matrix. Moreover the OP speaks about a skew- hermitian matrix with a reference to wikipedia ; if you read this reference (do it), then you see that we talk about COMPLEX matrices. The notion of generic matrix is linked to the notion of Zariski-dense set. I don't want to speak about Zariski topology. That is important is that if $A=[a_{i,j}]$ is a generic matrix, then there are no polynomials with coefficients in $\mathbb{Q}$ linking the $(a_{i,j})$. In particular, the discriminant of the characteristic polynomial of $A$ is a polynomial with rational coefficients linking the $(a_{i,j})$ ; thus this discriminant is not $0$ and $\chi_A$ has distinct COMPLEX roots. Then $A$ is diagonalizable over $\mathbb{C}$ and we are done. Sorry guys! Note that if we don't want to know the repeated eigenvalues of $A$, then we can replace the calculation of $gcd(P,P')$ with the calculation of $discrim(P)$.

Now let $A$ be a $(n\times n)$ real matrix ; $\mathbb{R}$ is not algebraically closed and, consequently, if you randomly choose $A$, then the probability that $A$ is diagonalizable over $\mathbb{R}$ tends to $0$ when $n$ tends to $\infty$. Thus, to say that a real matrix is in general not diagonalizable over $\mathbb{R}$ is not a scoop ! Yet, if a real matrix $A$ is generic, then it is diagonalizable over $\mathbb{C}$. In such a case, we say that $A$ is semi-simple. I want to insist on this important remark: to say that a real matrix $A$ is not diagonalizable (over $\mathbb{R}$) has not any interest ; on the contrary, to say that $A$ is semi-simple can be interesting ; for instance, the dimension of the commutants over $\mathbb{R}$ and over $\mathbb{C}$ of $A$ have same dimension and it suffices to diagonalize $A$ over $\mathbb{C}$. To complete this edit, note that a real generic matrix can be diagonalized in blocks of dimension $1$ (for the real eigenvalues) and in blocks of dimension $2$ (for the conjugate eigenvalues).

• It is not true that a generic complex matrix is always diagonalizable, the best you can do is Jordan Normal Form. The downvote is not mine. – enzotib May 9 '14 at 12:51
• And even Jordan Normal Form requires that $\chi_A$ splits over the field $K$, if $A \in Mat_n(K)$. Really, you can't even expect Jordan Normal Form unless you pass to the algebraic closure of $K$. – Nicholas Stull May 9 '14 at 14:59
• @Loupblanc, given $A=\left( \begin{matrix} 1&1\\ 0&1 \end{matrix} \right)$, which $P$ gives a diagonal matrix $D=P^{-1}AP$? – enzotib May 9 '14 at 19:00
• enzotib, your $A$ is not a generic matrix because $a[1,1]-a[2,2]=0$, a polynomial with coefficients in $\mathbb{Q}$. In particular, the $(a_{i,j})$ must be algebraically independent over $\mathbb{Q}$. – loup blanc May 9 '14 at 20:01
• Sorry, I was thinking that "generic" was an english word, without a precise mathematical meaning. I have no knowledge of what is a Generic Matrix, nor I found references around. – enzotib May 9 '14 at 20:22