The following is true: if the leading coefficient of $-P(t)$ is an $n$th power, then $P$ is achievable. Furthermore, replacing $A, B$ with $MAM^T$, $MBM^T$ for a matrix $M$ of determinant $d \in k$ shows that if $P$ is achievable, so is $d^2 P$. These two facts together imply that any polynomial of odd degree is achievable.

Also this seems related to Gross's recent talk on the arithmetic of pencils of quadrics which is online at http://techtv.mit.edu/collections/harris60/videos/13950-benedict-gross, but I'm not sure if there's a direct connection. Also, recent work of Melanie Wood may also be relevant: (in particular the parts of http://arxiv.org/PS_cache/arxiv/pdf/1008/1008.4781v1.pdf where she discusses symmetric tensors, and theorem 5.7, although you probably want to take your base ring $R$ to be a field).

The construction for matrices $A$ and $B$ in the case when $n$ is odd and $-P(t)$ is monic with no repeated roots is sketched in Bhargava and Gross's recent preprint on arithmetic invariant theory (http://www.math.harvard.edu/~gross/preprints/invariant.pdf, middle of page 8). Since it's buried mixed in with a lot of other stuff, I'll unpack it here. (It is essentially David Speyer's argument.)

Let $f(t) = (-1)^n P(t)$. By our assumption and rescaling, WLOG assume $f$ monic.

Let $K$ be the $k$-algebra $k[u]/f(u)$ (not necessarily etale, as David Speyer pointed out, since $f$ need not be separable), and let $\beta$ be the image of $u$ in $K$. We define trace and norm maps from $K$ down to $k$ in the standard way; namely, $\mathop{\mathrm{tr}}(x)$ and $\mathop{\mathrm{Norm}}(x)$ are the trace and norm respectively of the linear operator on $K$ given by multiplication by $x$.

We'll use the basis $1, \beta, \beta^2, \dotsc, \beta^{n-1}$ of $k$ over $K$. There's a nice nondegenerate pairing on $K$, which is the following: let $\langle a, b \rangle$ be $(-1)^{\binom{n}{2}}$ times the coefficient of $\beta^{n-1}$ in $ab$ (when written out in terms of our basis). It's easily checked that this pairing has determinant $1$ with respect to our basis (the entries above the antidiagonal are all $0$) so is nondegenerate.

(An earlier version of this answer used the trace pairing instead, but that runs into some issues, and this the pairing Bhargava and Gross actually use in their paper.)

Let $B$ be the matrix of the quadratic form $\langle, \rangle$ that we just defined. Let $A$ be the matrix of the quadratic form $(x, y) \mapsto \langle{\beta x, y}\rangle$.

Then $\det(A - t B)$ is the determinant of the pairing $(x, y) \mapsto \langle(\beta-t)x, y\rangle$ (I'm implicitly extending scalars to $k[t]$, or if $k$ is infinite, just think of this as a function of $t$). But that determinant is equal to $\mathop{\mathrm{Norm}}(\beta - t)$ times the determinant of the pairing $\langle, \rangle$ (with respect to our basis). But the latter determinant is just $1$, as stated above. Furthermore, by unpacking the definitions and using the definition of the characteristic polynomial, we get $\mathop{\mathrm{Norm}}(\beta - t) = (-1)^n f(t) = P(t)$, and so $\det(A - tB) = P(t)$ as desired. (Well, actually, not quite as desired, but $A - tB = A + t(-B)$, so we're good.)

Also note that nothing goes wrong if we choose $P$ to have repeated roots.

I still need to think about the general case.

`$\det \left( \begin{smallmatrix} 1 & t \\ t & -1 \end{smallmatrix} \right)$`

$\endgroup$ – David E Speyer Sep 12 '11 at 1:521more comment