Matrix Exponentiation Explained — Fibonacci and Linear Recurrences in O(log n) [LC 509, Google, Stripe]

Algorithm Statement#

Compute the $n$-th term of a linear recurrence $f(n) = c_1 f(n-1) + c_2 f(n-2) + \dots + c_k f(n-k)$ in $O(k^3 \log n)$ time using matrix exponentiation.

Pack the last $k$ states into a column vector, multiply by a $k \times k$ transition matrix $M$, and raise $M$ to the $n$-th power via fast exponentiation.

Constraints typical:

• $1 \le n \le 10^{18}$
• $1 \le k \le 100$ (so $k^3 = 10^6$ per matrix multiply)
• Modulus $10^9 + 7$

Example — Fibonacci:

F(n) = F(n-1) + F(n-2),  F(0) = 0, F(1) = 1
 
[F(n+1)]   [1 1]^n   [F(1)]
[F(n)  ] = [1 0]   * [F(0)]
 
n = 10 → F(10) = 55

Why This Problem Matters#

Linear recurrences are everywhere: Fibonacci, Tribonacci, tilings, dice-roll counts, paths in regular graphs, partition counts, even some game-theory positions. A naive DP takes $O(n)$. For $n = 10^{18}$, that is impossible. Matrix exponentiation drops the cost to $O(\log n)$ matrix multiplies, each costing $O(k^3)$.

Google asks "count strings over a small alphabet avoiding a substring" in $O(\log n)$, which reduces to matrix exponentiation on the KMP automaton. Stripe uses the technique to compute fee accumulations under recurring rules. Competitive programmers see it daily — it is the single most powerful "promote DP to log-time" trick in the interview canon.

The Core Insight#

Any linear recurrence of order $k$ can be written as a vector update:

For Fibonacci ($k = 2$):

Iterating gives

The trick: matrix multiplication is associative, so $M^n$ can be computed by binary exponentiation on the matrix exponent. We square the matrix at each step, taking $\log_2 n$ multiplies. Each multiply costs $k^3$ scalar operations.

Why it works. Linear recurrences correspond to discrete linear dynamical systems. The recurrence is a fixed linear map on the state vector; iterating it $n$ times is the $n$-th power of that map.

General template. For a $k$-th order recurrence $f(n) = c_1 f(n-1) + \dots + c_k f(n-k)$:

The first row encodes the recurrence; the lower diagonal shifts the state.

Visual Dry Run#

Compute $F(10) \bmod (10^9 + 7)$ with Fibonacci.

M = [[1, 1],
     [1, 0]]
 
M^2 = [[2, 1],
       [1, 1]]
 
M^4 = M^2 * M^2 = [[5, 3],
                   [3, 2]]
 
M^8 = M^4 * M^4 = [[34, 21],
                   [21, 13]]
 
M^9 = M^8 * M^1 = [[55, 34],
                   [34, 21]]
 
[F(10)]   [55 34] [F(1)]   [55 34] [1]   [55]
[F(9) ] = [34 21] [F(0)] = [34 21] [0] = [34]
 
F(10) = 55. Correct (sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55).

For $n = 10$, we used 4 squarings (M^2, M^4, M^8) and 1 multiply (M^8 * M^1) = 5 matrix multiplies, equal to $\lfloor \log_2 10 \rfloor + (\text{popcount}(10) - 1) = 4$. Matches the binary expansion of 10 = 1010.

Solution (Optimal)#

Python — Generic Matrix Exponentiation#

MOD = 10**9 + 7
 
def mat_mul(A, B, mod=MOD):
    n, k, m = len(A), len(B), len(B[0])
    C = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            s = 0
            for t in range(k):
                s += A[i][t] * B[t][j]
            C[i][j] = s % mod
    return C
 
def mat_pow(M, p, mod=MOD):
    n = len(M)
    result = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    while p > 0:
        if p & 1:
            result = mat_mul(result, M, mod)
        M = mat_mul(M, M, mod)
        p >>= 1
    return result
 
def fibonacci(n: int) -> int:
    if n == 0:
        return 0
    M = [[1, 1], [1, 0]]
    R = mat_pow(M, n - 1)
    # R * [F(1), F(0)]^T = [F(n), F(n-1)]^T → top entry
    return R[0][0]

