Matrix Exponentiation

Matrix Exponentiation

Many dynamic programming recurrences follow a simple pattern: the next value depends on a fixed number of previous values. When the number of steps n is small, a straightforward loop works fine. But when $n$ reaches $10^9$ or beyond, even an $O(n)$ loop is too slow. Matrix exponentiation transforms any constant-coefficient linear recurrence into a matrix power problem, solvable in $O(k^3 \log n)$ where $k$ is the number of terms in the recurrence.

Fibonacci as the Motivating Example

The Fibonacci recurrence is the simplest case:

F(n) = F(n-1) + F(n-2),   F(0) = 0, F(1) = 1

We can rewrite this as a matrix equation. At each step, we transform the state vector $[F(n), F(n-1)]$ into $[F(n+1), F(n)]$:

| F(n+1) |   | 1  1 |   | F(n)   |
| F(n)   | = | 1  0 | * | F(n-1) |

Call the $2 \times 2$ matrix $T$. Applying this transformation $n$ times from the base case gives:

| F(n+1) |       | 1 |
| F(n)   | = T^n | 0 |

So $F(n)$ is the bottom-left entry (row 1, column 0) of $T^n$. Computing $T^n$ via repeated squaring takes $O(\log n)$ matrix multiplications, each costing $O(2^3) = O(8)$ scalar operations. The total is $O(\log n)$, down from $O(n)$.

Walked Example: Fibonacci $F(5)$

Let $T = [[1,1],[1,0]]$. We compute $T^5$ by repeated squaring. Since $5 = 101_2$, we need $T^4 \cdot T^1$.

Step 1: Start with result = I (identity matrix) and base = T. $n = 5$.

Step 2: $n$ is odd. result = I * T = T = [[1,1],[1,0]]. Set $n = 4$, square base: $T^2 = [[2,1],[1,1]]$.

Step 3: $n$ is even. Skip multiply. Set $n = 2$, square base: $T^4 = [[5,3],[3,2]]$.

Step 4: $n$ is even. Skip multiply. Set $n = 1$, square base: $T^8$ (not needed).

Step 5: $n$ is odd. result = T * T^4 = T^5.

T^5 = [[1,1],[1,0]] * [[5,3],[3,2]] = [[8,5],[5,3]]

Reading $F(5)$ from position $[0][1]$ (or equivalently $[1][0]$): $F(5) = 5$. Correct.

The General Idea: Linear Recurrences as Matrices

Any linear recurrence of the form:

f(n) = c1*f(n-1) + c2*f(n-2) + ... + ck*f(n-k)

can be represented as a $k \times k$ transition matrix $T$:

| f(n)   |   | c1 c2 c3 ... ck |   | f(n-1) |
| f(n-1) |   | 1  0  0  ... 0  |   | f(n-2) |
| f(n-2) | = | 0  1  0  ... 0  | * | f(n-3) |
|  ...   |   | ...             |   |  ...   |
| f(n-k+1)|  | 0  0  0  ... 0  |   | f(n-k) |

The first row holds the coefficients. Each subsequent row shifts the state down by one position. Computing $T^n$ via binary exponentiation gives $f(n)$ in $O(k^3 \log n)$ time.

Implementation

The code consists of three pieces: matrix multiplication, matrix power via repeated squaring, and the recurrence solver.

MOD = 10**9 + 7

def mat_mul(A, B):
    """Multiply two k x k matrices mod MOD."""
    k = len(A)
    C = [[0] * k for _ in range(k)]
    for i in range(k):
        for j in range(k):
            for p in range(k):
                C[i][j] = (C[i][j] + A[i][p] * B[p][j]) % MOD
    return C

def mat_pow(M, n):
    """Compute M^n mod MOD using binary exponentiation."""
    k = len(M)
    result = [[int(i == j) for j in range(k)] for i in range(k)]  # identity
    while n > 0:
        if n & 1:
            result = mat_mul(result, M)
        M = mat_mul(M, M)
        n >>= 1
    return result

def fibonacci(n):
    if n <= 1:
        return n
    T = [[1, 1],
         [1, 0]]
    return mat_pow(T, n)[0][1]

The key insight in mat_pow is that it is identical to scalar binary exponentiation. The only difference is that scalar multiplication is replaced by matrix multiplication. Because matrix multiplication is associative, the repeated-squaring identity $(M^2)^{n/2} = M^n$ holds.

Application: Knight Dialer (LeetCode 935. Knight Dialer)

A chess knight is placed on a phone dial pad. Starting from any digit, it hops $n - 1$ times, each hop following an L-shaped knight move. Count how many distinct $n$-digit numbers can be dialed.

The phone pad layout determines which digits a knight can reach from each position:

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
|   | 0 |   |

The valid knight moves define a transition graph:

• From 0: can reach 4, 6
• From 1: can reach 6, 8
• From 2: can reach 7, 9
• From 3: can reach 4, 8
• From 4: can reach 0, 3, 9
• From 5: no reachable digits (isolated)
• From 6: can reach 0, 1, 7
• From 7: can reach 2, 6
• From 8: can reach 1, 3
• From 9: can reach 2, 4

