Steps as a matrix
When a state vector updates each step by multiplying with a fixed transition matrix, taking many steps means multiplying by that matrix many times. Computing the matrix raised to the step count jumps the system forward all at once.
Fast powers of a matrix
The same binary squaring used for numbers works for matrices:
- Express the step count in binary.
- Square the matrix repeatedly, one squaring per bit.
- Multiply selected squared matrices together for the set bits.
Each matrix product follows the usual row by column rule, and everything can be reduced by a modulus if needed. The count of matrix multiplications grows with the number of bits in the step count.
Where it shines
Linear recurrences, counting walks of a fixed length in a graph, and population style models all advance by a constant matrix, so a far away step is reached without iterating one step at a time.
Key idea
Matrix exponentiation advances a linear system many steps at once by raising its transition matrix to the step count using binary squaring, so far away states are reached without stepping one at a time.