cf.completefrontend
MATH & GEOMETRY · ADVANCED

Matrix exponentiation

Jump a step-by-step rule forward n steps in log n time by raising its matrix to the n-th power with repeated squaring.

Time O(k³ log n)Space O(k²)2 practice problemsStep-through picture

The idea

Some sequences follow a fixed rule from one step to the next. Fibonacci numbers do: each one is the sum of the two before it, 0, 1, 1, 2, 3, 5, 8, .... Computing the 10^15-th one step by step would take forever.

The trick is to write the rule as a matrix, a grid of numbers. For Fibonacci, multiplying the pair [F(n+1), F(n)] by the matrix [[1, 1], [1, 0]] gives the next pair [F(n+2), F(n+1)]. Doing the step n times is the same as multiplying by that matrix raised to the power n.

And powers can be computed by squaring, like fast exponentiation with numbers: square the matrix to get the 2nd, 4th, 8th power, and multiply in the ones that match the binary digits of n. That takes about log n matrix multiplications.

An everyday example

Folding a long strip of paper

You want to know where a mark ends up after a strip of paper goes through the same folding machine a million times. Running the machine a million times is slow. Instead, you work out what two runs in a row do, and that's one new machine. Two of those make a four-run machine, and so on. With about 20 of these combined machines, you can build the million-run machine and send the strip through once.

How the example maps to the code
In the exampleIn the code
What one run of the machine doesbase = [[1n, 1n], [1n, 0n]]
Combining a machine with itselfbase = multiply(base, base)
Adding a combined machine to the final oneresult = multiply(result, base)
A machine that changes nothingthe identity [[1n, 0n], [0n, 1n]]

From the slow way to matrix exponentiation

  1. Start with the obvious way to get F(n): keep two numbers and step forward n times, each time replacing (a, b) with (b, a + b). That's O(n) steps. For n = 10^15 it would run for weeks, even though each step is tiny.
  2. Look at what one step does. The new pair is a fixed mix of the old pair: F(k + 2) = 1 × F(k + 1) + 1 × F(k) and F(k + 1) = 1 × F(k + 1) + 0 × F(k). A fixed mix like that is a matrix, here M = [[1, 1], [1, 0]]. One step is one multiplication by M, so n steps are a multiplication by M to the power n.
  3. Matrix multiplication is associative: (A × B) × C equals A × (B × C). That's the only thing fast exponentiation needs. So M^13 can be built as M^8 × M^4 × M^1, using squares M^2, M^4, M^8, just like 3^13 with numbers.
  4. Start result at the identity matrix, which means zero steps, and copy the fast-exponentiation loop with multiply in place of *. Keep entries as BigInt reduced by MOD, so products stay exact. After the loop, result is M^n, and its top-right entry is F(n). That loop is matrix exponentiation.

How it works

  1. Write the one-step rule as a square matrix. For Fibonacci it's [[1, 1], [1, 0]].
  2. Write multiply(A, B): entry C[i][j] is the sum of A[i][k] * B[k][j] over k, reduced modulo MOD.
  3. Start result as the identity matrix (ones on the diagonal), which is "zero steps".
  4. While e > 0: if e is odd, set result = multiply(result, base).
  5. Square base and halve e, exactly like fast exponentiation with numbers.
  6. Read the answer from result. For Fibonacci, result[0][1] is F(n).

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. const MOD = 1_000_000_007n;
  3. function multiply(A, B) {
  4. const size = A.length;
  5. const C = Array.from({ length: size }, () => new Array(size).fill(0n));
  6. for (let i = 0; i < size; i++) {
  7. for (let k = 0; k < size; k++) {
  8. for (let j = 0; j < size; j++) {
  9. C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  10. }
  11. }
  12. }
  13. return C;
  14. }
  16. function fibonacci(n) {
  17. let result = [[1n, 0n], [0n, 1n]];
  18. let base = [[1n, 1n], [1n, 0n]];
  19. let e = n;
  20. while (e > 0) {
  21. if (e % 2 === 1) result = multiply(result, base);
  22. base = multiply(base, base);
  23. e = Math.floor(e / 2);
  24. }
  25. return Number(result[0][1]);
  26. }

How fast it is

TimeO(k³ log n)
Extra memoryO(k²)

