Eigenvalues of nonnegative integer matrices - MathOverflow

Eigenvalues of nonnegative integer matrices

2012-11-12T20:15:01Z

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:

Can the $\lambda_i$ be any algebraic integer?
Can the $a_i$ be non-integers?
(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$.

Answer by David Speyer for Eigenvalues of nonnegative integer matrices

2012-11-15T19:11:25Z

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.

Answer by Geoff Robinson for Eigenvalues of nonnegative integer matrices

2012-11-16T00:33:55Z

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