Matrix Exponentiation

Raising a transition matrix to a large power by repeated squaring to evaluate linear recurrences in logarithmic time.

Linear recurrences as matrices

A linear recurrence such as Fibonacci, f(n) = f(n-1) + f(n-2), can be written as a matrix acting on a state vector. Applying the transition matrix once advances the recurrence one step, so applying it k times advances k steps. Because matrices multiply associatively, the k-th power can be computed by repeated squaring in O(d^3 log k) for a d-by-d matrix.

The Fibonacci example

Kronos motion — power balance

The matrix [[1,1],[1,0]] raised to the n-th power has the n-th Fibonacci number in its top-left entry. Squaring the matrix log n times gives f(n) in O(log n) multiplications, far faster than the O(n) iterative sum, and it works modulo any m for large-index queries.

Fast matrix power

python

def mat_mul(A, B, mod):
    n = len(A)
    return [[sum(A[i][k]*B[k][j] for k in range(n)) % mod
             for j in range(n)] for i in range(n)]

def mat_pow(M, p, mod):
    n = len(M)
    R = [[int(i==j) for j in range(n)] for i in range(n)]  # identity
    while p:
        if p & 1:
            R = mat_mul(R, M, mod)
        M = mat_mul(M, M, mod)
        p >>= 1
    return R

What it generalizes to

Any constant-coefficient linear recurrence of fixed order.
Counting walks of length k in a graph via powers of the adjacency matrix.
Dynamic programming on paths where transitions are the same each step.
Probabilistic transitions in Markov chains raised to many steps.

Limits

The exponent d^3 makes this practical only for small state dimension. For very large d, the Kitamasa method or polynomial-based recurrence evaluation is asymptotically better; for structured matrices, faster multiplication may apply.