Are there any good tools to understand the movement of roots of polynomials in single variable with real or rational coefficients? That is say the coefficients are of the form $a_{i} + M b_{i}$ where $i$ coefficient index and the sets of numbers $a_{i}$ and $b_{i}$ for all $i$ need not be distinct but are fixed and $M$ is the parameter that varies. Is there a good tool to study when some of the roots turn positive for some $M \in \mathbb{Z}_{+}$ and $M$ bounded by some number $K$ and in an efficient way preferably in time $O(\log^{k}(K))$ for some $k > 0 \in \mathbb{R}$)?
$\begingroup$
$\endgroup$
8
-
$\begingroup$ A real root hits $0$ when the $0$'th coefficient $a_0 + M b_0 = 0$. Or are you talking about the real parts of complex roots? $\endgroup$– Robert IsraelJun 27, 2012 at 2:31
-
1$\begingroup$ Maybe I misunderstand the question, but if you have fixed polynomials $f(x),g(x)$ and want to know where are the positive roots of $f+Mg$, then you need $M = -f(x)/g(x)$ and you just want to see the values of $-f(x)/g(x)$ for $x>0$. This is just calculus. $\endgroup$– Felipe VolochJun 27, 2012 at 3:07
-
$\begingroup$ I think you are talking about the root locus technique in control theory. en.wikipedia.org/wiki/Root_locus $\endgroup$– Dan PetersenJun 27, 2012 at 3:20
-
$\begingroup$ corrected the question $\endgroup$– TurboJun 27, 2012 at 17:27
-
$\begingroup$ To expand on Felipe Voloch's "just calculus", you just need find which of the critical points of $-f/g$ are in the positive real axis, and the value at $f=0$ as well as the limit as $f\to \infty$. The number of positive roots of the polynomial cannot change unless $M$ moves through one of these values, so by counting positive roots in each interval between two values you divide $[-K,K]$ into $O(1)$ intervals and can count the roots on each interval. $\endgroup$– Will SawinJun 28, 2012 at 15:19
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
If Robert Israel is correct that you are talking about real parts of complex roots, then you can do the following, to test for an imaginary root:
If $z$ is an imaginary root, then so is $-z$, so $x^2-z^2$ divides the polynomial. This means that $z^2$ is a root of two different polynomials: the "even" polynomial $a_0+Mb_0+(a_2+Mb_2)x+(a_4+Mb_4)x^2\dots $ and the "odd" polynomial $a_1+Mb_1+(a_3+Mb_3)x+(a_5+Mb_5)x^2+\dots$
So, a necessary condition is that the resultant of these two polynomials be $0$. This will be a polynomial in $M$, which you can solve explicitly. For each real root of $M$ you then have to check that the root shared by the even and odd polynomials is a negative real number, or, equivalently, check that the original polynomial has an imaginary root. But you only have to check that for finitely many values of $M$, the roots of the resultant, so it's not too bad.
The resultant could be identically $0$. This implies that there are always two roots that sum to $0$, so some polynomial in $\mathbb C[M]$ with no odd coefficients divides the original polynomial. This can only happen if the polynomial reduces in $C[M]$ into one constant factor and one factor with linear coefficients, in which case you just repeat for the factor with linear coefficients, or if all the odd coefficients are $0$, in which case you can write the polynomial as $f_M(x^2)$ and imaginary roots are just negative real roots of $f_M$.
So the resultant gives a method to solve the problem. This may or may not be the best way to go about it.
answered Jun 27, 2012 at 3:14