Matrix Exponentiation
Pillar: Chain — "A linear recurrence is a Chain: each state is a fixed linear combination of previous states. The transition matrix is the Chain's step. Binary exponentiation on matrices compresses \(n\) steps into \(O(k^3 \log n)\)."
The Problem
Compute \(F_n \bmod (10^9 + 7)\) where \(n\) can be \(10^{18}\).
The Fibonacci recurrence is \(F_n = F_{n-1} + F_{n-2}\). A loop from \(2\) to \(n\) takes \(O(n)\) time. When \(n = 10^{18}\), that loop runs for roughly 30 years. You already know from Ch4 L2 that binary exponentiation computes \(a^n\) in \(O(\log n)\) multiplications. The same trick works on matrices. And once you can raise a matrix to a power quickly, every linear recurrence becomes a \(O(\log n)\) problem.
The Key Idea: Recurrence as Matrix Multiplication
The Fibonacci recurrence advances one step at a time. Write the state as a column vector holding two consecutive terms:
Call that \(2 \times 2\) matrix \(M\). One multiplication by \(M\) advances the recurrence by one step. Two multiplications advance by two steps. In general:
So computing \(F_n\) reduces to computing \(M^n\) and reading off the right entry. And \(M^n\) can be computed with the exact binary exponentiation technique from Ch4 L2 — the only change is that "multiply" now means matrix multiplication instead of scalar multiplication.
Why does this work? Matrix multiplication is associative: \((A \cdot B) \cdot C = A \cdot (B \cdot C)\). That's the only property binary exponentiation needs. Commutativity is not required, and matrices are indeed not commutative in general. But associativity holds, and that's enough.
Formal Definition
Matrix exponentiation is the application of binary exponentiation to matrices. Given a \(k \times k\) matrix \(M\) and a non-negative integer \(n\), compute \(M^n\) by repeated squaring, where \(M^0 = I\) (the \(k \times k\) identity matrix).
The cost of one \(k \times k\) matrix multiplication is \(O(k^3)\). Binary exponentiation performs \(O(\log n)\) multiplications. Total: \(O(k^3 \log n)\).
Worked Example: \(F_{10}\) via Matrix Exponentiation
We want \(F_{10} = 55\). The transition matrix is \(M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\) and the initial state is \(\begin{bmatrix} F_1 \\ F_0 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\).
We need \(M^9\) (nine steps from \(F_1\) to \(F_{10}\)). Binary of \(9\): \(1001_2 = 8 + 1\).
Step 0 — bit 0 is 1:
Square base: \(M^2 = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}\).
Step 1 — bit 1 is 0:
Skip multiplication. Square base: \(M^4 = (M^2)^2 = \begin{bmatrix} 5 & 3 \\ 3 & 2 \end{bmatrix}\).
Step 2 — bit 2 is 0:
Skip multiplication. Square base: \(M^8 = (M^4)^2 = \begin{bmatrix} 34 & 21 \\ 21 & 13 \end{bmatrix}\).
Step 3 — bit 3 is 1:
Now \(M^9 = \begin{bmatrix} 55 & 34 \\ 34 & 21 \end{bmatrix}\). Multiply by the initial state:
The top entry is \(F_{10} = 55\). The bottom is \(F_9 = 34\). Both correct.
Four matrix multiplications total (two squarings that contributed to result, two squarings that were skipped for result but still needed for base). Compare to 9 scalar additions in the naive loop — here the savings are modest, but at \(n = 10^{18}\) the loop is impossible while matrix exponentiation finishes in about 60 matrix multiplications.
Generalization: Order-\(k\) Recurrences
Fibonacci is order-2: each term depends on the previous 2 terms. The transition matrix is \(2 \times 2\).
For a general order-\(k\) recurrence:
the state vector holds \(k\) consecutive terms and the transition matrix is \(k \times k\):
The first row encodes the recurrence coefficients. Each subsequent row shifts the state down by one position. This is called a companion matrix.
Example: Throwing dice. Count the number of ways to reach sum \(n\) by rolling a standard die (faces 1 through 6). The recurrence is:
This is an order-6 recurrence with all coefficients equal to 1. The transition matrix is \(6 \times 6\) with the first row all ones and a shifted identity below it. Matrix exponentiation solves it in \(O(6^3 \log n) = O(216 \log n)\).
Path Counting on Graphs
There is a second, seemingly unrelated application. Let \(A\) be the adjacency matrix of a directed graph with \(n\) vertices, where \(A[i][j] = 1\) if there is an edge from \(i\) to \(j\).
The entry \(A^k[i][j]\) counts the number of walks of length exactly \(k\) from vertex \(i\) to vertex \(j\).
The proof is a clean induction. For \(k = 1\), \(A^1[i][j] = A[i][j]\) counts walks of length 1, which are just edges. For the inductive step, a walk of length \(k\) from \(i\) to \(j\) must pass through some intermediate vertex \(m\) at step \(k-1\). The number of such walks is \(A^{k-1}[i][m] \cdot A[m][j]\), summed over all \(m\). That sum is exactly the definition of matrix multiplication: \((A^{k-1} \cdot A)[i][j] = A^k[i][j]\).
So computing \(A^k\) via matrix exponentiation gives you the number of paths of length exactly \(k\) between every pair of vertices, in \(O(n^3 \log k)\) time.
The Code
Matrix Multiply
const long long MOD = 1e9 + 7;
using Matrix = vector<vector<long long>>;
Matrix multiply(const Matrix& left, const Matrix& right) {
int dimension = left.size();
Matrix product(dimension, vector<long long>(dimension, 0));
for (int row = 0; row < dimension; row++)
for (int col = 0; col < dimension; col++)
for (int mid = 0; mid < dimension; mid++)
product[row][col] = (product[row][col] + left[row][mid] * right[mid][col]) % MOD;
return product;
}
Matrix Power
This is the modpow function from Ch4 L2, with scalar multiply replaced by multiply() and the identity element changed from \(1\) to the identity matrix \(I\).
Matrix matpow(Matrix base, long long exponent) {
int dimension = base.size();
Matrix result(dimension, vector<long long>(dimension, 0));
for (int diag = 0; diag < dimension; diag++)
result[diag][diag] = 1;
while (exponent > 0) {
if (exponent & 1)
result = multiply(result, base);
base = multiply(base, base);
exponent >>= 1;
}
return result;
}
Fibonacci Solver
long long fibonacci(long long termIndex) {
if (termIndex <= 1) return termIndex;
Matrix transition = {{1, 1}, {1, 0}};
Matrix raised = matpow(transition, termIndex - 1);
return raised[0][0];
}
Why termIndex - 1? The initial state already holds \(F_1\) and \(F_0\). One multiplication by \(M\) produces \(F_2\). So \(M^{n-1}\) applied to \([F_1, F_0]^T\) produces \([F_n, F_{n-1}]^T\). The answer sits at raised[0][0].
Full Solution (CSES Fibonacci Numbers)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
using Matrix = vector<vector<long long>>;
Matrix multiply(const Matrix& left, const Matrix& right) {
int dimension = left.size();
Matrix product(dimension, vector<long long>(dimension, 0));
for (int row = 0; row < dimension; row++)
for (int col = 0; col < dimension; col++)
for (int mid = 0; mid < dimension; mid++)
product[row][col] = (product[row][col] + left[row][mid] * right[mid][col]) % MOD;
return product;
}
Matrix matpow(Matrix base, long long exponent) {
int dimension = base.size();
Matrix result(dimension, vector<long long>(dimension, 0));
for (int diag = 0; diag < dimension; diag++)
result[diag][diag] = 1;
while (exponent > 0) {
if (exponent & 1)
result = multiply(result, base);
base = multiply(base, base);
exponent >>= 1;
}
return result;
}
long long fibonacci(long long termIndex) {
if (termIndex <= 1) return termIndex;
Matrix transition = {{1, 1}, {1, 0}};
Matrix raised = matpow(transition, termIndex - 1);
return raised[0][0];
}
int main() {
long long termIndex;
cin >> termIndex;
cout << fibonacci(termIndex) << "\n";
return 0;
}
Complexity: \(O(k^3 \log n)\) time, \(O(k^2)\) space, where \(k\) is the matrix dimension and \(n\) is the exponent. For Fibonacci, \(k = 2\), so each multiplication is \(O(8)\) and the total is \(O(8 \log n) = O(\log n)\).
Common Mistakes
-
Off-by-one in the exponent. If your state vector starts at \([F_1, F_0]\), you need \(M^{n-1}\) to reach \(F_n\). If it starts at \([F_0]\) with a different encoding, you might need \(M^n\). Getting this wrong shifts every answer by one position. Trace a small case (\(n = 2\) or \(n = 3\)) before submitting.
-
Forgetting to mod inside matrix multiply. Each entry in the product matrix is a sum of \(k\) terms, each up to \((10^9)^2 \approx 10^{18}\). That's \(k \times 10^{18}\), which overflows
long longwhen \(k > 9\). Take mod after each addition:product[row][col] = (product[row][col] + left[row][mid] * right[mid][col]) % MOD. For larger \(k\), consider taking mod inside the inner loop or using__int128for the accumulation. -
Building the wrong transition matrix. For an order-\(k\) recurrence \(a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}\), the coefficients go in the first row, and the identity shift goes below. A common mistake is transposing the matrix or putting coefficients in a column instead of a row. Verify by multiplying \(M \times [a_{k-1}, a_{k-2}, \ldots, a_0]^T\) by hand and checking that you get \([a_k, a_{k-1}, \ldots, a_1]^T\).
Quick Recap
- A linear recurrence can be written as a matrix-vector product. The transition matrix encodes the recurrence coefficients.
- Matrix exponentiation uses the same binary exponentiation algorithm from Ch4 L2 — replace scalar multiply with matrix multiply, and the identity \(1\) with the identity matrix \(I\).
- Total cost for an order-\(k\) recurrence: \(O(k^3 \log n)\).
- The entry \(A^k[i][j]\) in the \(k\)-th power of an adjacency matrix counts walks of length exactly \(k\) from \(i\) to \(j\). Same algorithm, different interpretation.
- Always trace a small case to nail the exponent offset (\(M^n\) vs \(M^{n-1}\)).
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| CSES — Fibonacci Numbers | cses.fi/problemset/task/1722 | Easy | Direct \(2 \times 2\) matrix exponentiation |
| CSES — Throwing Dice | cses.fi/problemset/task/1096 | Medium | Order-6 recurrence, \(6 \times 6\) transition matrix |
| CSES — Graph Paths I | cses.fi/problemset/task/1723 | Medium | Adjacency matrix raised to \(k\)-th power for path counting |
Next lesson: The Tropical Semiring — replacing \((\times, +)\) with \((\min, +)\) to turn matrix exponentiation into shortest-path computation.