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