When does a higher order polynomial have complex roots?

I try to say it all in the title.

I'm wondering under what conditions a matrix will have complex eigenvectors and eigenvalues. That question, I think, reduces to whether the characteristic polynomial has complex roots.

So, how do I know when a very high order polynomial has complex roots?

(Perhaps it's obvious that I don't know much about analysis.)

-

Well, every polynomial of degree $n \geqslant 1$ has at least one complex zero by the fundamental theorem of algebra. When $n = 2$ you can look at the discriminant. For $n > 2$ it depends. If you can reduce it to $n = 2$ via substitution then you can again look at the discriminant. In general, if a polynomial has real coefficients, then either all roots are real or there is an even number of non-real complex roots because non-real complex roots come in conjugate pairs. That is all we can say. We also know that if a matrix is symmetric i.e. $A = {A^T}$ or Hermitian i.e. $A = {A^H}$ where $H$ denotes the conjugate transpose, then it must have real eigenvalues if it is neither then it depends on the matrix. So we can say that a matrix $A$ could have complex eigenvalues only when it is not symmetric and not Hermitian.
I think Sturm's theorem for finding real roots might be of use. Also, if the polynomial has all real coefficients, the complex roots come in complex conjugate pairs. Also$^2$, there is somebody's root-squaring method which might be relevant. –  marty cohen Oct 24 '12 at 21:28