Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
If you take the 2*2 matrix [1 1][0 1], you get $a_n=n+2$. –  Denis Jul 25 '13 at 11:30

1 Answer 1

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)

share|improve this answer
    
Thank you Igor, this is very helpful! –  Victor Jul 26 '13 at 16:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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