Each matrix multiplication is k³ steps for a k × k matrix, and there are about 2 log n of them. Only a few matrices are kept.

  • Best caseO(1)

    n is 0 or 1: the loop runs zero times or once.

  • Average caseO(k³ log n)

    About log₂ n steps, each with one or two multiplications of k × k matrices costing k³ small steps. For Fibonacci k = 2.

  • Worst caseO(k³ log n)

    n with every binary digit 1, so every step multiplies twice. n = 2^53 - 1 takes 106 matrix multiplications; n = 10^18 takes 84.

Common mistakes

  • Multiplying plain numbers near 10^9. The products lose precision; use BigInt.
  • Starting result as the base matrix instead of the identity. The answer is then one step too far.
  • Mixing up rows and columns in the rule matrix, so the sequence advances incorrectly. Check it on the first few values.
  • Using matrix exponentiation for small n. A plain loop is simpler and just as fast for n up to millions.

When to use it

Look for these clues in a problem:

  • Each value depends on a fixed number of previous values with fixed coefficients, like f(n) = f(n-1) + f(n-2).
  • n is huge, like 10^12 or 10^18, so even an O(n) loop is too slow.
  • The answer must be given modulo 1000000007.
  • Counting paths of exactly n steps in a small graph: that's a power of its adjacency matrix.

Check yourself

Answer each one in your head first, then open it.

Why does result start as the identity matrix?

The identity times any matrix is that matrix, so it means "zero steps so far". Starting at M instead makes every answer one step ahead.

How many matrix multiplications does fibonacci(13) do?

7: four squarings of base, one per binary digit of 1101, plus three multiplications into result for the three 1 digits.

Why does fibonacci(50) return 586268941 and not 12586269025?

Every entry is reduced modulo 1_000_000_007. 12586269025 minus 12 × 1000000007 is 586268941.

Matrix multiplication isn't commutative, so why can the loop multiply in any order?

result and base are both powers of the same matrix M, and powers of one matrix always commute: M^a × M^b = M^(a + b) = M^b × M^a.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

First, why M^n holds Fibonacci numbers. M^1 = [[F(2), F(1)], [F(1), F(0)]]. If M^k = [[F(k + 1), F(k)], [F(k), F(k - 1)]], multiplying by M adds the two columns into the first and moves the old first column to the second, giving [[F(k + 2), F(k + 1)], [F(k + 1), F(k)]]. So by induction the top-right entry of M^n is F(n).

The loop keeps the same promise as fast exponentiation: result × base^e equals M^n. It starts as I × M^n. When e is odd, one base moves into result. Squaring base and halving e leaves base^e unchanged. Matrix multiplication isn't commutative in general, but result and base are both powers of the same M, so their order never matters here.

The loop ends after one step per binary digit of n, and then e is 0, so result is M^n. Every entry is reduced with % MOD after each sum, and by the rules of modular arithmetic that gives the same remainders as computing the huge exact matrix and reducing at the end.

Going deeper

3 more ideas

Why the matrix power gives Fibonacci numbers

[[1, 1], [1, 0]] times the column [F(k+1), F(k)] gives [F(k+1) + F(k), F(k+1)] = [F(k+2), F(k+1)]: one step forward. So n steps are the matrix to the power n. In fact [[1, 1], [1, 0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]], so F(n) sits at row 0, column 1.

Precision with BigInt

Entries are kept below MOD, but a product of two entries can reach 10^18, past the 2^53 limit of exact numbers. The code stores entries as BigInt (the n suffix, like 1n) so every product and sum is exact, and only converts the final answer back to a number.

The cost

Multiplying two k × k matrices takes k³ steps, and the power needs about 2 log n multiplications. So the time is O(k³ log n). For Fibonacci k = 2, so F(10^18) takes about 60 tiny multiplications.

Work it by hand

Every step in a table, with why

Compute F(13). 13 is 1101 in binary, so one step skips and three multiply into result.

n = 13