Complexity: $O(k^3 \log n)$ time, $O(k^2)$ space.

JavaScript — Generic Matrix Exponentiation#

const MOD = 1_000_000_007n;
 
function matMul(A, B, mod = MOD) {
    const n = A.length, k = B.length, m = B[0].length;
    const C = Array.from({ length: n }, () => new Array(m).fill(0n));
    for (let i = 0; i < n; i++)
        for (let j = 0; j < m; j++) {
            let s = 0n;
            for (let t = 0; t < k; t++) s += A[i][t] * B[t][j];
            C[i][j] = s % mod;
        }
    return C;
}
 
function matPow(M, p, mod = MOD) {
    const n = M.length;
    let result = Array.from({ length: n }, (_, i) =>
        Array.from({ length: n }, (_, j) => (i === j ? 1n : 0n))
    );
    while (p > 0n) {
        if (p & 1n) result = matMul(result, M, mod);
        M = matMul(M, M, mod);
        p >>= 1n;
    }
    return result;
}
 
function fibonacci(n) {
    if (n === 0n) return 0n;
    const R = matPow([[1n, 1n], [1n, 0n]], n - 1n);
    return R[0][0];
}

Common Mistakes#

1. Wrong starting vector. Fibonacci needs $[F(1), F(0)]^T$ as the initial vector, multiplied by $M^{n-1}$. Off-by-one here gives $F(n+1)$ instead of $F(n)$.
2. Modulo on additions only. Accumulating $k$ products without modular reduction can overflow even long long when $k$ is large. Mod inside the inner loop.
3. Identity matrix initialization. The "result" must start as the identity, not the zero matrix or the input matrix.
4. Matrix multiplication is not commutative. Always multiply in the right order: result = result * M, not M * result.
5. Confusing $M^n$ with $M^{n-1}$. The mapping from $[F(1), F(0)]$ to $[F(n), F(n-1)]$ uses $M^{n-1}$; if you start from $[F(0), F(-1)]$ it is $M^n$.
6. Squaring inside if p & 1 branch. Square unconditionally each step, multiply only when the bit is set.
7. Allocating new matrices unnecessarily. For very tight contests, in-place multiplication into a temp buffer saves time.

Interview Tips#

• Spell out the transition: "I will represent the state as a vector and the transition as a matrix." This signals depth.
• Mention complexity in terms of $k$: "Each matrix multiply is $O(k^3)$, and we do $O(\log n)$ of them."
• For non-Fibonacci recurrences, draw the matrix on the whiteboard. Interviewers want to see you place coefficients correctly.
• If the recurrence has a forcing term (a non-homogeneous part), append a constant column to the state — a classic Stripe interview twist.

Follow-up Questions#

Q1: Solve Tribonacci $T(n) = T(n-1) + T(n-2) + T(n-3)$ for $n = 10^{18}$. A: $3 \times 3$ transition matrix with the first row $[1, 1, 1]$ and a $2 \times 2$ identity below. Same exponentiation technique.

Q2: Count walks of length $n$ in a graph with adjacency matrix $A$. A: (A^n)_{i,j} counts walks from $i$ to $j$ of length exactly $n$. Use matrix exponentiation.

Q3: Add a non-homogeneous term: $f(n) = 2 f(n-1) + 3$. A: Augment the state to $[f(n), 1]^T$ and use $M = [[2, 3], [0, 1]]$.

Q4: Why is matrix exponentiation $O(k^3 \log n)$ and not $O(k^2 \log n)$? A: Standard matrix multiply costs $O(k^3)$. Strassen reduces to $O(k^{2.81})$, but the constant overhead rarely pays off for small $k$.

Key Takeaways#

• Any linear recurrence of order $k$ becomes a matrix-vector update with a $k \times k$ transition matrix.
• Binary exponentiation on the matrix computes $M^n$ in $O(k^3 \log n)$ — fast enough for $n = 10^{18}$.
• For Fibonacci, the transition is $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$, and $F(n)$ is the top-left entry of $M^{n-1}$.
• Non-homogeneous terms are absorbed by appending a constant slot to the state vector and a corresponding row in $M$.
• The technique applies far beyond integer recurrences: count walks in graphs, paths in automata, transitions in Markov chains.
• Always reduce inside the inner-product loop to avoid 64-bit overflow when entries are large.