--- title: Matrix Exponentiation module: Mathematical Algorithms moduleNumber: 10 lessonNumber: 5 order: 1005 summary: | A linear recurrence advances by a fixed linear rule, so one step is a **matrix–vector** product and $n$ steps are a **matrix power**. Packaging Fibonacci, and any $k$-term recurrence, into a transition matrix lets us jump to the $n$-th term in $O(k^3 \log n)$ by **exponentiation by squaring** — the same doubling trick from modular exponentiation, now over matrices. topics: [Number Theory] sources: - book: CLRS ref: "Ch. 4 — Divide-and-Conquer (matrix powering); §31.6 (repeated squaring)" - book: Skiena ref: "§ — Number Theory / Dynamic Programming" - book: Erickson ref: "Ch. — (linear recurrences)" practice: - title: 'Fibonacci Number' slug: fibonacci-number difficulty: Easy - title: 'Climbing Stairs' slug: climbing-stairs difficulty: Easy - title: 'Count Vowels Permutation' slug: count-vowels-permutation difficulty: Hard - title: 'Student Attendance Record II' slug: student-attendance-record-ii difficulty: Hard --- [Modular exponentiation](/algorithms/mathematical-algorithms/modular-exponentiation-and-primality) computed $a^n$ in $O(\log n)$ multiplications by reading the bits of $n$ and **repeatedly squaring**. That lesson noted that the doubling idea is not special to integers: replace "multiply" with "matrix multiply" and the same loop computes the $n$-th **Fibonacci number** in $O(\log n)$ steps. This lesson makes that precise and general. A **linear recurrence** — a rule that builds each term from a fixed linear combination of the previous few — is repeated application of one fixed matrix. Computing the $n$-th term is then computing the $n$-th power of that matrix, and exponentiation by squaring does it in logarithmic time. ## A recurrence is a matrix Start with Fibonacci: $F_0 = 0$, $F_1 = 1$, and $F_{n} = F_{n-1} + F_{n-2}$. The naive loop is $\Theta(n)$ additions, and the closed form (Binet's formula) involves irrational powers of the golden ratio, awkward to evaluate exactly. Instead, package two **consecutive** terms into a state vector and ask what one step does to it. The update $F_{n+1} = F_n + F_{n-1}$ together with the trivial $F_n = F_n$ is a linear map: $$ \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}. $$ Call that $2\times2$ matrix $M$. One multiplication by $M$ advances the state by one term. Two multiplications advance it by two. Applying $M$ a total of $n$ times to the initial state $\brackets{\begin{smallmatrix}F_1\\F_0\end{smallmatrix}} = \brackets{\begin{smallmatrix}1\\0\end{smallmatrix}}$ lands on $\brackets{\begin{smallmatrix}F_{n+1}\\F_n\end{smallmatrix}}$. So the whole question reduces to computing the **matrix power** $M^n$. $$ % caption: One step of the Fibonacci map. The state holds two consecutive terms; multiplying % by $M$ slides the window forward by one, so $n$ applications carry % $[F_1, F_0]^\top$ to $[F_{n+1}, F_n]^\top$ \begin{tikzpicture}[ every node/.style={font=\small}, st/.style={draw, minimum width=16mm, minimum height=14mm, inner sep=2pt, align=center, fill=acc!8}, >=stealth, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} \node[st] (v0) at (0,0) {$F_1$\\[2pt] $F_0$}; \node[st] (v1) at (3.4,0) {$F_2$\\[2pt] $F_1$}; \node[st] (v2) at (6.8,0) {$F_3$\\[2pt] $F_2$}; \node[st, fill=acc!18, draw=acc, very thick] (vn) at (10.6,0) {$F_{n+1}$\\[2pt] $F_n$}; \draw[->, acc, thick] (v0) -- node[above, font=\footnotesize] {times M} (v1); \draw[->, acc, thick] (v1) -- node[above, font=\footnotesize] {times M} (v2); \draw[->, acc, thick, dashed] (v2) -- node[above, font=\footnotesize] {n steps} (vn); \end{tikzpicture} $$ > **Claim (Fibonacci by powers).** With $M = \brackets{\begin{smallmatrix}1&1\\1&0\end{smallmatrix}}$, > $$M^{n} = \begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{bmatrix}.$$ > **Proof.** Induction on $n$. The base $n=1$ reads > $M = \brackets{\begin{smallmatrix}F_2&F_1\\F_1&F_0\end{smallmatrix}} > = \brackets{\begin{smallmatrix}1&1\\1&0\end{smallmatrix}}$, true. For the step, assume > the claim for $n$ and multiply by $M$ once more: > $$M^{n+1} = M\cdot M^{n} = \begin{bmatrix}1&1\\1&0\end{bmatrix} \begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix} = \begin{bmatrix}F_{n+1}+F_{n}&F_{n}+F_{n-1}\\F_{n+1}&F_{n}\end{bmatrix} = \begin{bmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_{n}\end{bmatrix},$$ > using $F_{n+1}+F_n = F_{n+2}$ in each top entry. That is exactly $M^{n+1}$ in the claimed > form. $\qed$ The top-right entry of $M^n$ is $F_n$ directly, so once we can raise $M$ to the $n$-th power we can read off $F_n$ with no vector multiply at all. It remains to compute $M^n$ fast. ## Exponentiation by squaring, over matrices Matrix multiplication is **associative**, which is the only property repeated squaring ever used. So the entire argument from the modular-exponentiation lesson carries over verbatim with the scalar product replaced by the matrix product and the scalar $1$ replaced by the identity matrix $I$. Write $n$ in binary as $n = \sum_i b_i 2^i$; then $$ M^{n} = \prod_{i \,:\, b_i = 1} M^{2^i}, $$ where the powers $M^{2^i}$ are the **repeated squares** of $M$, each the square of the previous. Sweeping the bits of $n$ from low to high, we keep a running square and fold it into an accumulator whenever the bit is set. $$ % caption: One multiply doubles the exponent. Each box is the square of the one before it, % so the reachable power grows $M, M^2, M^4, M^8, \dots$ — only $\log_2 n$ boxes % to reach $M^n$ \begin{tikzpicture}[ every node/.style={font=\small}, pw/.style={draw=acc, very thick, fill=acc!12, minimum width=14mm, minimum height=10mm, inner sep=2pt}, >=stealth, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} \node[pw] (p0) at (0,0) {$M$}; \node[pw] (p1) at (2.6,0) {$M^2$}; \node[pw] (p2) at (5.2,0) {$M^4$}; \node[pw] (p3) at (7.8,0) {$M^8$}; \node[acc, font=\footnotesize] (dots) at (9.8,0) {and so on}; \draw[->, acc, thick] (p0) -- node[above, font=\footnotesize] {square} (p1); \draw[->, acc, thick] (p1) -- node[above, font=\footnotesize] {square} (p2); \draw[->, acc, thick] (p2) -- node[above, font=\footnotesize] {square} (p3); \draw[->, acc, thick] (p3) -- (dots); \end{tikzpicture} $$ $$ % caption: Doubling on matrices: each square halves the exponent's remaining bits; the % set bits of $n=13=1101_2$ select which squares multiply into the accumulator \begin{tikzpicture}[ every node/.style={font=\small}, box/.style={draw, minimum width=13mm, minimum height=7mm, inner sep=2pt}, >=stealth] \definecolor{acc}{HTML}{2348F2} \node (lab) at (-1.9,0.4) {$n=13$}; \node (lab2) at (-1.9,-0.1) {$=1101_2$}; \node[box] (b0) at (0,0) {$b_0{=}1$}; \node[box] (b1) at (0,-1) {$b_1{=}0$}; \node[box] (b2) at (0,-2) {$b_2{=}1$}; \node[box] (b3) at (0,-3) {$b_3{=}1$}; \node[box] (s0) at (3,0) {$M$}; \node[box] (s1) at (3,-1) {$M^2$}; \node[box] (s2) at (3,-2) {$M^4$}; \node[box] (s3) at (3,-3) {$M^8$}; \draw[->] (s0) -- node[right, font=\footnotesize] {square} (s1); \draw[->] (s1) -- node[right, font=\footnotesize] {square} (s2); \draw[->] (s2) -- node[right, font=\footnotesize] {square} (s3); \node[box, fill=acc!15, draw=acc, very thick] (r) at (7,-1.5) {$M\,M^4\,M^8=M^{13}$}; \draw[->, draw=acc, thick] (s0.east) -- (r.west); \draw[->, draw=acc, thick] (s2.east) -- (r.west); \draw[->, draw=acc, thick] (s3.east) -- (r.west); \end{tikzpicture} $$ There are $\lfloor\log_2 n\rfloor + 1$ squarings and at most that many accumulator multiplications, so $O(\log n)$ matrix multiplications in all. Each multiplication of two $k\times k$ matrices is $\Theta(k^3)$ by the schoolbook method, giving the headline cost. > **Theorem (Linear recurrence in logarithmic time).** A linear recurrence of order $k$ > can be advanced $n$ steps using $O(\log n)$ multiplications of $k\times k$ matrices, in > total time $O(k^3 \log n)$. For Fibonacci $k=2$, so this is a flat $O(\log n)$ — exponentially faster than the $\Theta(n)$ loop once $n$ is large, and exact (only integer arithmetic, no floating-point golden ratio). The schoolbook $\Theta(k^3)$ per product can be shaved to $\Theta(k^{2.807})$ with [Strassen's algorithm](/algorithms/divide-and-conquer/mergesort), but for the small $k$ typical of recurrences the constant-factor simplicity of the cubic method wins. ```algorithm caption: $\textsc{Mat-Pow}(M, n)$ — $M^n$ by repeated squaring, $O(k^3 \log n)$ number: 1 $R \gets I$ // identity, the accumulator while $n > 0$ do if $n \bmod 2 = 1$ then // low bit set $R \gets R \cdot M$ // fold running square into result $M \gets M \cdot M$ // square for next bit $n \gets \lfloor n / 2 \rfloor$ return $R$ ``` ::impl{algo="matrix_power"} The loop is byte-for-byte the iterative $\textsc{ModPow}$ from the previous lesson, with the scalar identity $1$ swapped for the matrix identity $I$ and `$\cdot$` now meaning matrix multiply. To compute a recurrence **modulo a prime** — the usual demand when the true terms overflow — reduce every entry mod $p$ after each multiply, exactly as $\textsc{ModPow}$ reduces after each scalar product. **Worked example ($F_{10}$ by squaring).** Take $M = \brackets{\begin{smallmatrix} 1&1\\1&0\end{smallmatrix}}$ and compute $M^{10}$; the top-right entry is $F_{10} = 55$. The exponent is $10 = 1010_2$, so the set bits are at positions $1$ and $3$. Build the repeated squares: $$ M^1 = \begin{bmatrix}1&1\\1&0\end{bmatrix},\quad M^2 = \begin{bmatrix}2&1\\1&1\end{bmatrix},\quad M^4 = \begin{bmatrix}5&3\\3&2\end{bmatrix},\quad M^8 = \begin{bmatrix}34&21\\21&13\end{bmatrix}. $$ Each is the square of the previous — for instance $M^4 = (M^2)^2$ has top-left $2\cdot2 + 1\cdot1 = 5$. The bits select $M^2$ and $M^8$, so $$ M^{10} = M^8 \cdot M^2 = \begin{bmatrix}34&21\\21&13\end{bmatrix} \begin{bmatrix}2&1\\1&1\end{bmatrix} = \begin{bmatrix}89&55\\55&34\end{bmatrix}, $$ and reading the entries confirms $F_{11}=89$, $F_{10}=55$, $F_9=34$ — the Fibonacci identity $M^n = \brackets{\begin{smallmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{smallmatrix}}$ in a single squaring chain of four multiplies instead of ten additions. The gap only widens with $n$: reaching $F_{10^{18}} \bmod p$ is $\approx 60$ multiplies, not $10^{18}$ additions. $$ % caption: $M^{10}$ from two of four repeated squares. Bits $1$ and $3$ of % $10=1010_2$ select $M^2$ and $M^8$; their product is $M^{10}$, whose entries % are $F_{11},F_{10},F_9$. \begin{tikzpicture}[ every node/.style={font=\small}, box/.style={draw, minimum width=13mm, minimum height=7mm, inner sep=2pt}, >=stealth, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-2.4,0.7) rectangle (8.4,-3.7); \node (lab) at (-1.7,0.4) {$n=10$}; \node (lab2) at (-1.7,-0.1) {$=1010_2$}; \node[box] (b0) at (0,0) {$b_0{=}0$}; \node[box] (b1) at (0,-1) {$b_1{=}1$}; \node[box] (b2) at (0,-2) {$b_2{=}0$}; \node[box] (b3) at (0,-3) {$b_3{=}1$}; \node[box] (s0) at (3,0) {$M$}; \node[box, fill=acc!15, draw=acc, very thick] (s1) at (3,-1) {$M^2$}; \node[box] (s2) at (3,-2) {$M^4$}; \node[box, fill=acc!15, draw=acc, very thick] (s3) at (3,-3) {$M^8$}; \draw[->] (s0) -- node[right, font=\footnotesize] {square} (s1); \draw[->] (s1) -- node[right, font=\footnotesize] {square} (s2); \draw[->] (s2) -- node[right, font=\footnotesize] {square} (s3); \node[box, fill=acc!15, draw=acc, very thick] (r) at (6.8,-2) {$M^2 M^8 = M^{10}$}; \draw[->, draw=acc, thick] (s1.east) -- (r.west); \draw[->, draw=acc, thick] (s3.east) -- (r.west); \end{tikzpicture} $$ ## The general $k$-term recurrence Nothing above used $k=2$. Suppose a sequence obeys an order-$k$ linear recurrence with fixed coefficients $c_1,\dots,c_k$, $$ a_{n} = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}. $$ Carry the last $k$ terms as the state vector $v_n = (a_n, a_{n-1}, \dots, a_{n-k+1})^{\!\top}$. The new top entry is the recurrence itself; every other entry is just a copy shifted down by one. That "compute the combination on top, shift the rest down" rule is a single matrix, the **companion matrix** of the recurrence: $$ \underbrace{\begin{bmatrix} c_1 & c_2 & c_3 & \cdots & c_k \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix}}_{C} \begin{bmatrix} a_{n-1} \\ a_{n-2} \\ \vdots \\ a_{n-k} \end{bmatrix} = \begin{bmatrix} a_{n} \\ a_{n-1} \\ \vdots \\ a_{n-k+1} \end{bmatrix}. $$ The top row holds the coefficients and produces $a_n$; the **sub-diagonal** of $1$s copies each old term down one slot, discarding the oldest. The figure makes the two roles visible: one row that mixes, and a staircase of $1$s that shifts. $$ % caption: Companion matrix of an order-$3$ recurrence: top row mixes by the coefficients, % the sub-diagonal of $1$s shifts the state down one slot \begin{tikzpicture}[ every node/.style={font=\small}, cell/.style={draw, minimum width=10mm, minimum height=8mm, inner sep=1pt}, >=stealth, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} % matrix cells, 3x3 \node[cell, fill=acc!28, draw=acc, very thick] (a) at (0,0) {$c_1$}; \node[cell, fill=acc!28, draw=acc, very thick] (b) at (1,0) {$c_2$}; \node[cell, fill=acc!28, draw=acc, very thick] (c) at (2,0) {$c_3$}; \node[cell, fill=acc!8] at (0,-1) {$1$}; \node[cell] at (1,-1) {$0$}; \node[cell] at (2,-1) {$0$}; \node[cell] at (0,-2) {$0$}; \node[cell, fill=acc!8] at (1,-2) {$1$}; \node[cell] at (2,-2) {$0$}; % role labels \node[acc, font=\footnotesize, anchor=west] at (2.8,0) {mix: new top term}; \node[acc, font=\footnotesize, anchor=west] at (2.8,-1.5) {shift: copy down one}; \draw[acc, thick, ->] (0.35,-0.95) -- (0.65,-1.65); \draw[acc, thick, ->] (1.35,-1.95) -- (1.65,-2.05); \end{tikzpicture} $$ Then $v_n = C^{n-k+1} v_{k-1}$ where $v_{k-1}$ holds the $k$ given initial terms, and $\textsc{Mat-Pow}$ delivers $C$'s power in $O(k^3\log n)$. The pattern generalizes: counting problems whose answer satisfies a fixed linear recurrence — tilings, constrained strings, walk counts — are all handled this way. _Climbing Stairs_ is literally Fibonacci; _Count Vowels Permutation_ and _Student Attendance Record II_ track a constant number of states whose transitions are linear, so each is a small companion (or transfer) matrix raised to the $n$-th power.[^skiena-lr] ::impl{algo="linear_recurrence"} > **Remark (Affine and inhomogeneous recurrences).** A recurrence with a constant added, > $a_n = c_1 a_{n-1} + \dots + c_k a_{n-k} + d$, is still handled by appending a constant > $1$-entry to the state and a row that carries the $d$: the augmented matrix stays fixed, > so the same power trick applies. Any recurrence whose update is **affine** in a bounded > state can be exponentiated. **Worked example (a $2\times1$ tiling count).** The number of ways to tile a $2\times n$ board with dominoes obeys $T_n = T_{n-1} + T_{n-2}$ with $T_0 = T_1 = 1$ — a shifted Fibonacci. A richer case is the $3$-term **tribonacci** count $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ with $a_0=0, a_1=a_2=1$, whose companion matrix is $$ C = \begin{bmatrix} 1&1&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}. $$ The top row adds the last three terms; the two sub-diagonal $1$s shift the window. Starting from $v_2 = (a_2,a_1,a_0)^\top = (1,1,0)^\top$, one multiply gives $C v_2 = (1{+}1{+}0,\,1,\,1)^\top = (2,1,1)^\top = (a_3,a_2,a_1)^\top$, so $a_3 = 2$; another gives $a_4 = 2+1+1 = 4$, then $a_5 = 4+2+1 = 7$. To leap to $a_{n}$ directly, raise $C$ to the $n-2$ power by $\textsc{Mat-Pow}$: $a_{60}$ is $58$ matrix multiplies of a fixed $3\times3$ matrix, independent of how large the terms grow. ## Graph walks: the same matrix, a different reading The companion matrix is one instance of a broader principle: whenever a process advances by a **fixed linear rule**, its $n$-step behaviour is a matrix power. The cleanest other instance is **counting walks in a graph**. Let $A$ be the adjacency matrix of a graph, so $A_{ij}=1$ when there is an edge $i\to j$. Then the matrix power counts paths: > **Theorem (Walk counting).** $(A^{n})_{ij}$ equals the number of walks of length exactly > $n$ from vertex $i$ to vertex $j$. > **Proof.** Induction on $n$. For $n=1$, $(A)_{ij}$ is $1$ or $0$, the number of length-$1$ > walks. For the step, a walk of length $n+1$ from $i$ to $j$ is a walk of length $n$ from > $i$ to some neighbour $\ell$ followed by the edge $\ell\to j$. Summing over $\ell$, > $(A^{n+1})_{ij} = \sum_{\ell} (A^{n})_{i\ell}\, A_{\ell j}$, the very > definition of the matrix product $A^n\cdot A$. $\qed$ $$ % caption: Walk counting as matrix product. Every length-$(n+1)$ walk from $i$ to $j$ is a % length-$n$ walk from $i$ to some neighbour $\ell$ followed by the edge % $\ell\!\to\! j$; summing over $\ell$ is exactly $(A^{n+1})_{ij}=\sum_\ell (A^n)_{i\ell}A_{\ell j}$ \begin{tikzpicture}[ every node/.style={font=\small}, v/.style={circle, draw=acc, very thick, fill=acc!12, minimum size=10mm, inner sep=1pt}, m/.style={circle, draw=acc, fill=acc!8, minimum size=8mm, inner sep=1pt}, >=stealth, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} \node[v] (i) at (0,0) {$i$}; \node[m] (l1) at (4,1.4) {$v_1$}; \node[m] (l2) at (4,0) {$v_2$}; \node[m] (l3) at (4,-1.4) {$v_3$}; \node[v] (j) at (8,0) {$j$}; % length-n walks from i to each neighbour \draw[->, acc, thick, dashed] (i) -- node[above, font=\footnotesize, sloped] {n steps} (l1); \draw[->, acc, thick, dashed] (i) -- (l2); \draw[->, acc, thick, dashed] (i) -- node[below, font=\footnotesize, sloped] {n steps} (l3); % final edge into j \draw[->, acc, thick] (l1) -- (j); \draw[->, acc, thick] (l2) -- node[above, font=\footnotesize, sloped] {one edge} (j); \draw[->, acc, thick] (l3) -- (j); \end{tikzpicture} $$ **Worked example (counting length-$2$ walks).** Take the triangle-with-a-tail graph on vertices $\{1,2,3\}$ with edges $1\!-\!2$, $2\!-\!3$, $1\!-\!3$ (an undirected triangle), adjacency matrix $$ A = \begin{bmatrix}0&1&1\\1&0&1\\1&1&0\end{bmatrix},\qquad A^2 = \begin{bmatrix}2&1&1\\1&2&1\\1&1&2\end{bmatrix}. $$ Read $(A^2)_{11} = 2$: there are exactly two length-$2$ walks from vertex $1$ back to itself, namely $1\!\to\!2\!\to\!1$ and $1\!\to\!3\!\to\!1$. The off-diagonal $(A^2)_{12} = 1$ counts the single length-$2$ walk $1\!\to\!3\!\to\!2$. Every entry is a sum over the intermediate vertex $\ell$, exactly $\sum_\ell A_{1\ell}A_{\ell 2}$, and raising $A$ to higher powers counts longer walks with no new idea — just more multiplies, each delivered in $O(\log n)$ of them by $\textsc{Mat-Pow}$. So "how many length-$n$ walks?" is answered in $O(V^3 \log n)$ by raising $A$ to the $n$-th power with $\textsc{Mat-Pow}$ — and the companion-matrix recurrence above is just this theorem applied to the small state-transition graph of the recurrence. The same $O(V^3\log n)$ power, taken over the **boolean semiring** (replace $+$ with OR, $\times$ with AND), computes reachability within $n$ steps; over the **min-plus semiring** (replace $+$ with $\min$, $\times$ with $+$) it computes shortest-path lengths, which underlies the all-pairs shortest-path algorithms. ::impl{algo="walk_counting,semiring_power"} ## Faster recurrence solvers and the semiring view Matrix powering is the textbook route to a linear recurrence's $n$-th term, but it is neither the only route nor always the fastest. **Faster than cubic: Kitamasa and Fiduccia.** The $O(k^3\log n)$ cost is dominated by full $k\times k$ multiplies. But the answer $a_n$ is a fixed linear combination of the first $k$ terms, and the coefficients of that combination are the residue of $x^n$ modulo the recurrence's **characteristic polynomial** $x^k - c_1 x^{k-1} - \dots - c_k$. Computing $x^n \bmod$ that polynomial by repeated squaring of _polynomials_ — the **Fiduccia / Kitamasa** method — costs $O(k^2\log n)$ with schoolbook polynomial multiplication, and $O(k\log k\log n)$ when the polynomial products use the [FFT](/algorithms/mathematical-algorithms/fast-fourier-transform).[^fiduccia] For a recurrence of large order $k$ this is a decisive improvement over the cubic matrix approach. **Eigen-decomposition and Binet's formula.** If the companion matrix is diagonalizable, $C = P\,D\,P^{-1}$ with $D$ diagonal, then $C^n = P\,D^n\,P^{-1}$ and $D^n$ is just the eigenvalues raised to the $n$-th power. For Fibonacci the eigenvalues are the golden ratio $\varphi = \tfrac{1+\sqrt5}{2}$ and its conjugate, which recovers **Binet's formula** $F_n = (\varphi^n - \psi^n)/\sqrt5$ exactly. The closed form is exact on paper but numerically fragile (the irrational powers must be carried to high precision), which is why the integer matrix power, exact by construction, is the algorithm of choice.[^clrs-mat] **One idea, three algorithms.** The semiring view unifies several algorithms in this course. Over the ordinary ring, $A^n$ counts walks; over the **boolean** semiring $(\lor, \land)$ it computes reachability, and the repeated-squaring version is essentially **transitive closure**; over the **min-plus (tropical)** semiring $(\min, +)$ it computes shortest walks of bounded length, and squaring the distance matrix $\lceil\log n\rceil$ times gives the **repeated-squaring all-pairs shortest paths** algorithm that precedes Floyd–Warshall. The doubling trick on this page is the same one used in those graph algorithms. ## Takeaways - A **linear recurrence** of order $k$ is one fixed matrix applied repeatedly: pack the last $k$ terms into a state vector, and one step is a multiply by the **companion matrix** $C$ (top row = coefficients, sub-diagonal of $1$s = shift). - Computing the $n$-th term is computing $C^n$, done in $O(\log n)$ matrix multiplications by **exponentiation by squaring** — the identical bit-scanning loop as $\textsc{ModPow}$, with scalar $\cdot$ replaced by matrix $\cdot$ and $1$ by $I$. - Total cost is $O(k^3 \log n)$ (cubic per multiply, logarithmically many multiplies); for Fibonacci $k=2$ this is a flat $O(\log n)$, exact and overflow-free under a modulus. - The **same matrix power** counts **length-$n$ walks** in a graph via $(A^n)_{ij}$, and over other semirings (boolean, min-plus) computes reachability and shortest paths — one algebraic idea behind recurrences, walk-counting, and transitive closure. [^skiena-lr]: **Skiena**, § — Number Theory / Dynamic Programming: linear recurrences advanced by powering a transition matrix in $O(\log n)$ matrix multiplications; the companion-matrix construction. [^fiduccia]: C. M. Fiduccia, "An efficient formula for linear recurrences," _SIAM J. Computing_ **14**(1), 1985 — computing $a_n$ via $x^n$ modulo the characteristic polynomial; the same method is widely known in competitive programming as Kitamasa's algorithm. [^clrs-mat]: **CLRS**, Ch. 4 — Divide-and-Conquer: matrix powering for recurrences; and Problem 31-3 (Binet-style closed forms via eigenvalues) for the golden-ratio decomposition.