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.

Function Contracts

mat_mul(a, b, mod) expects compatible matrices and a positive modulus. The number of columns in a must equal the number of rows in b.

mat_pow(matrix, exponent, mod) expects a square matrix and a non-negative exponent. It returns the matrix raised to that power under modular arithmetic.

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
 
 
def identity(size):
    result = [[0] * size for _ in range(size)]
    for i in range(size):
        result[i][i] = 1
    return result
 
 
def mat_pow(matrix, exponent, mod):
    result = identity(len(matrix))
    base = matrix
 
    while exponent > 0:
        if exponent % 2 == 1:
            result = mat_mul(result, base, mod)
        base = mat_mul(base, base, mod)
        exponent //= 2
 
    return result

mat_pow is the matrix version of fast exponentiation. It repeatedly squares the transition matrix and multiplies it into the result when the current exponent bit is set.

Fibonacci Example

The Fibonacci recurrence can be represented as:

[F(n + 1)]   [1 1] [F(n)]
[F(n)    ] = [1 0] [F(n - 1)]

Applying the same matrix repeatedly advances the state. Raising the matrix to a high power computes many recurrence steps at once.

Why It Works

Matrix multiplication can encode a fixed linear transition from one state vector to the next. Fast exponentiation applies that transition many times using repeated squaring.

This is the same exponentiation idea used for numbers, but the multiplication operation is matrix multiplication.

Complexity

For small fixed-size matrices, the main factor is O(log n) matrix multiplications. For a k * k matrix with ordinary multiplication, each multiplication costs O(k^3), so the total is O(k^3 log n).

Failure Example

Matrix exponentiation does not apply when the transition rule changes at each step or depends on a non-linear choice such as max over alternatives.

The method requires one fixed linear transition matrix that can be reused.

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.

Another common mistake is changing the transition at each step. Matrix exponentiation requires the same transition matrix to be reused.

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.

Do not use it when a simple loop is fast enough or when the transition is not linear and fixed.

The Main Point

Matrix exponentiation applies the same linear transition many times by using fast exponentiation on the transition matrix.