29
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ What made you suspect that the Moebius conversion would be relevant? $\endgroup$ Jul 11, 2016 at 16:12
  • 1
    $\begingroup$ @Prime: a nonnegative integer matrix is the adjacency matrix of some graph (directed, multi). The Mobius-inverted quantities above count the number of aperiodic walks on this graph of length $n$. $\endgroup$ Jul 11, 2016 at 18:18
  • 1
    $\begingroup$ Ah, ok. Thanks! The Möbius function must certainly rank among the functions with the highest usefulness to number-of-possible-output-values ratio. $\endgroup$ Jul 12, 2016 at 12:29

7 Answers 7

34
$\begingroup$

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

This is really a remarkable and beautiful theorem.

$\endgroup$
1
  • $\begingroup$ Wow, thank you for this nice reference! $\endgroup$ Apr 3, 2011 at 23:07
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
1
  • 1
    $\begingroup$ 1. For quadratic polynomials a necessary condition is that the linear term is non-positive, since the trace is non-negative. It's not hard to get all polynomials of the form x^2 - 2nx + 1, but admittedly I haven't thought too hard about the quadratic case. 2. No. For example, P(x) = x^n - 1 works. $\endgroup$ Nov 4, 2009 at 1:11
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ When I say "graph" I mean "directed multigraph." Sorry if that wasn't clear. $\endgroup$ Nov 3, 2009 at 17:58
  • $\begingroup$ P also doesn't satisfy the non-negativity condition on roots. $\endgroup$ Nov 3, 2009 at 18:01
  • $\begingroup$ Ah, I see. The basic mahler measure idea would work for multigraphs (as the only 'good' integer matrices are the ones corresponding to CSMs) but if you relax symmetry by introducing directionality I imagine things break. $\endgroup$ Nov 3, 2009 at 18:33
-1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Yes, but the coefficients of the companion matrix aren't necessarily non-negative. $\endgroup$ Nov 3, 2009 at 15:10
  • $\begingroup$ Oh, sorry, I missed the non-negative part. I was wondering why you had asked such an easy question. $\endgroup$
    – Ben Webster
    Nov 3, 2009 at 15:15
  • $\begingroup$ I am curious with a question ,it has not been replied in the above discussion. When is a monic polynomial a characteristic polynomial of a nonnegative matrix. $\endgroup$
    – Sunni
    Dec 10, 2010 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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