Matrix Exponentiation for Linear Recurrences
You'll learn how to compute the nth term of a linear recurrence in logarithmic time by representing the recurrence as matrix multiplication and using fast exponentiation.
The Core Idea
A linear recurrence is a sequence where each term is a linear combination of previous terms. For example, Fibonacci: F(n) = F(n-1) + F(n-2).
Instead of computing all terms one-by-one (O(n) time), we can represent the recurrence as a matrix equation. By raising that matrix to the nth power using fast exponentiation (the same trick we use to compute x^n in O(log n) multiplications), we jump directly to the nth term.
How It Works
For a recurrence depending on the previous k terms, we build a k×k transition matrix that transforms state [term(i), term(i-1), ..., term(i-k+1)] into [term(i+1), term(i), ..., term(i-k+2)].
Raising this matrix to power (n - k) and multiplying by the base state gives us the nth term.
The trick: matrix exponentiation uses repeated squaring (if computing M^8, we compute M^2, then (M^2)^2, then ((M^2)^2)^2) — taking only O(log n) matrix multiplications instead of n.
Each matrix multiplication takes O(k³) time, so total complexity: O(k³ log n).
Why This Matters
This technique transforms problems that seem inherently sequential (compute term 1, then 2, then 3...) into ones solvable via exponentiation. It's powerful when n is enormous (like 10^9) but the recurrence order k is small.
Key Takeaway: Matrix exponentiation lets you compute the nth term of a k-order linear recurrence in O(k³ log n) time by encoding the recurrence as matrix multiplication and using fast exponentiation to "skip ahead" exponentially.