Asymptotically analyzing growth rate of matrix entries

Question

I have the matrix $M=\begin{bmatrix} 1&1&0&0\\ 0&0&0&1\\ 1&1&0&0\\ 0&0&1&1 \end{bmatrix}$,

and I am trying to find asymptotic bounds for the entries in the matrix as we take $M$ to the $k$th power for $k>1$. It's pretty easy to show that each entry of $M^k$ does not exceed $2^{k-2}$. The Perron-Frobenius theorem tells us something about the exponential growth rate of the matrix in terms of the eigenvalue with the largest absolute value. Is it possible to get closer? Possibly an expression that is asymptotically equivalent to the entries?

Answer 1

$M^3$ is a positive matrix, therefore $M$ is primitive and $M^k$ is asymptotically equivalent to $\lambda^k A$ according to the Perron-Frobenius theorem. Let $r$ be the real root of $r^3 + r^2 - 1$, $\mathbf v$ and $\mathbf w$ the eigenvectors of $M$ and $M^t$ corresponding to $r + 1$, then $$M^k \sim \frac {(r + 1)^k} {\mathbf v \cdot \mathbf w} \mathbf v \mathbf w^t = \frac {(r + 1)^k} {3 - r^2} \begin{pmatrix} r^2 & r^2 & r^3 & r \\ r^3 & r^3 & r^4 & r^2 \\ r^2 & r^2 & r^3 & r \\ r & r & r^2 & 1 \end{pmatrix}.$$

Answer 2

You may prove by mathematical induction that for each $n\ge2$, $$ M^n=\pmatrix{ a_n&a_n&b_{n-1}&b_n\\ b_{n-1}&b_{n-1}&a_{n-1}&a_n\\ a_n&a_n&b_{n-1}&b_n\\ b_n&b_n&a_n&a_{n+1}\\ } $$ where $$ \pmatrix{a_1\\ b_0\\ a_0}=\pmatrix{1\\ 0\\ 0}, \quad \pmatrix{a_{n+1}\\ b_n\\ a_n} =\underbrace{\pmatrix{1&1&0\\ 0&1&1\\ 1&0&0}}_A\pmatrix{a_n\\ b_{n-1}\\ a_{n-1}}\text{ for } n\ge1. $$ It follows that both $\{a_n\},\{b_n\}$ are increasing sequences with $b_n\le a_{n+1}$ for every $n$. Therefore the maximum entry of $M^n$ is $a_{n+1}$, which is the top left entry of $A^n$. Hence you may diagonalise $A$ to find $a_{n+1}$.

More specifically, you can diagonalise $A$ as $PDP^{-1}$, where $D=\operatorname{diag}(\rho(A),\lambda,\bar{\lambda})$ is the eigenvalue matrix and the columns of $P$ are the corresponding eigenvectors of $A$. Scale the first column of $P$ so that $P(1,1)=1$. The first row of $P$ and the first column of $P^{-1}$ are then $(1,w,\bar{w})$ and $(x,z,\bar{z})^\top$ respectively for some real number $x$ and some complex numbers $w$ and $z$. Numerically, we have $x\approx0.41150,\ \rho(A)\approx1.75488$ and it also happens that $|\lambda|=\rho(A)-1<1$. Hence \begin{align} a_{n+1}=(A^n)_{11} &=x\rho(A)^n + 2\Re(wz\lambda^n),\\ &\sim x\rho(A)^n\\ &=0.41150\times1.75488^n. \end{align}