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?

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!

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?

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!