Lesson 27 · Core algorithms

Matrix Exponentiation

Matrix exponentiation raises a transition matrix by repeated squaring, accelerating linear recurrences and fixed-state transitions to logarithmic time.

From recurrence to transition

A linear recurrence can package its recent values into a state vector. A fixed matrix maps state k to k+1; applying n steps is matrix power. Fibonacci uses [[1,1],[1,0]] on [F(k),F(k−1)].

The matrix must match state ordering and recurrence coefficients. Derive one transition by hand before exponentiating; a correct power routine cannot repair a wrong model.

State vectors hold recurrence memory
One matrix represents one step
Derive the transition explicitly

Binary powering

Initialize result to the identity matrix. While exponent is positive, multiply result by base on a set bit, square base, and halve exponent. Associativity makes the same exponentiation-by-squaring proof used for scalars apply to matrices.

Matrix multiplication is not commutative, so preserve multiplication order. For a constant d×d matrix, powering costs O(d³log n) with the classical product.

Identity is the neutral element
Set bits contribute powers
Order matters despite associativity

Key reference

Terms, operations, and practical uses

Linear transitions

State vectorState vector is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Transition matrixTransition matrix is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Companion matrixCompanion matrix is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Powering

Identity matrixIdentity matrix is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Repeated squaringRepeated squaring is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Exponent bitExponent bit is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Applications

Linear recurrenceLinear recurrence is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Walk countingWalk counting is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Affine transitionAffine transition is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Implementation

Binary matrix power accelerates Fibonacci

def mul(a,b):return [[sum(a[i][k]*b[k][j] for k in range(2)) for j in range(2)] for i in range(2)]
def power(a,n):
    r=[[1,0],[0,1]]
    while n:
        if n&1:r=mul(r,a)
        a=mul(a,a);n//=2
    return r
print("F(10):",power([[1,1],[1,0]],10)[0][1])

#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using M=array<array<long long,2>,2>;
M mul(M a,M b) {
    M c={};
    for(int i=0;i<2;i++) for(int k=0;k<2;k++) for(int j=0;j<2;j++) c[i][j]+=a[i][k]*b[k][j];
    return c;
}
int main() {
    M a={{{1,1},{1,0}}},r={{{1,0},{0,1}}};
    int n=10;
    while(n) {
        if(n&1) r=mul(r,a);
        a=mul(a,a);
        n/=2;
    }
    cout << "F(10): " << r[0][1] << '\n';
}

class Main {
    static long[][] mul(long[][] a,long[][] b) {
        long[][] c=new long[2][2];
        for(int i=0;i<2;i++) for(int k=0;k<2;k++) for(int j=0;j<2;j++) c[i][j]+=a[i][k]*b[k][j];
        return c;
    }
    public static void main(String[] args) {
        long[][] a={{1,1},{1,0}},r={{1,0},{0,1}};
        int n=10;
        while(n>0) {
            if((n&1)==1) r=mul(r,a);
            a=mul(a,a);
            n/=2;
        }
        System.out.println("F(10): "+r[0][1]);
    }
}

Watch it run

Step through it

Running on F(10)

Output

Modular multiplication

Competitive-programming recurrences often request results modulo m. Reduce every cell accumulation, using a wide intermediate or safe multiplication. Sparse or structured matrices can multiply faster than the dense triple loop.

Negative recurrence coefficients require normalized residues. A modulus of one yields an all-zero result matrix, including the reduced identity.

Reduce cell sums
Protect products from overflow
Exploit structure when present

Applications beyond Fibonacci

Transition matrices count walks of exact length: entry (i,j) of adjacency matrix power k counts k-edge walks. They accelerate finite automata, coupled recurrences, tiling states, and linear DP with huge step counts.

Affine recurrences add a constant coordinate fixed at one. Time-varying transitions cannot use one simple power unless they repeat in a pattern that can be grouped.

Adjacency powers count walks
Add a constant coordinate for affine terms
Transitions must be stationary

Boundaries and validation

Exponent zero must return identity; exponent one returns the original matrix. Test 1×1 matrices, zero matrices, negative coefficients under modulus, huge exponents, and dimension mismatch.

Compare small exponents with repeated multiplication and small recurrence indexes with ordinary DP. Clearly map the powered matrix back to the requested state coordinate to avoid off-by-one errors.

Test powers zero and one
Cross-check with iterative DP
Map exponent to recurrence index carefully

General transition construction

For an order-k recurrence, the first row contains coefficients and the subdiagonal shifts older state values. Verify that multiplying once maps [F(n),F(n−1),…] to [F(n+1),F(n),…]. Then exponent n−baseIndex advances exactly the required number of steps.

For huge sparse state systems, multiplying a vector by selected powers may be cheaper than forming the full powered matrix when only one initial state is queried. Precompute powers when many exponent queries share the same transition. Dimension and modulus are part of the matrix type’s contract.

Numerical matrices over floating point accumulate rounding error under repeated squaring. The exact algebraic technique remains valid, but stability becomes an additional concern. Integer recurrence pages should use exact or modular arithmetic, while numerical applications may need specialized linear-algebra routines.

Correctness follows by maintaining result·base^exponent equal to the original requested power. On an odd bit, moving one base factor into result preserves the invariant; squaring base while halving an even exponent does the same. At termination the remaining exponent is zero, so result is the full power. This proof also reveals why swapping multiplication order can be wrong for matrices even though scalar examples still pass. For recurrence code, test both matrix powers and recovered sequence terms, since the power routine may be correct while the state-vector orientation is transposed. Rectangular matrices cannot be exponentiated because repeated self-composition requires square dimensions. Reject incompatible dimensions before multiplication begins.

Companion matrices encode recurrences
Exponent equals transition count
Precompute powers for repeated queries