Matrix exponentiation for recurrences
A linear recurrence is a matrix; raise it to the nth power by squaring.
M^n applied to the base vector gives the nth term.
01The intuition
Start with what you would do by hand
The Fibonacci numbers start 0, 1 and each one after that is the sum of the two before: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. The tenth is 55. By hand you add your way up, which is 10 additions and takes a few seconds. Now find the billionth Fibonacci number modulo 109 + 7. A billion additions is too many. The step "add the last two" is the same every time, so a billion identical steps feels like something that should collapse into a few big steps, the way a billion multiplications by 2 collapse into thirty squarings.
Build the structure, one piece at a time
Piece one: write the state as a pair. At any point you only need the last two numbers, (Fn+1, Fn). The step turns it into (Fn+1 + Fn, Fn+1).
Piece two: notice the step is linear, so it can be written as a matrix multiplying the pair. Each new entry is a fixed combination of the old entries:
[ Fn+2 ; Fn+1 ] = [ 1 1 ; 1 0 ] · [ Fn+1 ; Fn ]
Call the 2 × 2 matrix M. Applying the step n times is multiplying by M n times, which is multiplying by Mn once. And Mn itself has the Fibonacci numbers inside it: Mn = [ Fn+1 Fn ; Fn Fn−1 ].
Piece three: compute M10 by squaring, exactly as for numbers. Write 10 in binary, 1010, keep a running result (start at the identity matrix) and a running base (start at M), square the base each round, and multiply it into the result when the current bit is 1:
| round | bit | result | base after squaring |
|---|---|---|---|
| 1 | 0 | identity | [2 1; 1 1] = M2 |
| 2 | 1 | [2 1; 1 1] | [5 3; 3 2] = M4 |
| 3 | 0 | [2 1; 1 1] | [34 21; 21 13] = M8 |
| 4 | 1 | [2 1; 1 1] · [34 21; 21 13] = [89 55; 55 34] | done |
The top-right entry of M10 is 55, which is F10. Four matrix multiplications instead of ten additions, and for n = 109 about sixty matrix multiplications instead of a billion additions.
Why it is correct
The invariant is the one from fast exponentiation, now for matrices: result · baseexp = Mn at the start of every round. It holds at the start (identity · Mn) and each round preserves it, because squaring the base and halving the exponent leaves baseexp unchanged, and an odd exponent first moves one factor into the result. Matrix multiplication is associative, which is all the argument needs; it is not commutative, so always multiply in the same order.
That Mn holds (Fn+1, Fn, Fn, Fn−1) follows by induction: it is true for n = 1, and multiplying by M once more adds the two top entries and shifts, which is one Fibonacci step in each column.
Why it is fast
Squaring halves the exponent, so there are ⌊log2 n⌋ + 1 rounds. Multiplying two k × k matrices costs k3 multiplications, and each round does at most two:
time = O(k3 log n), here k = 2
Taking every entry modulo 109 + 7 after each multiplication keeps the numbers small. Any recurrence where the next term is a fixed linear combination of the previous k terms fits, with a k × k matrix: a shifted identity below the top row, and the coefficients in the top row.
How to recognise it in an interview
Cues: a recurrence like "ways to reach step n from steps n − 1 and n − 2", "count strings of length n where each letter can be followed by certain letters", together with an n far too large to loop over, often 109 or more. Say: "the recurrence is linear with constant coefficients, so n steps are one matrix power, computed by squaring in logarithmic time".
Fibonacci Number and Climbing Stairs are the 2 × 2 case above. Knight Dialer is a 10 × 10 matrix where entry (i, j) is 1 when a knight can move from key i to key j; the count of dialable numbers of length n is the sum of all entries of that matrix to the power n − 1.
02The idea in one line
A linear recurrence is a matrix; raise it to the nth power by squaring.
Reach for it when: Fibonacci in O(log n), climbing stairs, counting strings of length n.
Cost: O(k³ log n) time.
03The walk-through, step by step
The video works one example: Fibonacci(10) via [[1,1],[1,0]]^10. These are its captions in order, so you can follow without the video or check a step you missed.
- Fibonacci is a linear recurrence, so n steps = one matrix power
- Write 10 in binary: 1010; square the base, multiply in where a bit is 1
- bit is 0: result unchanged
- square the base → [[2, 1], [1, 1]]; exp becomes 5
- bit is 1: result = result × base = [[2, 1], [1, 1]]
- square the base → [[5, 3], [3, 2]]; exp becomes 2
- bit is 0: result unchanged
- square the base → [[34, 21], [21, 13]]; exp becomes 1
- bit is 1: result = result × base = [[89, 55], [55, 34]]
- M^10 = [[89, 55], [55, 34]]: the top-right entry is F(10) = 55
- Only ⌈log₂ n⌉ squarings: O(k³ log n) for a k×k matrix
04Asked at Google
4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Climbing Stairs | Easy | 63 | last 6 months |
| Fibonacci Number | Easy | 46 | last 6 months |
| Knight Dialer | Medium | 26 | |
| Number of Ways to Stay in the Same Place After Some Steps | Hard | 18 |
05Related patterns
Other patterns in Advanced Structures: Segment tree (range query + point update), Fenwick tree (binary indexed tree), Ordered set / sorted container, Bucketing by value range, Meet in the middle.