Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question arose out of mere curiosity. Given a polynomial equation and I happen to know that its roots are real (but not the roots itself). Does it mean it is the characteristic equation of a Hermitian matrix? And if that is the case, could I just find the hermitian matrix and solve for its eigenvalues?. When I thought about it, looks like determining the hermitian matrix from the polynomial equation looks like a daunting task. Any thoughts on this?

share|improve this question
    
What about a diagonal matrix? –  plusepsilon.de Nov 23 '12 at 12:01
    
You mean the diagonal matrix with the roots as the entries. But I don't know the roots other than the knowledge that they are real. –  dineshdileep Nov 23 '12 at 12:23
    
Okay, then the question becomes less trivial. A shame that I can't undo my vote to close:( –  plusepsilon.de Nov 23 '12 at 13:00

3 Answers 3

up vote 9 down vote accepted

Let $K$ be a subfield of $\mathbb R$ (e.g., $K=\mathbb Q$) and $f\in K[x]$ be a monic polynomial of degree $n$ all of whose roots are real. We want to compute a symmetric matrix $A\in K^{n\times n}$ such that $f=\det(xI_n-A)$. By squarefree decomposition in $K[x]$ we can assume that $f$ has only simple roots (otherwise perform euclidean divisions to compute the squarefree decomposition, find a determinantal representation for each factor in this decomposition and use diagonal blocks).

Of course, the idea is to start off with the companion matrix $C\in K^{n\times n}$ of $f$ which represents the vector space endomorphism $$\varphi\colon K[x]/(f)\to K[x]/(f),\ \overline p\mapsto\overline{xp}$$ with respect to the canonical monomial basis. We know that $f=\det(xI_n-C)$. In particular, $C$ is similar to a triangular matrix and therefore $\text{tr}(C^k)$ is the sum of the $k$-th powers of the roots of $f$ for each $k\in\mathbb N$.

Now $C$ itself is almost never symmetric but $\varphi$ is self-adjoint with respect to the $L_2$ "scalar product" given by a measure whose mass is uniformly distributed on the roots of $f$ (we use here that the roots are simple so that this really gives a non-degenerate bilinear form). Denoting the usual scalar product on $\mathbb R^n$ by $\langle.,.\rangle$ and by $V\in \mathbb R^{n\times n}$ the Vandermonde matrix corresponding to the roots of $f$, this means that $\langle VCx,Vy\rangle=\langle Vx,VCy\rangle$ for all $x,y\in\mathbb R^n$. In other words, we have $C^TV^TV=V^TVC$.

Now the Hermite matrix $H:=V^TV$ of $f$ comes naturally into play. It is a Hankel matrix whose entries are power sums of roots of $f$. But these power sums are traces of powers of $C$ and therefore lie in $K$ and can easily be computed. The idea is to replace $V$ by another matrix $W$ with $H=W^TW$. In contrast to $V$, the matrix $W$ should have entries in $K$ and should be easily computed. But this is possible: Just take any $W\in K^{n\times n}$ with $H=W^TW$. You get such a $W$ even in a triangular form if you use the Cholesky decomposition of the positive definite matrix $H$.

Now $C^TW^TW=C^TH=C^TV^TV=V^TVC=HC=W^TWC$ and since $W$ is invertible (note that $V$ and $H$ are invertible since all roots of $f$ are simple) this shows that $WCW^{-1}$ is symmetric. So you can set $A:=WCW^{-1}$.

All this is folklore.

If you want a tridiagonal $A$ then you would have to perform Sturm's algorithm as indicated above by Denis. In fact, finding a tridiagonal $A$ is essentially equivalent to Sturm's algorithm, see the recent interesting work of Ronan Quarez:

http://arxiv.org/pdf/0811.2365v1.pdf

If the coefficients of the monic polynomial are itself polynomials in variables $y_i$ such that for each fixed real value of the $y_i$ the polynomial has again only real roots (cf. Garding's notion of hyperbolic polynomials), then you can still use the Hermite matrix to do something, see the recent article of Netzer, Plaumann and Thom:

http://arxiv.org/abs/1108.4380

share|improve this answer
    
Thanks a lot for the informative reply. –  dineshdileep Nov 24 '12 at 9:37

You may even find an explicit real symmetric tridiagonal matrix whose characteristic polynomial is the one you give yourself, say $P$. The construction uses the Sturm sequence $(P_j)_{j=1,\dots,n}$ of polynomials associated with $P$. Then the matrix is constructed by adding a row/column at each step, to pass from $P_j$ to $P_{j+1}$.

See Exercise 92 in my list of exercises, additional to my book Matrices (Springer-Verlar GTM 216)

share|improve this answer
    
I went through your list of exercises. Unfortunately, I can't find a solution to them. Can you please provide a link for the solutions of the additional exercise problems. I believe working on it will greatly improve my knowledge in matrix theory. Thanks a lot. –  dineshdileep Nov 23 '12 at 17:29

This is a special case of the Inverse Problem of the spectral theory. One can construct such a matrix (symmetric 3-diagonal) even with rational operations (without square roots). This construction has a very nice mechanical interpretation.

I recommend the paper of M. Krein, On a remarkable problem for a string with beads, and on continued fractions of Stieltjes. This paper is available as an appendix to the book Gantmakher and Krein, Oscillation matrices and kernels... which has been recently translated into English, MR1908601.

share|improve this answer
    
Thanks for the answer. I will definitely have a look at that work. –  dineshdileep Nov 23 '12 at 17:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.