I have come across the following interesting problem: let $p,q$ be polynomials over the field of real numbers, and let us suppose that their coefficients are all integer (that is, there is a finite exact representation of these polynomials). If needed, we may suppose that the degree of both polynomials is equal. Let us denote by $x_p$ (resp. $x_q$) the greatest absolute value of some (real or complex) root of the polynomial $p$ (resp. $q$). Is the property $x_p = x_q$ decidable?
If not, does this property hold for some restricted families of polynomials? In the context from which this problem arises, the polynomials are characteristic polynomials of matrices, and their roots are eigenvalues.
I am aware of some numerical algorithms for computing roots of polynomials / eigenvalues, however these seem to be of no use here, since the output of these algorithms is only approximate. It seems to me that computer algebra might be useful here, however, unfortunately, I do not have almost any knowledge in that field.
I am not searching for a detailed solution to this problem, however any intuition and ideas where to search for the solution would be helpful.
Thank you in advance.
Asked By : 042
Answered By : Gilles
I'm not knowledgeable in that field either, but I think I can provide a non-constructive answer.
The first-order theory of real closed fields is decidable. Your problem can be stated as a system of algebraic equations and inequations over the real algebraic numbers. Consider $2 (\deg P + \deg Q)$ variables $x_1,\ldots,x_{\deg P}, y_1,\ldots,y_{\deg P}, x'_1,\ldots,x'_{\deg P}, y'_1,\ldots,y'_{\deg P}$. You want to know whether the following system is satisfiable: $$\begin{align*} P(x_j+i\,y_j) &= 0 & \text{for \(1 \le j \le \deg P\)} \\ Q(x'_k+i\,y'_k) &= 0 & \text{for \(1 \le k \le \deg Q\)} \\ x_j^2 + y_j^k &\le x_1^2 + x_2^2 & \text{for \(2 \le j \le \deg P\)} \\ x'_j^2 + y'_j^k &\le x'_1^2 + x'_2^2 & \text{for \(2 \le k \le \deg Q\)} \\ x_1^2 + y_1^2 = x'_1^2 + y'_1^2 \\ \end{align*}$$
The first two equation families express that the $x_j+i\,y_j$ and $x'_k+i\,y'_k$ are roots of the polynomials, the next two inequation families express that $x_1+i\,y_1$ and $x'_1+i\,y'_1$ have the largest absolute value, and the last inequation compares these largest absolute values.
It is decidable whether this system is satisfiable: your problem is decidable. However, this statement is probably not the most efficient way to go about it.
A more useful answer probably involves the theory of Gröbner bases. If you're trying to solve that problem for yourself, I think reading the first few chapters of any computational algebra book will give you the requisite background. If you're just aiming to solve your underlying problem, there is probably an off-the-shelf algorithm you can implement.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6088
0 comments:
Post a Comment
Let us know your responses and feedback