I ran across the following beautiful paper which appears to completely answer my question in general. Quarez, Ronan. "Sturm and Sylvester algorithms revisited via tridiagonal determinantal representations". Nov. 14, 2008. http://hal.archives-ouvertes.fr/docs/00/33/89/25/PDF/prebubli_dual_bez_sturm... In this paper, Ronan shows how to take a real polynomial p(x) with distinct roots and construct a tridiagonal matrix M which is symmetric iff p(x) has all real roots. In particular, he constructs a "polynomial remainder sequence" (Euclid's algorithm on polynomials for the rest of us) on p(x) and p'(x)/deg(p) and constructs the 3 diagonals of M from the sequences of quotients and remainders. If p(x) = x^2+2bx+c and q(x) = p'(x)/2 =x+b, then the tridiagonal matrix M is: [ -b e*sqrt(|b^2-c|) ] [ ] [ sqrt(|b^2-c|) -b ] where e = sgn(b^2-c) = +-1. (If y is real, then y = sgn(y)|y|.) If e = +1, then we have a symmetric matrix and 2 real roots. charpoly(M) = x^2+2bx+b^2-e*|b^2-c| = x^2+2bx+b^2-sgn(b^2-c)*|b^2-c| = x^2+2bx+b^2-b^2+c = x^2+2bx+c If p(x) = x^3-3px+2pq and q(x) = p'(x)/3 = x^2+p, then the tridiagonal matrix M is: [ q e1*sqrt(|p-q^2|) 0 ] [ ] [ sqrt(|p-q^2|) -q e2*sqrt(|2p|) ] [ ] [ 0 sqrt(|2p|) 0 ] where e1 = sgn(p-q^2) and e2 = sgn(2p). This matrix is symmetric when e1 = e2 = +1, in which case we have 3 real roots. The general matrix construction of this type fails if we have repeated roots, because gcd(p(x),p'(x)) /= 1. But this is good news, because we have constructed the polynomial gcd in the process, in which case we have a non-trivial divisor of p(x). Constructing matrices of this type involve only rational operations and _square roots_ of non-negative numbers. In particular, the "hard work" of cracking a polynomial remains ahead even after a tridiagonal matrix has been constructed. At 06:16 AM 11/16/2009, Henry Baker wrote:

We would like to represent the polynomial t^2+2*b*t-c as the characteristic polynomial of a 2x2 matrix.

By translating the origin, we can get rid of b, which makes the following analysis more perspicuous.

So we have p(t)=t^2-c as the polynomial we want to represent by the symmetric real matrix

[x y] [y z] = M.

This matrix M satisfies its own characteristic polynomial, so we have the two equations:

y*(x+z)=0

x^2+y^2-c=0

The first equation gives z=-x, while the second gives x=+- sqrt(c-y^2).

So, M is

[-sqrt(c-y^2) y] [y sqrt(c-y^2)]

Thus, so long as |y|<sqrt(c), M will represent p(t).

In general, for 2x2 matrices, y^2 enters as an addition to the discriminant, so we have some freedom to choose y if the discriminant is positive.

Unfortunately, we have effectively solved the polynomial p(t) already, prior to constructing M, so it would appear that constructing M is not easier than solving p(t).