Return to Answer

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. 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

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

Let $K$ be a subfield of $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. 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

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. 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

Let $K$ be a subfield of $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. 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

Let $K$ be a subfield of $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. 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