Suppose I have a given monic homogeneous polynomial $p$ of total degree $n$ in $a_0,...,a_k$ and $x$ with integer coefficients, and suppose I know or "reasonably conjecture" that there exists at least one matrix which has $p(x)$ as its characteristic polynomial and whose entries are linear combinations of the $a_j$'s.
What would be a good algorithm to find such a matrix?
The question is motivated by this example where there is a family of polynomials which have very likely this property and the matrices probably a not-too-complicated pattern, which I would of course like to identify. After the trivial $p_1=x+a_0-a_1$, the next one is $$p_2=x^2 + (a_0 - a_2)x + a_0^2 - a_1^2 + a_1a_2- a_0a_3$$ with a fitting matrix (which may well be unique up to transposition, but I would not give a guarantee)$$\pmatrix{-a_0 + a_1 &a_0\\ -a_0 + a_1 - a_2 + a_3 & -a_1 + a_2}$$ The next one in the row is already quite unfeasible to do by hand. It can be written as $$p_3=x^3 - a_3x^2 + \bigl[(a_0-a_2) (a_2-a_3 ) + ( a_0-a_1) ( a_4- a_3 )\bigr]x\\ - a_0^3 + a_0^2(a_1 + a_4)+a_0(a_1^2+ a_3^2 - a_2a_3 - 2a_1a_4)- a_1^3 + a_1^2a_4+ a_1a_2^2 - a_1a_2a_3. $$The way I have arranged the coefficient of $x$ is maybe the shortest one, but that does by no means imply that the four factors used here occur as entries of the researched $3\times 3$ matrix. Further on, the corresponding entry for $p_5$ (i.e. the coefficient of $x^3$) has exactly 13 terms, not 12. This may hint that some of the matrix entries might be $0$, which does not necessarily facilitate the task of guessing a general pattern...
BTW the traces of the occurring matrices apparently follow the pattern $$\mathrm {tr}(M_n)=-a_0+ \sum_{j=0}^{\lfloor n/3\rfloor }a_{n-3j},$$ which, to begin with, makes even the guessing of suitable diagonal elements for the general case difficult.
Here is some Sage code producing these polynomials.