Fibonacci matrix (source code)

= Fibonacci matrix
{c}
{title2=$Q=\begin{pmatrix}1&1\\1&0\end{pmatrix}$}

= Fibonacci Q-matrix
{c}
{synonym}

With $F_0=0$, $F_1=1$, the <Fibonacci matrix> advances consecutive <Fibonacci numbers>:
$$
\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}=Q^n\begin{pmatrix}1\\0\end{pmatrix},\qquad
Q^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}\quad(n\geq1).
$$
Multiplying by $Q$ proves the formula by <induction>. Since <matrix powers> obey $Q^{m+n}=Q^mQ^n$, their entries give <Fibonacci addition formulas>. <Exponentiation by squaring> computes $Q^n$ with $O(\log n)$ <matrix multiplications>, including directly in <modular arithmetic>. The determinant identity $\det Q=-1$ also makes the update invertible modulo every <positive integer>.