Let $P(X) = a_nX^n + \cdots + a_1X + a_0$ with $a_i \in \mathbb Z$.
Question 1. Is there an efficient criterion on the $a_i$ to decide if there exists a primitive nonnegative integer matrix with characteristic polynomial equal to $P(X)$? [$M$ is primitive if $M^k$ is positive for some $k \geq 0$.]
Question 2. Given such a polynomial, is there an efficient method to enumerate the valid matrices?
An answer in the particular case $a_n = a_0 = 1$ will also make me happy. The polynomials I'm interested in are typically a product of a Perron number and roots of unity, for example $(X^3-X-1)(X-1)^k$.
A similar question, "What algebraic numbers are eigenvalues of nonnegative integer matrices?", is answered here, but I want all the roots of $P(X)$ and no other eigenvalues in the candidate matrices.
There seems to be many variants of this problem (example), sorry if this question was already answered somewhere.
Thanks in advance!