# Spectrum of primitive nonnegative integer matrices

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.

• Can you do the case $n=2$? Feb 16, 2015 at 22:28
• It would be fascinating to obtain a criterion, let alone an efficient one. Do you permit adding extra zeros as eigenvalues (that is, replacing $p$ by $X^k p$)? Over the reals, it is possible to do this (with criteria in terms of traces of powers, see Boyle & Handelman cited in the reference you cited). Note that $(x-2)(x-1)$ cannot be realized (in your strong sense), but $x(x-2)(x-1)$ can. Reference is another paper by Mike B and me, Algebraic shift equivalence and primitive matrices, tams (1993), which deals mostly with realization over the nonnegative integers. Feb 17, 2015 at 0:10
• Gerry, I haven't looked at it for hours but it doesn't seem to be obvious even for $2\times2$ matrices. Feb 17, 2015 at 15:42
Torre-Mayo et al. [MR2350690 Torre-Mayo, J.; Abril-Raymundo, M. R.; Alarcia-Estévez, E.; Marijuán, C.; Pisonero, M. The nonnegative inverse eigenvalue problem from the coefficients of the characteristic polynomial. EBL digraphs. Linear Algebra Appl. 426 (2007), no. 2-3, 729–773] solved the following problem when $n=4$: "given $k_1$,$k_2$,$\dots$,$k_n$ real numbers, find necessary and sufficient conditions for the existence of a nonnegative matrix $A$ of order $n$ with characteristic polynomial $x^n+k_1 x^{n-1}+k_2x^{n-2}a+\cdots+k_n$".