Lo siguiente es cierto: si el coeficiente principal de $-P(t)$ es un $n$ ª potencia, entonces $P$ es factible. Además, la sustitución de $A, B$ con $MAM^T$ , $MBM^T$ para una matriz $M$ del determinante $d \in k$ muestra que si $P$ es factible, también lo es $d^2 P$ . Estos dos hechos juntos implican que cualquier polinomio de grado impar es alcanzable.
También esto parece relacionado con la reciente charla de Gross sobre la aritmética de los lápices de cuádricas que está en línea en http://techtv.mit.edu/collections/harris60/videos/13950-benedict-gross pero no estoy seguro de que haya una conexión directa. Además, el trabajo reciente de Melanie Wood también puede ser relevante: (en particular las partes de http://arxiv.org/PS_cache/arxiv/pdf/1008/1008.4781v1.pdf donde discute los tensores simétricos, y el teorema 5.7, aunque probablemente quieras tomar tu anillo base $R$ ser un campo).
La construcción para matrices $A$ y $B$ en caso de que $n$ es impar y $-P(t)$ es mónico sin raíces repetidas está esbozado en el reciente preprint de Bhargava y Gross sobre teoría aritmética invariante ( http://www.math.harvard.edu/~gross/preprints/invariant.pdf , mitad de la página 8). Como está enterrado mezclado con muchas otras cosas, lo desglosaré aquí. (Es esencialmente el argumento de David Speyer).
Sea $f(t) = (-1)^n P(t)$ . Por nuestra suposición y reescalado, WLOG asume $f$ monic.
Sea $K$ sea el $k$ -álgebra $k[u]/f(u)$ (no necesariamente etale, como señaló David Speyer, ya que $f$ no tiene por qué ser separable), y que $\beta$ sea la imagen de $u$ en $K$ . Definimos los mapas de traza y norma de $K$ hasta $k$ de la forma habitual, a saber, $\mathop{\mathrm{tr}}(x)$ y $\mathop{\mathrm{Norm}}(x)$ son la traza y la norma respectivamente del operador lineal sobre $K$ dada por la multiplicación por $x$ .
Utilizaremos la base $1, \beta, \beta^2, \dotsc, \beta^{n-1}$ de $k$ en $K$ . Hay un bonito emparejamiento no degenerado en $K$ que es la siguiente: sea $\langle a, b \rangle$ sea $(-1)^{\binom{n}{2}}$ veces el coeficiente de $\beta^{n-1}$ en $ab$ (cuando se escribe en términos de nuestra base). Es fácil comprobar que este emparejamiento tiene determinante $1$ con respecto a nuestra base (las entradas por encima de la antidiagonal son todas $0$ ) por lo que es no degenerada.
(Una versión anterior de esta respuesta utilizaba en su lugar el emparejamiento de trazas, pero esto plantea algunos problemas, y este es el emparejamiento que Bhargava y Gross utilizan realmente en su artículo).
Sea $B$ sea la matriz de la forma cuadrática $\langle, \rangle$ que acabamos de definir. Sea $A$ sea la matriz de la forma cuadrática $(x, y) \mapsto \langle{\beta x, y}\rangle$ .
Entonces $\det(A - t B)$ es el determinante del emparejamiento $(x, y) \mapsto \langle(\beta-t)x, y\rangle$ (Estoy ampliando implícitamente los escalares a $k[t]$ o si $k$ es infinita, piensa que es una función de $t$ ). Pero ese determinante es igual a $\mathop{\mathrm{Norm}}(\beta - t)$ veces el determinante del emparejamiento $\langle, \rangle$ (con respecto a nuestra base). Pero este último determinante es simplemente $1$ como se ha indicado anteriormente. Además, descomprimiendo las definiciones y utilizando la definición del polinomio característico, obtenemos $\mathop{\mathrm{Norm}}(\beta - t) = (-1)^n f(t) = P(t)$ y así $\det(A - tB) = P(t)$ como desee. (Bueno, en realidad, no tan deseado, pero $A - tB = A + t(-B)$ así que estamos bien).
También hay que tener en cuenta que nada sale mal si elegimos $P$ tener raíces repetidas.
Aún tengo que pensar en el caso general.