Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we have a polynomial function $f(z)=a_0+a_1z+a_2z^2+...+z^n$ with each $a_i$ between 0 and 1. Is there a method to determine if $f$ has a pair of complex conjugate roots?

There are many results on radius of roots, but I never see similar facts concerning the question here.

share|improve this question
20  
What are you guys talking about? The question is whether the roots are all real. An explicit method is based on Sturm's theorem, which is a non-trivial answer. Who is to say whether this is "homework"? Who assigns homework over Christmas break? –  Greg Kuperberg Dec 20 '09 at 18:15
2  
Agree with Greg. We perhaps should not jump to conclusions too quickly even if the question is from "unknown". –  Hailong Dao Dec 20 '09 at 18:58
5  
While this isn't homework, it is a question that is hard to answer briefly. As others have noted, a real polynomial either has all roots real or else has a pair of complex conjugate roots. The condition on the coefficients is useless: For any polynomial $f=x^d+\ldots$, the roots of $f$ are real if and only if the roots of $f(Nx)/N^d$ are and the coefficients of the latter polynomial can be made as small as we want. So the question is really "when are all the roots of a polynomial real?" This question doesn't have a clean answer; keywords are "Sturm's theorem", "discriminant." –  David Speyer Dec 20 '09 at 20:20
1  
George, there's also the transformation that sends the polynomial $f(x)$ to $f(x+a)$, so you can further simplify the situation. –  Ryan Budney Dec 20 '09 at 22:23
2  
Hmm, I was pretty ready to answer "when all the roots are real." This is definitely a question the questioner should have thought out more clear (which is probably in part why a couple people jumped to call it homework). –  Ben Webster Dec 21 '09 at 3:19

3 Answers 3

We can assume $f$ has no multiple root (if the gcd of $f$ and $f'$ is not constant, divide by this gcd). Let $n$ be the degree of $f$. Compute $$\frac{f(X)f'(Y)-f(Y)f'(X)}{X-Y} = \sum_{i,j=i}^{n}a_{i,j}\; X^{i-1}\; Y^{j-1}\;.$$ Then $f$ has all roots real iff the symmetric matrix $(a_{i,j})_{i,j=1,\ldots,n}$ is positive definite. This can be checked for instance by computing the principal minors of this matrix and verifying whether they are all positive.

There are several methods for computing the number of real roots using signature of quadratic form : see for instance this note (in french).

share|improve this answer

Let $f$ be the polynomial in question and let $g$ be $f$ divided by the gcd of $f$ and $f'$. Use Sturm's theorem http://en.wikipedia.org/wiki/Sturm_theorem to compute the number of real roots of $g$ between $-n-1$ and $n+1$. The result is equal to $\deg g$ if and only if all roots of $g$ (and also of $f$) are real.

share|improve this answer

It's not clear to me what sort of answer you want - a practical method or a definitive algorithm? Also, I'm not sure how to make use of the assumption on the coefficients.

One thing to observe is that if $f'(z)$ has a complex root, then so does $f(z)$ by the Gauss-Lucas Theorem. Taking the discrminant of $f^{(n-2)}(z)$, we get a quick criterion for there to be a complex root: $$(n-1) a_{n-1}^2 < 2n a_{n-2}.$$

share|improve this answer
1  
That's necessary, but not sufficient. Generalizing this argument, you can get en.wikipedia.org/wiki/Newton%27s_inequalities , which are still not sufficient. –  David Speyer Dec 20 '09 at 20:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.