Interesting construction -- I had forgotten about that. Thanks! If all of the (distinct) roots are real, you should be able to find those root pairs that are negatives of one another by computing gcd(p(x),p(-x)), which should pull out all the +- pairs, although not separated from one another. So, we can now assume that all the |r|^2's are distinct. At the very worst, we can simply try both the positive & negative square roots of each of the |r|^2's to see which are actually roots. --- But this only "works" properly for polynomials which _do_ have only real roots. I was hoping for some sort of construction that failed if the polynomial had one or more non-real roots. If the coefficients of the polynomial are real to begin with, we are (in essence) talking about a construction that implicitly computes a _Sturm chain_ which tells us whether we have enough real roots. http://en.wikipedia.org/wiki/Sturm%27s_theorem At 04:36 PM 11/14/2009, Gareth McCaughan wrote:
On Saturday 14 November 2009 21:48:17 Henry Baker wrote:
Let's assume that the polynomial has no repeated roots, since those can be detected with rational operations only.
I'd like to construct an Hermitian matrix with the same real roots, but _without solving for the roots_; i.e., the elements of the matrix are in the field of the polynomial coefficients, prior to being extended all the way to the root field.
So your answer gets close to the answer to my question -- thanks for the pointer.
In the case where the answer is no, can we make modest extensions -- e.g., square roots -- that would get us such a matrix w/o extending to the full root field.
If you're prepared to allow the modest extensions *after* solving the characteristic polynomial, the answer to the last question is certainly yes, with no particular ingenuity required, unless I'm missing something:
1. Given the polynomial p = X^n + amX^m + ... + a0 (m=n-1 for notational convenience), the (not at all Hermitian) matrix A = [0 0 0 ... -a0] [1 0 0 ... -a1] [0 1 0 ... -a2] [.............] [0 0 ... 1 -am] has p as its characteristic polynomial.
2. Now consider B = At.A ("t" meaning Hermitian conjugate); its eigenvalues are |z|^2 where z runs over eigenvalues of A, i.e. (assuming all zeros distinct) over zeros of p.
3. So, suppose p has distinct real zeros. Then construct A and B as above; obviously the elements of B are in the field generated by the coefficients of A; the zeros of the characteristic polynomial of B are the squares of the zeros of p; so you get the zeros of p by square-rooting them.
Alternatively, the following gets you something close to what you want without any field extensions: before step 1, replace X with X^2 in p; this yields a polynomial whose zeros are the square roots of p's. So now the eigenvalues of B are the absolute values of the zeros of p. (They're no longer distinct, which you may or may not care about.)
-- g