= Fibonacci powers of the cat-map matrix
{c}
{title2=$A^n=\begin{pmatrix}F_{2n+1}&F_{2n}\\F_{2n}&F_{2n-1}\end{pmatrix}$}
Use the standard <Fibonacci number> convention $F_0=0$, $F_1=1$, $F_{m+1}=F_m+F_{m-1}$. For the <cat map> matrix,
$$
A^n=\begin{pmatrix}F_{2n+1}&F_{2n}\\F_{2n}&F_{2n-1}\end{pmatrix},\qquad n\geq1.
$$
At $n=1$, the right side is $\begin{pmatrix}2&1\\1&1\end{pmatrix}$. To prove the induction step, multiply it by $A$. The top-left entry becomes $2F_{2n+1}+F_{2n}=F_{2n+3}$, the top-right becomes $F_{2n+1}+F_{2n}=F_{2n+2}$, and the lower row follows from the same recurrence. This advances all indices by two.
For example, $A^2=\begin{pmatrix}5&3\\3&2\end{pmatrix}$, so two iterations send $(x,y)$ to $(5x+3y,3x+2y)$ <modulo> one. The formula turns repeated matrix multiplication into an explicit <integer> recurrence; the exponential growth of the <Fibonacci numbers> agrees with the expanding eigenvalue of the cat map.
Back to article page