Matrix Exponentiation

Binary exponentiation on square matrices for solving linear recurrences in O(n^3 log k).

[Number Theory]|

Jul 9, 2026

|explanatory_notes.md|

#matrix#exponentiation#linear-recurrence#fibonacci

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;

struct Matrix {
    int n;
    vector<vector<ll>> mat;

    Matrix(int _n, bool identity = false) : n(_n), mat(_n, vector<ll>(_n, 0)) {
        if (identity)
            for (int i = 0; i < n; i++) mat[i][i] = 1;
    }

    Matrix operator*(const Matrix &o) const {
        Matrix res(n);
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++) {
                if (!mat[i][k]) continue;
                for (int j = 0; j < n; j++)
                    res.mat[i][j] = (res.mat[i][j] + mat[i][k] * o.mat[k][j]) % MOD;
            }
        return res;
    }

    Matrix pow(ll e) const {
        Matrix res(n, true), base = *this;
        while (e > 0) {
            if (e & 1) res = res * base;
            base = base * base;
            e >>= 1;
        }
        return res;
    }
};

36 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Matrix Exponentiation

Compute $M^k$ for an $n \times n$ matrix using binary exponentiation in $O(n^3 \log k)$ .

How It Works

Same idea as scalar binary exponentiation but with matrix multiplication:

Start with identity matrix

I

Decompose

k

in binary, square

M

repeatedly, multiply into result when bit is 1

Recurrence to Matrix

For a linear recurrence $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$ , define:

A = \begin{pmatrix} c_1 & c_2 & \cdots & c_k \\ 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & & \ddots & 0 \end{pmatrix}

Then $v_n = A^n \cdot v_0$ where $v_0$ is the initial state vector.

When to Use

Fibonacci / Lucas numbers for

n

up to

10^{18}

Any fixed-order linear recurrence where

n

is too large for DP

Counting paths of length

k

in a graph via adjacency matrix powers

State machine transitions raised to a large power

Complexity

Time —

O(n^3 \log k)

where

n

is matrix size and

k

is exponent

Space —

O(n^2)