Matrix Exponentiation

Matrix exponentiation uses fast exponentiation on matrices to apply a linear transition many times.

It is useful when a recurrence can be represented as multiplying by the same transition matrix repeatedly.

Core Idea

If a state vector changes by the same linear rule each step, one step can be written as matrix multiplication. Many steps can then be computed by raising the matrix to a power.

Fast exponentiation reduces the number of matrix multiplications to logarithmic in the number of steps.

Python Example

def mat_mul(a, b, mod):
    rows = len(a)
    cols = len(b[0])
    mid = len(b)
    result = [[0] * cols for _ in range(rows)]
 
    for i in range(rows):
        for k in range(mid):
            for j in range(cols):
                result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % mod
 
    return result

This is the multiplication operation used inside matrix exponentiation.

Common Confusions

Matrix exponentiation is not needed for ordinary small recurrences. It becomes useful when the number of steps is huge.

The recurrence must be expressible as a fixed linear transition. Not every dynamic programming recurrence fits this form.

When To Use It

Use matrix exponentiation for large-step linear recurrences, transition counting, and problems where the same linear state update repeats many times.