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? 



When is a monic integer polynomial the characteristic polynomial of a non-negative integer matrix?
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.


