# Growth of powers of non-negative integer matrices

In what I am currently doing, there naturally appears the following question: let $A$ be a square matrix with non-negative integer entries. Let $a_n$ be the sum of all entries of $A^n$.

Question: How the sequence $\{a_n\}_{n\geq 1}$ can grow?

Of course if $A$ is positive, then Perron-Frobenius Theorem tells us the answer, but in the general case of non-negative matrices, it can be difficult to guess the asymptotics of the sequence $\{A^n\}_{n\geq 1}$. So, I thought may be there is something known for this case, when we have actually integer matrices. Any references and comments would be appreciated.

-
Let $l(A)$ denote the largest entry in a matrix $A$. Then we have for two $m\times m$ matrices with nonnegative entries $l(AB)\le m\cdot l(A)\cdot l(B)$ and thus $a_n\le m^2l(A^n)\le m^{2+n}l(A)^n$. If we consider the matrix with all entries equal, we get equality and so this bound is as sharp as possible. But I guess you were looking for examples, where this sequence grows polynomially or subexponentially or so. –  HenrikRüping Jul 25 '13 at 11:04
Thanks, Henrik. Yes, it would be interesting to learn what could be the growth rates of that sequence. It would be quite surprising if the growth could be intermediate –  Victor Jul 25 '13 at 11:26
If you take the 2*2 matrix [1 1][0 1], you get $a_n=n+2$. –  Denis Jul 25 '13 at 11:30

I am not sure I understand the question. Any matrix $A$ (integer or not, positive or not) has a Jordan canonical form $A = MJM^{-1},$ whereupon $A^n = M J^n M^{-1}.$ If $A$ is integer and nonsingular, the biggest eigenvalue is at least $1$ in modulus (since the determinant is at least $1$ in absolute value). If it IS equal to $1$ in modulus, the sum of the elements will be polynomial, if it is greater than one, it will be exponential -- if there is a single eigenvalue of maximal modulus, it will be really exponential, otherwise at least there will be a positive density subsequence of $n$ for which it is. Which numbers can occur as eigenvalues of nonnegative integer matrices was answered by Doug Lind in: