8
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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$
    – HenrikRüping
    Commented Jul 25, 2013 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
    Commented Jul 25, 2013 at 11:26
  • 1
    $\begingroup$ If you take the 2*2 matrix [1 1][0 1], you get $a_n=n+2$. $\endgroup$
    – Denis
    Commented Jul 25, 2013 at 11:30

1 Answer 1

Reset to default
4
$\begingroup$

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)

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .