Matrix Exponentiation
Matrix Exponentiation is a technique to solve linear recurrence relations in O(log N) time.
Current Action
Ready
Exponent (p)
()
×
Binary Exponent (Reversed):
Ready
Find F(n):
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
The Problem: Finding the N-th Fibonacci number takes O(N) using standard DP. Valid for N=10^7, but too slow for N=10^18.
The Solution: Transition logic (like `f(n) = f(n-1) + f(n-2)`) is linear. Linear transformations can be represented by matrices.
If we can represent the transition from step i to i+1 as State_{i+1} = M * State_i, then State_n = M^n * State_0.
Calculating M^n takes O(k^3 log N) where k is the matrix size.
Concept
Transition Matrix: For Fibonacci [F(n), F(n-1)]^T = M * [F(n-1), F(n-2)]^T.
- F(n) = 1*F(n-1) + 1*F(n-2)
- F(n-1) = 1*F(n-1) + 0*F(n-2)
Matrix M: [[1, 1], [1, 0]].
Binary Exponentiation: We can compute M^N using the same 'square and multiply' logic used for integers.
How it Works
- Identify Recurrence: Determine the linear relation (e.g., `f(n) = 3f(n-1) - f(n-2)`).
- Define State Vector: E.g., `[f(n), f(n-1)]`.
- Construct Transformation Matrix: Find `M` such that `V_n = M * V_{n-1}`.
- Compute M^(N-1): Use fast exponentiation.
- Result: Multiply `M^(N-1)` by the base state vector `V_1`.
Step-by-Step Breakdown
1. Function multiply(A, B): Standard matrix multiplication `C[i][j] = sum(A[i][k] * B[k][j])`.
2. Function power(A, p): Initialize `res` as Identity Matrix. While `p > 0`: if `p` is odd `res = multiply(res, A)`. `A = multiply(A, A)`. `p /= 2`.
3. Solve: Construct initial matrix `T`. Compute `T^n`. Answer is usually in the top-left cell or product of vector.
When to Use
- Finding N-th term of a linear recurrence for very large N (up to 10^18).
- Counting paths of length N in a graph (Adjacency Matrix ^ N).
- Dynamic Programming where state space is small but N is huge.
When NOT to Use
- Non-linear recurrences (e.g., `f(n) = f(n-1) * f(n-2)`).
- When N is small (O(N) DP is simpler).
- When matrix size `k` is large (Matrix Mult is O(k^3), so k > 100 becomes slow).
How to Identify
"Find f(n) mod 10^9+7 where N <= 10^18", "Number of paths of length K", Linear Recurrences.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.