Stepee % 2resultbase afterWhat happensWhy
113-[[1, 0], [0, 1]][[1, 1], [1, 0]]startresult is the identity, M^0. base is M, one step of the rule.
2131[[1, 1], [1, 0]][[2, 1], [1, 1]]multiply, then square13 is odd, so result = I × M = M^1. Then base becomes M^2, and e becomes 6.
360[[1, 1], [1, 0]][[5, 3], [3, 2]]only square6 is even, so M^2 isn't used. base becomes M^4, and e becomes 3.
431[[8, 5], [5, 3]][[34, 21], [21, 13]]multiply, then squareresult = M^1 × M^4 = M^5, and its top-right entry is F(5) = 5. base becomes M^8, and e becomes 1.
511[[377, 233], [233, 144]][[1597, 987], [987, 610]]multiply, then squareresult = M^5 × M^8 = M^13. base becomes M^16, which is never used, and e becomes 0.
60-[[377, 233], [233, 144]]-return result[0][1]The loop ends. M^13 = [[F(14), F(13)], [F(13), F(12)]], so the top-right entry is F(13).

It returns 233, which is F(13), after 4 loop steps and 7 matrix multiplications. Each 2-by-2 multiplication does 8 small multiplications, so for n = 13 the plain loop is actually cheaper; the matrix wins when n is huge.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Matrix exponentiationO(k³ log n)O(k²)n is huge (up to 10^18), the rule is a fixed linear mix, and the answer is wanted modulo a number.
Step-by-step loopO(n)O(1)n is up to a few million: simpler, and faster for small n.
Fast doublingO(log n)O(1)It's Fibonacci or a close relative, and you want the fewest multiplications.

Extra memory: O(k²): result, base, and one new matrix C per multiplication, each k × k. For Fibonacci that's a handful of numbers.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Matrix exponentiation and the other approaches, on a scale where each line up is 10 times more steps.
  • Matrix exponentiation O(k³ log n)
  • Step-by-step loop O(n)
  • Fast doubling O(log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Matrix exponentiation3,32210 billionmore than a quadrillion
Step-by-step loop101,0001 million
Fast doubling31020

Inputs that need care

5 tricky inputs
n = 0
The loop doesn't run, result stays the identity, and result[0][1] is 0, which is F(0). Starting from the identity is what makes this right.
n = 1
One step: result becomes M, and result[0][1] is 1, which is F(1).
An answer bigger than MOD: n = 50
F(50) is 12586269025, but the code returns 586268941, its remainder modulo 1_000_000_007. That's the point of MOD; remove it only if you want exact BigInt answers that grow.
Starting result at base instead of the identity
Everything is one step ahead: for n = 13 it returns 377, which is F(14). The identity means "zero steps so far".
A negative n
e > 0 is false at once and it returns 0. Reject negative n up front, since the rule only runs forward.

Variations and follow-ups

Twists interviewers add

Other linear rules

Any rule where the next value is a fixed mix of the last k values gets a k × k matrix. Tribonacci, where each value is the sum of the previous three, uses [[1, 1, 1], [1, 0, 0], [0, 1, 0]]. A constant term, like + 1 each step, is handled by adding one more row and column that always holds 1.

Counting walks in a graph

If A is a graph's adjacency matrix, entry [i][j] of A^n counts the walks of exactly n edges from i to j. So "how many ways to move between 3 screens in 10^12 clicks" is a matrix power.

Fast doubling

For Fibonacci only, F(2k) = F(k) × (2F(k + 1) - F(k)) and F(2k + 1) = F(k)² + F(k + 1)². It walks the binary digits like the matrix version but with fewer multiplications per step.

Dynamic programming with a fixed step

When a DP's next row depends on the previous row through the same rule every time, such as counting strings of length n with no two 1s in a row, that rule is a matrix. Raising it to the power n skips all the rows in between.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from a step-by-step rule combined with a huge n: "n up to 10^18, return the answer modulo 10^9 + 7", "count tilings of a 2 × n board", or "how many walks of length k".
  • Explain it in three parts: "The state is a vector, one step is a matrix, n steps are the matrix to the nth power, and I compute that power by squaring."
  • Test n = 0, 1, 2, and a few more against the plain loop before trusting a new matrix. A wrong row or column shows up within the first few values.
  • Expect "what's the cost in terms of the matrix size?" Answer: O(k³ log n), so it suits rules with a small k. For k = 100 each multiplication is already a million steps.

Where frontend code uses it

The same idea in real UI code
  • CSS transforms and the DOMMatrix API represent moves, rotations, and scales as matrices. Applying the same transform several times is multiplying by a matrix power.
  • Canvas and WebGL animations compose transforms by multiplying matrices, the same multiply loop as above.
  • Counting how many ways a user can move through a small navigation graph in exactly n clicks is a power of the graph's adjacency matrix.

Related algorithms