Matrix exponentiation computes a high power of a square matrix in O(log n) time instead of O(n), by reusing the same fast-power (binary exponentiation) trick you would use on plain numbers — only the multiplication is now a matrix multiply. It turns any linear recurrence, like Fibonacci, into a logarithmic-time formula.
Core idea. Just as x^13 can be found by squaring (x, x^2, x^4, x^8, ...) and multiplying in only
the powers whose bit is set, M^n is found by repeatedly squaring the matrix and folding it into a result
whenever a bit of n is 1. For Fibonacci, M = [[1, 1], [1, 0]] and M^n has F(n) sitting at index
[0][1].
The classic application: Fibonacci. Because [[1, 1], [1, 0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]], computing M^7 gives us F(7) = 13 directly — and the power needs only about log2(7) matrix multiplies, not 7 additions.
Intuition
Fast power on a number works because n written in binary tells you exactly which squared powers to combine: 13 = 1101, so x^13 = x^8 · x^4 · x^1. You walk the bits of n from least significant to most, keeping a base that doubles its exponent each step (x, x^2, x^4, x^8), and you multiply the base into your running result only when the current bit is 1.
Nothing about that argument used the fact that the values were numbers — it only used that they could be multiplied and that multiplication is associative. Matrices satisfy both, so the identical loop computes M^n. The result starts as the identity matrix I (the matrix version of "1"), and each squaring is one matrix multiply.
Walk through it
Step through the animation on the right. The left grid is the result R (starts as the identity), the right grid is the base B (starts as M), and the labels track e in binary and the running R. We want M^7, and e = 7 = 111.
Because all three bits of 7 are 1, every iteration multiplies. First, the low bit is 1, so R = R · B = M; then B squares to M^2 and e shifts to 11. Next bit is 1, so R = M · M^2 = M^3; B squares to M^4 and e becomes 1. Last bit is 1, so R = M^3 · M^4 = M^7; B squares to M^8 and e drops to 0, ending the loop. The final R = [[21, 13], [13, 8]], and F(7) = R[0][1] = 13.
The code, line by line
def mat_mult(A, B):
return [[A[0][0]*B[0][0] + A[0][1]*B[1][0],
A[0][0]*B[0][1] + A[0][1]*B[1][1]],
[A[1][0]*B[0][0] + A[1][1]*B[1][0],
A[1][0]*B[0][1] + A[1][1]*B[1][1]]]
def mat_pow(M, n):
R = [[1, 0], [0, 1]] # identity
while n > 0:
if n & 1:
R = mat_mult(R, M)
M = mat_mult(M, M)
n >>= 1
return R # F(n) = R[0][1] for the Fib basemat_multis the ordinary2x2matrix product, written out entry by entry; it is the only "expensive" operation and runs in constant time for a fixed-size matrix.Rstarts as the identity[[1, 0], [0, 1]]— the matrix that leaves any product unchanged, exactly like starting a numeric product at1.if n & 1tests the current low bit of the exponent. When it is 1, line 11 folds the current base into the result:R = R · M.- Line 12 squares the base so it now represents the next higher power of two, and line 13 shifts
nright to expose the next bit. - After the loop,
R = M^n. For the Fibonacci base matrix,F(n)is the top-right entryR[0][1].
Complexity
| Case | Time | Notes |
|---|---|---|
| Time | O(log n) (fast) | about log2(n) matrix multiplies; each is O(k^3) for a k x k matrix |
| Space | O(k^2) (moderate) | two k x k matrices held at once (k = 2 here) |
O(k^2) (moderate)The exponent loses one bit per iteration (n >>= 1), so it runs about log2(n) times. Each iteration does at most two matrix multiplies, and a k x k multiply is O(k^3), giving O(k^3 · log n) overall. For a fixed 2x2 matrix that is simply O(log n) — exponentially faster than the O(n) iterative Fibonacci.
When to use / pitfalls
Reach for matrix exponentiation whenever you need the n-th term of a linear recurrence for very large n (think n up to 1e18), where an O(n) loop would time out. Fibonacci, tribonacci, counting paths of a fixed length in a graph (adjacency-matrix powers), and many "number of ways after n steps" problems all reduce to raising a small transition matrix to the n-th power.
Two pitfalls. First, matrix multiplication is not commutative — keep the order fixed (here R = R · M,
not M · R) so the powers compose correctly. Second, the entries grow exponentially, so for large n you
almost always work modulo some number (e.g. 1e9 + 7); apply the mod inside mat_mult to every entry to
avoid overflow.
Practice
We are computing M^7 with e = 111. On the first loop iteration, after testing the low bit and updating, what are the values of R and e?
1. Why does the result matrix R start as the identity matrix?
2. How many matrix multiplies does computing M^n take, asymptotically?
3. For the Fibonacci base matrix M = [[1, 1], [1, 0]], where does F(n) appear in M^n?
4. Why must you usually apply a modulus inside mat_mult for large n?