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 polynomialequalto $P(X)$? [$M$ isprimitiveif $M^k$ is positive for some $k \geq 0$.]

Question 2.Given such a polynomial, is there anefficientmethod to enumerate the valid matrices?

Some remarks.

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!

Algebraic shift equivalence and primitive matrices,tams (1993), which deals mostly with realization over the nonnegative integers. $\endgroup$ – David Handelman Feb 17 '15 at 0:10