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.

  • $\begingroup$ 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. $\endgroup$ Jul 25 '13 at 11:04
  • $\begingroup$ 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 $\endgroup$
    – Victor
    Jul 25 '13 at 11:26
  • 1
    $\begingroup$ If you take the 2*2 matrix [1 1][0 1], you get $a_n=n+2$. $\endgroup$
    – 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:

Lind, D. A.(1-WA) The entropies of topological Markov shifts and a related class of algebraic integers. Ergodic Theory Dynam. Systems 4 (1984), no. 2, 283–300. 58F11 (15A48 28D20)

MR1149738 (92m:11117) Reviewed Lind, Douglas(1-WA) Matrices of Perron numbers. J. Number Theory 40 (1992), no. 2, 211–217. 11R06 (15A48 58F03)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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