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!

  • $\begingroup$ Can you do the case $n=2$? $\endgroup$ Feb 16, 2015 at 22:28
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 17, 2015 at 0:10
  • $\begingroup$ David, unfortunately I would like to avoid the additional zero eigenvalues. Is this question open even without the primitivity assumption? Thanks for the very interesting articles! $\endgroup$
    – subshift
    Feb 17, 2015 at 15:41
  • $\begingroup$ Gerry, I haven't looked at it for hours but it doesn't seem to be obvious even for $2\times2$ matrices. $\endgroup$
    – subshift
    Feb 17, 2015 at 15:42
  • $\begingroup$ Right now the best I can do is to enumerate all the matrices (using the trace constraint) and test them one by one... Can anyone think of a less stupid approach? $\endgroup$
    – subshift
    Feb 17, 2015 at 15:44

1 Answer 1


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$".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.