Course contentsShow
← Computer Science
Lesson 961 of 2,87222. Dynamic ProgrammingFree lesson

Matrix Exponentiation for Linear Recurrences

Compute nth term of linear recurrences in O(k³ log n) using matrix powers.

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.