# Eigenvalues of nonnegative integer matrices

Edit I realized that the key piece of information that I need is question 1, and so I'd like to rephrase this post:

What are the possible eigenvalues of nonnegative integer matrices?

Any answer to this question would be appreciated and checkmarked.

Original Question:

My question is related to this question about integer nonnegative matrices but goes in a slightly different direction. Like the previous poster, my question comes from solving linear recursions (specifically, computing the discrete modulus of a product finite subdivision rule acting on a grid).

Given $A$ a square matrix with nonnegative integer entries and $v$ a column vector of the same dimension, we can use the Jordan canonical form to get a closed expression for $A^n(v)$. If we sum the entries of $A^n(v)$, we get a function of the form $f(n)=a_1 P_1(n)\lambda_1^n+...+a_kP_k\lambda_k$, where the $\lambda$'s are the distinct eigenvalues and each $P_i$ is a monic polynomial in $n$.

My question is, what are the possible values for the $a_i$ and the $\lambda_i$? In particular:

1. Can the $\lambda_i$ be any algebraic integer?
2. Can the $a_i$ be non-integers?
3. (My real question): Given an algebraic integer $\lambda$, can we construct two matrices $A_1$ and $A_2$ such that the ratio of their associated polynomials $\frac{f_1(n)}{f_2(n)}$ (where, as above, $f_i(n)$ is the sum of the entries of $A_1^n v$) has limit $\lambda$? The limit of such a fraction will be 0 unless the 'largest terms' of each polynomial have the same magnitude; my worry is that it would be impossible to get some algebraic integers in this way because they have Galois conjugates of equal or larger size. But it seems that the column vector $v$ might allow one to 'cancel out' unwanted eigenvalues. Is this possible? Is it even possible to get $\sqrt{3}$ in this way?

Thank you for your help! The first two questions seem like they would be easily answerable by experts in matrix theory, but google searches have led to nothing. I appreciate in advance your help.

## An example of $f_1(n)$

Let $A=\left[ \begin{array}{cc} 1 & 2 \\ 0 & 2 \end{array} \right]$. It can be diagonalized as $A=\left[ \begin{array}{cc} 1 & 2 \\ 0 & 1 \end{array} \right] \left[ \begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array} \right] \left[ \begin{array}{cc} 1 & -2 \\ 0 & 1 \end{array} \right]$. Now, let $v = \left[ \begin{array}{c} 2 \\ 3 \end{array} \right]$.

Then $A^{n} v= \left[ \begin{array}{cc} 1 & 2 \\ 0 & 1 \end{array} \right] \left[ \begin{array}{cc} 1 & 0 \\ 0 & 2^{n} \end{array} \right] \left[ \begin{array}{cc} 1 & -2 \\ 0 & 1 \end{array} \right] \left[ \begin{array}{c} 2 \\ 3 \end{array} \right] = \left[ \begin{array}{cc} 1 & 2^{n+1} -2 \\ 0 & 2^{n} \end{array} \right] \left[ \begin{array}{c} 2 \\ 3 \end{array} \right] = \left[ \begin{array}{c} 3(2^{n+1})-4 \\ 3(2^{n}) \end{array} \right]$. Adding all the entries of this matrix together, we see that the growth function $f(n)$ is $3(2^{n+1} + 2^{n})-4=9(2^{n})-4$.

-
As you might well know, the answer to #1 is yes if you don't restrict the integer entries to be nonnegative (since you can make any polynomial the characteristic polynomial of a matrix, using rational canonical form). As for #2, I believe the classic Fibonacci matrix gives a positive answer - see en.wikipedia.org/wiki/Fibonacci_number#Matrix_form and note that the sum of the entries is $F_{n+3}$. –  Greg Martin Nov 13 '12 at 1:25
@Greg The Fibonnaci matrix is a perfect example; thank you! That definitely resolves question 2. I thought about the rational canonical form; is there any way to replace the negative entries with a larger submatrix that has positive entries? That would do the job. –  Brian Rushton Nov 13 '12 at 17:24
What are the associated polynomials $f_1, f_2$? –  Qiaochu Yuan Nov 15 '12 at 4:44
As for the first question, the answer is no. See mathoverflow.net/questions/3939/… . –  Qiaochu Yuan Nov 15 '12 at 4:44
Question 3 has been answered in the affirmative by Walter Parry. –  Brian Rushton Nov 17 '12 at 3:05

