Pattern Guide
Linear Algebra & Matrix Exponentiation
"Speed up any linear recurrence from O(n) to O(log n) with matrix power."
Matrix exponentiation accelerates linear recurrences, counts graph paths, and solves state-transition problems in O(k³ log n). Learn the matrix construction trick, fast power, and Gaussian elimination.
18 min readlinear algebra problems →
Problems you can solve with this pattern
6 problems · click any to start solving
Matrix multiply + fast power — O(k³ log n)
const MOD = 1_000_000_007n;
function matMul(A, B) {
const n = A.length, m = B[0].length, k = B.length;
const C = Array.from({length: n}, () => new Array(m).fill(0n));
for (let i = 0; i < n; i++)
for (let j = 0; j < m; j++)
for (let p = 0; p < k; p++)
C[i][j] = (C[i][j] + A[i][p] * B[p][j]) % MOD;
return C;
}
function matPow(M, n) {
let result = M.map((r, i) => r.map((_, j) => i === j ? 1n : 0n)); // identity
while (n > 0n) {
if (n & 1n) result = matMul(result, M);
M = matMul(M, M);
n >>= 1n;
}
return result;
}
// Fibonacci in O(log n)
// [F(n+1)] [1 1]^n [1]
// [F(n) ] = [1 0] × [0]
function fibonacci(n) {
if (n <= 1) return n;
const M = [[1n, 1n], [1n, 0n]];
const R = matPow(M, BigInt(n - 1));
return R[0][0]; // F(n)
}Matrix exponentiation is a single powerful trick: if a system's next state is a linear function of its current state, you can represent that function as a matrix and compute the nth state in O(k³ log n) instead of O(kn). This unlocks Fibonacci in log n, counts paths of length n in a graph, and accelerates any DP with a fixed transition.
Core Idea — State × Transition Matrix
Pattern recognition:
- "Find f(n) where f(n) = a·f(n-1) + b·f(n-2) + ..." → matrix exponentiation
- "Count paths of length exactly k in a graph" → raise adjacency matrix to kth power
- "DP transition is the same at every step" → encode in a matrix
Key formula: If state_n = M × state_{n-1}, then state_n = M^n × state_0
- "Find f(n) where f(n) = a·f(n-1) + b·f(n-2) + ..." → matrix exponentiation
- "Count paths of length exactly k in a graph" → raise adjacency matrix to kth power
- "DP transition is the same at every step" → encode in a matrix
Key formula: If state_n = M × state_{n-1}, then state_n = M^n × state_0
Matrix multiply + fast power — O(k³ log n)
const MOD = 1_000_000_007n;
function matMul(A, B) {
const n = A.length, m = B[0].length, k = B.length;
const C = Array.from({length: n}, () => new Array(m).fill(0n));
for (let i = 0; i < n; i++)
for (let j = 0; j < m; j++)
for (let p = 0; p < k; p++)
C[i][j] = (C[i][j] + A[i][p] * B[p][j]) % MOD;
return C;
}
function matPow(M, n) {
let result = M.map((r, i) => r.map((_, j) => i === j ? 1n : 0n)); // identity
while (n > 0n) {
if (n & 1n) result = matMul(result, M);
M = matMul(M, M);
n >>= 1n;
}
return result;
}
// Fibonacci in O(log n)
// [F(n+1)] [1 1]^n [1]
// [F(n) ] = [1 0] × [0]
function fibonacci(n) {
if (n <= 1) return n;
const M = [[1n, 1n], [1n, 0n]];
const R = matPow(M, BigInt(n - 1));
return R[0][0]; // F(n)
}Building the Transition Matrix
Recipe for any linear recurrence f(n) = c1·f(n-1) + c2·f(n-2) + ... + ck·f(n-k):
State vector: [f(n), f(n-1), ..., f(n-k+1)]
Transition matrix (k×k):
``
For "count paths of length n in graph": raise adjacency matrix to nth power. Entry [i][j] = number of paths from i to j of length n.
State vector: [f(n), f(n-1), ..., f(n-k+1)]
Transition matrix (k×k):
``
[c1 c2 c3 ... ck ]
[1 0 0 ... 0 ]
[0 1 0 ... 0 ]
...
[0 0 ... 1 0 ]
For "count paths of length n in graph": raise adjacency matrix to nth power. Entry [i][j] = number of paths from i to j of length n.
Count paths of length exactly k in a graph
// adj[i][j] = 1 if edge exists
// After matPow(adj, k): result[i][j] = paths from i to j of length k
function countPaths(n, edges, k, src, dst) {
const adj = Array.from({length: n}, () => new Array(n).fill(0n));
for (const [u, v] of edges) {
adj[u][v] = 1n;
adj[v][u] = 1n; // undirected
}
const R = matPow(adj, BigInt(k));
return R[src][dst];
}Gaussian Elimination
Gaussian elimination solves Ax = b or finds matrix rank. Over GF(2) (bits), it solves systems of XOR equations — used for XOR basis / linear independence problems.
Time: O(n² × cols/64) with bitset optimization.
Time: O(n² × cols/64) with bitset optimization.
XOR basis — linear independence over GF(2)
// Insert numbers into XOR basis
// Basis can represent any XOR of inserted numbers
function buildXorBasis(nums) {
const basis = new Array(30).fill(0);
for (const x of nums) {
let cur = x;
for (let i = 29; i >= 0; i--) {
if (!(cur >> i & 1)) continue;
if (!basis[i]) { basis[i] = cur; break; }
cur ^= basis[i];
}
}
return basis;
}
// Max XOR of any subset
function maxXor(nums) {
const basis = buildXorBasis(nums);
let res = 0;
for (let i = 29; i >= 0; i--)
res = Math.max(res, res ^ basis[i]);
return res;
}
// Check if x can be formed by XOR of subset
function canForm(basis, x) {
for (let i = 29; i >= 0; i--) {
if (!(x >> i & 1)) continue;
if (!basis[i]) return false;
x ^= basis[i];
}
return x === 0;
}When to use matrix exponentiation:
- Recurrence of fixed order k: O(k³ log n) vs O(kn)
- n can be up to 10¹⁸ — impossible to iterate
- Counting paths of exact length in small graph
- Tiling, staircase, domino problems with periodic structure
Matrix size rule of thumb: k×k matrix where k = number of terms in recurrence. Keep k small (≤ 4) for competitive programming.
XOR basis:
- Maintain basis of O(32) independent XOR vectors
- Maximize XOR: greedily try adding each basis vector if it increases result
- Add number to basis: Gaussian elimination on bits (highest bit first)
- Recurrence of fixed order k: O(k³ log n) vs O(kn)
- n can be up to 10¹⁸ — impossible to iterate
- Counting paths of exact length in small graph
- Tiling, staircase, domino problems with periodic structure
Matrix size rule of thumb: k×k matrix where k = number of terms in recurrence. Keep k small (≤ 4) for competitive programming.
XOR basis:
- Maintain basis of O(32) independent XOR vectors
- Maximize XOR: greedily try adding each basis vector if it increases result
- Add number to basis: Gaussian elimination on bits (highest bit first)