Possible growth rates of a matrix entry with respect to exponentiation Let $A = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}$, so $A^n = \begin{pmatrix}1 & n \\ 0 & 1\end{pmatrix}$. Thus, $(A^n)_{1,1} = 1 = \Theta(1)$, and $(A^n)_{1,2} = n = \Theta(n)$.
Given a constant $c$, if $B = \begin{pmatrix} c/2 & c/2 \\ c/2 & c/2\end{pmatrix}$ then $B^n = \begin{pmatrix} c^n/2 & c^n/2 \\ c^n/2 & c^n/2\end{pmatrix}$. Thus, $(B^n)_{1,1} = c^n/2 = \Theta(c^n)$.
We have observed three possible growth rates of a particular entry with respect to the exponent of a matrix, constant, linear, and exponential. What other growth rates are possible? For example, does there exist an $m\times m$ matrix $C$ and indices $i,j$ such that $(C^n)_{i,j} = \Theta(n^2)$?
 A: Consider $A=I+S,$ where $S$ a matrix with entries $s_{i,i+1}=1$ and $0$ otherwise. If the dimension is equal $m,$ then $$A^n=I+ \sum_{k=1}^{m-1} {n\choose k}S^k$$ Thus $$(A^n)_{1,1+j}={n\choose j}\approx {n^j\over j!}\quad \qquad 1\le j\le m-1$$
A: Due to the Cayley-Hamilton theorem, matrix elements with respect to exponentiation adhere to the linear recurrence defined by the characteristic polynomial of a matrix. And a linear recurrence $A_0, A_1, \dots$ with the characteristic polynomial
$$
P(x) = \prod\limits_{i=1}^k (x-x_i)^{d_i},
$$
has a generic solution
$$
A_n = \sum\limits_{i=1}^k C_i(n) x_i^n,
$$
where $x_1 < x_2 < \dots < x_k$ are distinct roots of $P(x)$ and $C_i(x)$ are polynomials of degree at most $d_i-1$.
With such characteristic polynomial, the asymptotics of $A_n$ is estimated as $A_n \in O(n^{d_i-1} x_k^n)$.
So, all possible growth rates have a form of $\Theta(n^d c^n)$, the simplest possible example to such growth rate is the Jordan cell that has a size $d+1$ and a characteristic polynomial $(x-c)^{d+1}$.
$$
J_{c,{d+1}} = \begin{pmatrix}
c & 1       & 0      & \cdots  & 0 \\
0       & c & 1      & \cdots  & 0 \\
\vdots  & \vdots  & \vdots & \ddots  & \vdots \\
0       & 0       & 0      & c & 1      \\
0       & 0       & 0      & 0       & c
\end{pmatrix}.
$$
Another common example is the companion matrix of the polynomial $(x-c)^{d+1} = x^{d+1}+\sum\limits_{i=0}^{d} a_i x^i$:
$$
C((x-c)^{d+1})=\begin{pmatrix}
0 & 0 & \dots & 0 & -a_0 \\
1 & 0 & \dots & 0 & -a_1 \\
0 & 1 & \dots & 0 & -a_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \dots & 1 & -a_{d}
\end{pmatrix}.
$$
