Faangprep Logo
Log inStart free
Browse curriculum

Matrix Exponentiation

Matrix Exponentiation is a technique to solve linear recurrence relations in O(log N) time.

Multiplying by [[1, 1], [1, 0]] turns the pair (F(k), F(k−1)) into (F(k+1), F(k)), so raising that one matrix to the (n−1)th power puts F(n) in its top-left corner. And a power does not have to be reached one multiplication at a time: read the exponent in binary, keep doubling a matrix, and fold it in wherever a place holds a 1. Switch the method to walk the exponent instead, and watch the count.

READY

Exponent 29 = 0b11101

T^0

T^29

Built T^0

1
0
0
1

×

Power T^1

1
1
1
0

Multiplies

0

One by one

29

 

Building T^29, because T^29 holds F(30) in its top-left corner. In binary 29 is 11101 — 4 ones across 5 places — so this route costs 8 where multiplying by T one power at a time costs 29. BUILT starts at T^0, the identity.

Next

11101 has a 1 in the 1s place, and POWER is holding T^1 — the power that place stands for, already built. One multiplication folds it into BUILT: T^0 × T^1 = T^1.

n

Method

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

  1. Identify Recurrence: Determine the linear relation (e.g., f(n) = 3f(n-1) - f(n-2)).
  2. Define State Vector: E.g., [f(n), f(n-1)].
  3. Construct Transformation Matrix: Find M such that V[n] = M * V[n-1].
  4. Compute M^(N-1): Use fast exponentiation.
  5. 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.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Bitmask DP

Frequently Asked Questions

How do I build the transition matrix?

Write the recurrence as a vector of the last k terms and express the next vector as a matrix times the current one. Fibonacci uses the state [F(n), F(n-1)] with the matrix [[1, 1], [1, 0]], whose rows are the coefficients of the recurrence.

Where does the log N come from?

From binary exponentiation. Computing M^N by repeated squaring takes O(log N) matrix multiplications, each O(k³), giving O(k³ log N) overall instead of O(N) steps of ordinary DP.

What are the limits of the technique?

The recurrence must be linear with constant coefficients, so something like f(n) = f(n-1) * f(n-2) is out of reach. And since each multiplication is O(k³), it stops paying off once the number of states k runs into the hundreds.