We build a $10 \times 10$ transition matrix $T$ where $T[i][j] = 1$ if a knight on digit $j$ can hop to digit $i$. Then the number of $n$-digit numbers is the sum of all entries in $T^{n-1} \cdot v$, where $v = [1, 1, 1, ..., 1]^T$ (we can start on any digit).

def knight_dialer(n):
    if n == 1:
        return 10
    moves = {
        0: [4, 6],    1: [6, 8],    2: [7, 9],
        3: [4, 8],    4: [0, 3, 9], 5: [],
        6: [0, 1, 7], 7: [2, 6],    8: [1, 3],
        9: [2, 4]
    }
    # Build 10x10 transition matrix
    T = [[0] * 10 for _ in range(10)]
    for src, dsts in moves.items():
        for dst in dsts:
            T[dst][src] = 1  # column src -> row dst

    Tn = mat_pow(T, n - 1)

    # Sum all entries: each starting digit contributes
    # sum of its column in T^(n-1)
    total = 0
    for i in range(10):
        for j in range(10):
            total = (total + Tn[i][j]) % MOD
    return total

Without matrix exponentiation, you would use DP in $O(10 \cdot n)$ time. When $n$ can be $10^9$, that is far too slow. Matrix exponentiation solves it in $O(10^3 \cdot \log n) = O(1000 \cdot 30) \approx 30{,}000$ operations.

Building the Transition Matrix: A Checklist

When applying this technique to a new problem:

1. Identify the state vector. What quantities does the recurrence track? For Fibonacci it is $[F(n), F(n-1)]$. For Knight Dialer it is the count at each of the 10 digits.

1. Write the recurrence as a matrix equation. Each entry $T[i][j]$ describes how much state $j$ contributes to the next value of state $i$.

1. Verify the base case. Multiply $T$ by the initial state vector to confirm you get the correct next state.

1. Exponentiate. Compute $T^{n}$ (or $T^{n-1}$, depending on your indexing) and extract the answer from the result.

When to Use Matrix Exponentiation

This technique shines under specific conditions:

• $n$ is very large, typically $10^9$ or more, where even $O(n)$ is too slow.
• The recurrence has a small, fixed number of terms. The matrix is $k \times k$, so each multiplication is $O(k^3)$. If $k$ is 2 or 10 this is fast; if $k$ is 1000 it is not practical.
• The recurrence has constant coefficients. The transition matrix must be the same at every step. If the coefficients change with $n$, matrix exponentiation does not directly apply.

Common problem types: counting paths of length $n$ in a graph with $k$ nodes, linear recurrence evaluation, string counting with fixed-length forbidden patterns (via automaton states).

Complexity

• Time: $O(k^3 \log n)$ where $k$ is the matrix dimension and $n$ is the exponent. Each of the $O(\log n)$ squaring steps performs one $O(k^3)$ matrix multiplication.
• Space: $O(k^2)$ for storing the matrices.

For LeetCode 509. Fibonacci Number, $k = 2$, so the time is $O(8 \log n) = O(\log n)$. For LeetCode 935. Knight Dialer, $k = 10$, so each multiplication is $O(1000)$ and the total is $O(1000 \log n)$.

The tradeoff is clear: matrix exponentiation replaces an $O(n)$ loop with $O(k^3 \log n)$. When $k$ is small and $n$ is enormous, this is a dramatic win. When $k$ is large or $n$ is small, the overhead of matrix multiplication makes the naive loop faster.

Recognizing this pattern

You're probably looking at matrix exponentiation when:

• There is a linear recurrence with constant coefficients ($f(n) = a_1 f(n-1) + a_2 f(n-2) + \ldots$) and the problem asks for $f(n)$ where $n$ is up to $10^9$, $10^{15}$, or $10^{18}$.
• A standard $O(n)$ DP would be the obvious solution but $n$ is too large by orders of magnitude.
• The "state" feeding the recurrence is a small fixed-size vector, counts at each of $k$ graph nodes, or the last few values of a sequence, with $k$ at most a few dozen.
• The problem asks for an answer modulo a large prime, signaling that integer arithmetic over many iterations is expected.
• The transition can be described as "next state $=$ matrix $\cdot$ current state," and the matrix is the same at every step.

Common templates:

• Linear recurrence ($k$ previous terms): exponentiate the companion matrix. Example: Fibonacci Number.
• Count paths of length $n$ in a fixed graph: adjacency matrix raised to $n$. Example: Knight Dialer.
• Count strings of length $n$ avoiding a forbidden pattern: automaton-state transition matrix. Example: Student Attendance Record II.
• Tile / tromino counting with fixed transitions: encode column profiles as states, exponentiate the profile-transition matrix. Example: Domino and Tromino Tiling.
• Counting with periodic / modular constraints: recurrence with terms indexed modulo a small number, encoded into a vector state. Example: Count of Sub-Multisets With Bounded Sum.