4
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • $\begingroup$ Can you do the case $n=2$? $\endgroup$
    – Gerry Myerson
    Commented 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$
    – David Handelman
    Commented 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
    Commented 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
    Commented 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
    Commented Feb 17, 2015 at 15:44

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .