When is a monic integer polynomial the characteristic polynomial of a non-negative integer matrix?

Question

Suppose $P(x)$ is a monic integer polynomial with roots $r_1, ... r_n$ such that $p_k = r_1^k + ... + r_n^k$ is a non-negative integer for all positive integers $k$. Is $P(x)$ necessarily the characteristic polynomial of a non-negative integer matrix?

(The motivation here is that I want $r_1, ... r_n$ to be the eigenvalues of a directed multigraph.)

Edit: If that condition isn't strong enough, how about the additional condition that $$\frac{1}{n} \sum_{d | n} \mu(d) p_{n/d}$$

is a non-negative integer for all d?

Answer 1

This question is completely answered, and the result is that the condition involving the Moebius inversion you mention is both necessary and sufficient! See

• K. H. Kim, N. Ormes, F. Roush. The spectra of nonnegative integer matrices via formal power series, J. Amer. Math. Soc. 13 (2000) 773–806. https://doi.org/10.1090/S0894-0347-00-00342-8

This is really a remarkable and beautiful theorem.

Answer 2

This is an interesting question! It seems that the corresponding problem even with "integer" replaced by "real" is hard (see Thomas J. Laffey, Inverse Eigenvalue Problems for Matrices, JSTOR), i.e., there are "further" inequalities satisfied by the eigenvalues of non-negative real matrices. I do not know what extra complexity is induced by passing to integers but I suspect it must be very hard to give exact conditions.

Answer 3

Second idea, which at least gives some necessary conditions...

The Perron-Frobenius Theorem for non-negative matrices ensures that there is always a real eigenvalue equal to the spectral radius. So a polynomial cannot be the char.poly. of such a matrix if it has no real roots, or if the greatest absolute value of any root is greater than the largest real root. This necessary condition thus generalises your observation in the monic quadratic case.

Answer 4

This is true for quadratic polynomials with constant term $+1$. Any such polynomial is the determinant of a matrix in $SL_2(\mathbb{Z})$ (e.g. using the companion matrix as indicated by Ben Webster). It's well known that any such matrix is conjugate to a multiple product of $\left(\begin{matrix}1&1\\0&1\end{matrix}\right)$ and $\left(\begin{matrix}1&0\\1&1\end{matrix}\right)$ (upper and lower triangular unipotent matrices). I'm not sure the original reference for this fact, but a reference is Proposition 2.1 of On canonical triangulations of once-punctured torus bundles and two-bridge link complements.

I believe that your criterion implies that the maximal root of the polynomial is a Perron number. If so, then Lind has shown that every Perron number occurs as the spectral radius of a non-negative integral Perron-Frobenius matrix (and therefore the spectral radius of a recurrent digraph). This only implies that the polynomial divides the characteristic polynomial of the matrix—there might be other factors.

Added comment: The general quadratic case might be possible to work out using Markov partitions of the induced map of a torus.

I forgot about the cyclotomic case, which can occur if the matrix is not Perron-Frobenius. If the polynomial is irreducible, I think the condition implies that the maximal norm roots are complex Perron numbers (or cyclotomic). These crop up in work of Kenyon on self-similar tilings (The construction of self-similar tilings, MR1392326).

Answer 5

Well, let me say what I know so far.

For monic quadratic polynomials it's necessary and sufficient that both roots be real and one be positive with absolute value at least the other. This requires no complicated argument: the characteristic polynomial of $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ is $x^2 - (a + d)x + (ad - bc)$. Since $a, d \geq 0$ it's necessary that at one root has positive real part at least as large as the absolute value of the real part of the other, and since $b, c \geq 0$ it's necessary that $(a + d)^2 \geq 4ad \geq 4(ad - bc)$. This is sufficient because we can set $c = 1$.

For general polynomials, I believe a theorem of Berstel implies that 1) the radius of convergence of $1/x^n P(1/x)$ must occur as a positive real pole $r$, and 2) any other pole $s$ with $|s| = r$ has the property that $s/r$ is a root of unity. On the other hand polynomials such as the polynomial with roots $5, 5, 3 + 4i, 3 - 4i$ don't have this property even though they satisfy the non-negativity condition.

Answer 6

I can possibly offer a counterexample, from James McKee and Chris Smyth's Integer symmetric matrices of small spectral radius and small Mahler measure.

If $P=x^7-8x^5+19x^3-12x+1$ were the characteristic polynomial of a matrix corresponding to a graph, then it would be the char.poly of a matrix corresponding to a charged signed graph (symmetric, all entries $0$,$1$ or $-1$). For such matrices we define the associated reciprocal polynomial to be $(z^d)X(z+1/z)$, where $X$ is the characteristic polynomial and d its degree. In this case, the associate reciprocal polynomial would be $z^{14}-z^{12}+z^7-z^2+1$. For any integer polynomial we can find a Mahler measure, and the Mahler measure of this polynomial is $1.20261\!\ldots$ However, Smyth and McKee determined the Mahler measures less than $1.3$ that arise from associated reciprocal polynomials of charged signed graphs, and this quantity is not attained.

So $P$ cannot be the characteristic polynomial of a charged signed graph, of which graphs are a special case. Does $P$ satisfy your non-negativity conditions on the roots? The sums of odd powers seem to be zero.

Answer 7

EDIT: I misread the question and proved something easier. Oh well.

Any monic polynomial $p(x)=p_0+p_1x+p_2x^2+...+x^n$ with coefficients in a ring $R$ is the characteristic polynomial of a matrix with coefficients in $R$. Consider a vector space with basis $e_0,\ldots,e_{n-1}$, and the linear transformation that sends $e_i\mapsto e_{i+1}$ and $e_{n-1} \mapsto p_0e_0+p_1e_1+\cdots$

This linear transformation obviously has minimal polynomial $p(x)$, and so that must be the characteristic polynomial.

Any of the usual bases of symmetric functions is integer if and only if any other is, so we are done.