I claim that any algebraic integer $\lambda$ is the eigenvalue of a nonnegative matrix with integer coefficients. This answer relies on Doug Lind's answer here. Let $\lambda_1$, $\lambda_2$, ..., $\lambda_r$ be the Galois conjugates of $\lambda$. Let $\ell = \max(|\lambda_i|)$. Choose an integer $L$ large enough that $L^n \cdot (L-2)/(L-1) > \ell^n \cdot \ell/(\ell-1)$ for all positive integers $n$. I claim there will be a nonnegative integer matrix with eigenvalues $(\lambda_1, \lambda_2, \ldots, \lambda_r, L,L,\ldots, L)$ where there are $r$ copies of $L$.

Let $\mu_1$, $\mu_2$, ..., $\mu_{2r}$ be $(\lambda_1, \lambda_2, \ldots, \lambda_r, L,L,\ldots, L)$. According to Lind's answer, all we have to check is that, for all $n>0$, $$\frac{1}{n} \sum_k \sum_{d|n} \mu(n/d) \mu_k^d$$ is a nonnegative integer.

It's an integer: Let $g(x) = \prod_{i=1}^{2r} (x-\mu_i)$. Since $\lambda$ is an algebraic integer, $g$ is a monic polynomial with integer coefficients. So there is a $(2r) \times (2r)$ integer matrix $B$ with characteristic polynomial $g$ -- the companion matrix. As explained on the second paper Lind links, if $g$ is the characteristic polynomial of an integer matrix, then there is a graph theoretic interpretation of the above quantity which is manifestly integral. (I gave a slightly incorrect description of this interpretation before; I'll stick to just citing for now.)

It's nonnegative

We have $$\sum_{d|n} \mu(n/d) L^d \geq L^n - \sum_{-\infty < d<n} L^d = L^n - \frac{L^{n-1}}{1-1/L}=L^n \frac{L-2}{L-1}.$$ and $$\left| \sum_{d|n} \mu(n/d) \lambda^d \right| \leq \sum_{- \infty < d \leq n} |\lambda|^d = \frac{|\lambda|^n}{1-1/|\lambda|} = |\lambda|^n \frac{|\lambda|}{|\lambda|-1}$$

So, for every $i$, $\sum_{d|n} \mu(n/d) L^d$ is a positive integer which is greater than the norm of $\sum_{d|n} \mu(n/d) \lambda_i^d$.

So the real part of $$\sum_{i=1}^r \left( \sum_{d|n} \mu(n/d) L^d + \sum_{d|n} \mu(n/d) \lambda_i^d \right)$$ is nonnegative. By Galois symmetry, the sum is real, so it is a nonnegative real, as desired.

Disclaimer: I haven't read the paper Lind cites.

In response to Turbo's question: Any eigenvalue of an nonnegative integer matrix is an eigenvalue of a $(0,1)$ matrix. Choose $N$ larger than any matrix entry and replace each matrix entry $a_{ij}$ with an $N \times N$ block of the form $$\begin{pmatrix} 1 & 1 & \cdots & 1 & 0 & 0 \cdots & 0 \\ 1 & 1 & \cdots & 1 & 0 & 0 \cdots & 0 \\ 1 & 1 & \cdots & 1 & 0 & 0 \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \\ 1 & 1 & \cdots & 1 & 0 & 0 \cdots & 0 \\ \end{pmatrix}$$ where there are $a_{ij}$ columns of $1$'s. If $(v_1, v_2, \dots, v_n)^T$ is an eigenvector of the old matrix, then $(v_1, v_1, \dots, v_1, v_2, v_2, \dots, v_2, \dots, v_n, v_n, \dots, v_n)^T$ is an eigenvector of the new matrix with the same eigenvalue.

-
Thank you! I appreciate you taking the time to answer. –  Brian Rushton Nov 15 '12 at 19:41
@DavidSpeyer can we say same about 0-1 matrices? –  Turbo Feb 25 at 3:09
@Turbo Yes, see my edit above. –  David Speyer 2 days ago

I think there is a simpler approach. Let $\alpha$ be any algebraic integer, and let $A$ be an $n \times n$ integer matrix with $\alpha$ as an eigenvalue. Take $B$ to the the direct sum of 2 copies of $A$, ie a $2n \times 2n$ matrix, and let $J$ be the $2n \times 2n$ matrix with all entries $1.$ For large enough positive integers $m,$ $B +mJ$ is a matrix with non-negative integer entries, and still has $\alpha$ as an eigenvalue. This is because the $\alpha$ eigenspace of $B$ is (at least) $2$-dimensional, while the $0$-eigenspace of $J$ has codimension $1,$ so there is a nonzero vector $u$ with $Bu = \alpha u$ and $Ju = 0.$ Hence $(B+mJ)u = \alpha u$ for all positive integers $m.$

-
Gorgeous! You are absolutely right. –  David Speyer Nov 16 '12 at 1:10