Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A$ be a square matrix with nonnegative integer coefficients.

Is there a simple way to prove that there is a "period" $d$ such that for all $0\leq r<d$, the coefficient $a_{i,j,n}$ at position $(i,j)$ in the matrix $A^{nd+r}$ is asymptotically (with respect to $n$) equivalent to $x n^y z^n$, where $x,y,z$ are nonnegative constants depending on $i,j,d,r$.

The period is needed to avoid oscillating behaviours like $(-1)^n$, or cycles of bigger length.

I found this paper which should help, but I'm having trouble formalizing a proof: http://www.ams.org/journals/jams/2000-13-04/S0894-0347-00-00342-8/S0894-0347-00-00342-8.pdf).

share|improve this question
    
maybe you want the perron frobenius thm, en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem –  mike Aug 7 '13 at 17:02
    
No I looked into it but it doesn't seem to solve the problem (unless I missed something). –  Denis Aug 7 '13 at 17:03

1 Answer 1

For a primitive matrix $A$, $A = ||a_{i j}||$ (the one that has a single eigenvalue with maximum modulo) you can use a Perron's formula for elements of matrix $A^m$, $A^m = ||a_{ij}^{<m>}||$: \begin{equation*} a^{<m>}_{i j} = \sum_{h = 1}^\nu \frac{1}{(n_h - 1)!} \biggl[\frac{d^{n_h-1}}{d\lambda^{n_h-1}} \biggl(\frac{\lambda^m A_{i j}(\lambda)}{\Psi_h(\lambda)} \biggr) \biggr]_{\lambda = \lambda_h}, \end{equation*} where $A(\lambda) = |\lambda E - A|$; $\lambda_1, \dots, \lambda_\nu$ are roots of the matrix characteristic equation $A(\lambda) = 0$ of multiplicities $n_1, \dots, n_\nu$ respectively; $A_{i j}(\lambda)$ is an algebraic adjunct for the element $\lambda \delta_{i j} - a_{i j}$ in determinant $A(\lambda)$; $\Psi_h = A(\lambda) \cdot (\lambda - \lambda_h)^{-n_h}$.

If $A$ is an imprimitive matrix $A$ with index of imprimitivity $h$, then $A^h$ splits into $h$ primitive matrices with the same maximum eigenvalue: $A^h = \operatorname{diag} \{ A_1, \dots, A_h\}$. In this case you can use the same formula for matrices $A^{mh}$.

Perron's formula is a well known formula and can be found for instance in the book Gantmacher F.R. The Theory of Matrices, 1960, volume 1, page 116, formula (23') and a note for it. The proof of the statement about imprimitive matrices can be found in the same book volume 2 at page 82. There is a link for the book: Gantmacher F.R. The Theory of Matrices.

share|improve this answer

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.