Linear recurrences as matrix steps
A linear recurrence defines each term as a fixed combination of previous terms, like the Fibonacci sequence. Computing the nth term step by step takes work proportional to n. Matrix exponentiation computes it in far fewer steps by expressing one recurrence step as a matrix multiplication and then raising that matrix to a power.
Building the transition matrix
You pack the last few terms into a state vector. A carefully chosen transition matrix maps the current state vector to the next one in a single multiply. Applying the matrix once advances the recurrence by one term, so applying it n times advances by n terms.
- The state vector holds the window of recent terms.
- The transition matrix encodes the recurrence coefficients.
- Multiplying the matrix into the state advances one step.
Fast powers
Rather than multiply the matrix n times, you use fast exponentiation by squaring, the same square and multiply idea used for numbers. This reduces the number of matrix multiplications to roughly the number of bits in n. The result is a logarithmic number of matrix multiplies, each a small fixed cost when the state window is small.
Key idea
Encode one recurrence step as a transition matrix, then exponentiate it by squaring so you reach the nth term in a logarithmic number of matrix multiplications.