How does a matrix compute Fibonacci?

The 2×2 matrix [[1,1],[1,0]] advances the Fibonacci state: multiplying [F(k+1), F(k)] by it gives [F(k+2), F(k+1)]. So that matrix raised to the n-th power encodes F(n) directly — its entries are consecutive Fibonacci numbers. Compute the power fast and you read F(n) off the result without iterating n times.

Why is it O(log n) instead of O(n)?

Binary exponentiation squares the base repeatedly, doubling the exponent it represents each step, and multiplies the running result in only when the corresponding bit of n is 1. An n-bit exponent needs about log2(n) squarings and at most log2(n) multiplications — logarithmic in n. Each matrix multiply is constant work for a fixed-size matrix.

When would you use matrix exponentiation?

Whenever you must evaluate a linear recurrence at a very large index, often modulo something: the n-th Fibonacci or Tribonacci number, counting paths of length n in a graph (adjacency-matrix powers), dynamic programming over huge step counts, and many competitive-programming problems where n can be 10^18 and an O(n) loop is far too slow.

Algorithms · Fast Exponentiation

Fibonacci, Fast-Forwarded.

Q: What is matrix exponentiation?

Matrix exponentiation raises a square matrix to a large integer power efficiently using binary exponentiation (repeated squaring), in O(log n) matrix multiplications instead of n. It's the standard way to evaluate a linear recurrence — like Fibonacci — at a huge index quickly, because the recurrence can be written as multiplying a state vector by a fixed transition matrix.

Want the 1,000,000th Fibonacci number? Adding one at a time is a million steps. But Fibonacci hides inside a tiny 2×2 matrix: raise [[1,1],[1,0]] to the n-th power and F(n) falls out. And you can raise anything to a huge power in ~log n steps by squaring — so a million-step recurrence collapses to about twenty matrix multiplies.

O(log n) time · binary exponentiation · linear recurrence

transition matrix

[[1,1],[1,0]] advances the Fibonacci state one step.

the power

That matrix to the n gives F(n) in its entries.

square, don’t multiply

Squaring doubles the exponent — the log-time trick.

binary bits

Multiply the result in only where n has a 1 bit.

matpow.js — square the base, multiply on set bits

n =

Ready

We raise the Fibonacci matrix B=[[1,1],[1,0]] to the power n. Read n in binary from the low bit. Press Step: if this bit is 1, fold B into the result; then square B and move to the next bit.

–

current bit

multiplies

–

F(n)

How it works

Two ideas snap together. First, Fibonacci is a linear recurrence, so one step of it is a matrix multiply: [F(k+1), F(k)] × [[1,1],[1,0]] = [F(k+2), F(k+1)]. Apply that matrix n times and you’ve advanced n steps — meaning [[1,1],[1,0]]ⁿ literally contains F(n). Second, you don’t apply it n times; you square your way there.

Write n in binary

Say n = 13 = 1101₂. Each bit, low to high, corresponds to B, B², B⁴, B⁸…

Bit is 1 → fold it in

Multiply the running result by the current power of B. That bit’s contribution is now included.

Square the base

Replace B with B×B — the next bit represents twice the exponent. Advance to that bit.

✓

Read F(n)

After ~log₂(n) rounds, the result is Bⁿ; its top-right entry is F(n). Twenty rounds reach a million.

Time

O(log n)

Naive loop

O(n)

Rounds for 10⁶

~20

Space

O(1)

The code

# F(n) via matrix power, O(log n) def mul(A, B): return [[A[0][0]*B[0][0]+A[0][1]*B[1][0], A[0][0]*B[0][1]+A[0][1]*B[1][1]], [A[1][0]*B[0][0]+A[1][1]*B[1][0], A[1][0]*B[0][1]+A[1][1]*B[1][1]]] def fib(n): result = [[1,0],[0,1]] # identity base = [[1,1],[1,0]] # Fibonacci matrix while n > 0: if n & 1: result = mul(result, base) # bit set → fold in base = mul(base, base) # square n >>= 1 # next bit return result[0][1] # F(n)

Swap the matrix and you get any linear recurrence — Tribonacci, or an adjacency matrix whose n-th power counts length-n paths in a graph. The fast-exponentiation skeleton is identical to modular exponentiation for numbers; only the multiply changes.

Quick check

1. Why is raising the matrix O(log n), not O(n)?

2. What does the matrix let you compute besides Fibonacci?

FAQ

What is matrix exponentiation?

Raising a square matrix to a large integer power in O(log n) matrix multiplications using binary exponentiation (repeated squaring) — the fast way to evaluate a linear recurrence at a huge index.

How does a 2×2 matrix give Fibonacci?

Multiplying the state [F(k+1), F(k)] by [[1,1],[1,0]] yields [F(k+2), F(k+1)]. So that matrix to the n-th power encodes F(n) — its entries are consecutive Fibonacci numbers.

Why not just loop n times?

For huge n (say 10¹⁸, common in competitive programming, often modulo a prime), an O(n) loop is far too slow. Matrix exponentiation is O(log n) — about 60 rounds for 10¹⁸.

How is it related to modular exponentiation?

Identical skeleton — square the base, multiply the result on set bits — but the "multiply" is matrix multiplication instead of scalar multiplication. Both compute xⁿ in O(log n).

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Fibonacci, Fast-Forwarded.

How it works

Write n in binary

Bit is 1 → fold it in

Square the base

Read F(n)

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Write n in binary

Bit is 1 → fold it in

Square the base

Read F(n)

The code

Quick check

FAQ

Keep going

Modular Exponentiation →

Coin Change (DP) →

Floyd-Warshall →

The DSA Roadmap →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.