Re: [math-fun] Polynomials with real roots
Yes, you are right, I wasn't very clear. 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. I assume that the generality of Hermitian v. real symmetric doesn't help, does it? At 10:56 AM 11/14/2009, victor miller wrote:
Perhaps there's some condition you're not telling me. Since every real diagonal matrix is Hermitian the answer is obviously yes (just put the roots on the diagonal). There is a related arithmetic question -- Suppose that a monic polynomial with integer coefficients has all real roots, is it the characteristic polynomial of a symmetric integer matrix? The answer is no -- there's a series of papers about this by Ed Bender and Norman Hertzberg around 1970.
Victor
On Sat, Nov 14, 2009 at 10:21 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Stupid matrix question:
I know that the characteristic polynomial of a Hermitian matrix must have all real roots (it is diagonalizable into a real diagonal matrix).
But is every polynomial with only real roots the characteristic polynomial of a Hermitian matrix?
If so, is there a construction that takes one from the polynomial (in the form of a vector of coefficients) to the Hermitian matrix?
(The construction from the roots themselves is trivial: they form a diagonal matrix that can be rotated by any unitary matrix.)
Presumably, such a construction would fail if/when not all of the roots are real.
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
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
Thanks to your pointer to Bender & Herzberg, I found using Google the following paper, which would appear to solve my problem. I believe that this paper references Bender & Herzberg's work. I have contacted the Prof. Weiss for a preprint. Characteristic Polynomials of Symmetric Matrices Alfred Weiss Department of Mathematics University of Alberta Edmonton, Canada The problem: Given a monic polynomial f(X) with coefficients in a field F decide if f(X) is the characteristic polynomial of some symmetric matrix with entries from F. p. 59 & following of: Taussky, Olga. Ternary Quadratic Forms & Norms. v. 79 of Lecture Notes in Pure & Applied Math. ISBM 0-8247-1651-5. 1982. At 01:48 PM 11/14/2009, Henry Baker wrote:
Yes, you are right, I wasn't very clear.
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.
I assume that the generality of Hermitian v. real symmetric doesn't help, does it?
At 10:56 AM 11/14/2009, victor miller wrote:
Perhaps there's some condition you're not telling me. Since every real diagonal matrix is Hermitian the answer is obviously yes (just put the roots on the diagonal). There is a related arithmetic question -- Suppose that a monic polynomial with integer coefficients has all real roots, is it the characteristic polynomial of a symmetric integer matrix? The answer is no -- there's a series of papers about this by Ed Bender and Norman Hertzberg around 1970.
Victor
On Sat, Nov 14, 2009 at 10:21 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Stupid matrix question:
I know that the characteristic polynomial of a Hermitian matrix must have all real roots (it is diagonalizable into a real diagonal matrix).
But is every polynomial with only real roots the characteristic polynomial of a Hermitian matrix?
If so, is there a construction that takes one from the polynomial (in the form of a vector of coefficients) to the Hermitian matrix?
(The construction from the roots themselves is trivial: they form a diagonal matrix that can be rotated by any unitary matrix.)
Presumably, such a construction would fail if/when not all of the roots are real.
participants (2)
-
Gareth McCaughan -
Henry Baker