Relating a Polynomial equation to the characteristic equation of a Hermitian matrix

Question

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?

Answer 1

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

Answer 2

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)

Answer 3

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.