CODING CHALLENGE · N°45

Matrix Exponentiation

Medium MathDivide and ConquerLinear Algebra

Raise a matrix to the n-th power in O(log n) multiplications instead of n — the trick that computes the billionth Fibonacci number or counts length-n walks in a graph almost instantly. It’s fast exponentiation, lifted from numbers to matrices. Solve it in Python or TypeScript, with hidden tests.

The problem

Implement matrix_power(mat, power): given a square integer matrix mat (a list of rows) and a non-negative integer power, return mat raised to that power (matrix multiplication, not element-wise). power = 0 returns the identity matrix. Use binary (fast) exponentiation to do it in O(log power) matrix multiplies.

EXAMPLE 1

Input mat = [[1,1],[1,0]], power = 10

Output [[89, 55], [55, 34]]

the Fibonacci matrix; entries are F(11), F(10), F(10), F(9)

EXAMPLE 2

Input mat = [[2,0],[0,2]], power = 3

Output [[8, 0], [0, 8]]

diagonal matrices power element-wise on the diagonal

CONSTRAINTS

The matrix is square (n×n) with integer entries; use exact integer arithmetic.
power = 0 → the identity matrix (1 on the diagonal, 0 elsewhere).
Use fast exponentiation: square the base and halve the exponent, multiplying into the result when the current bit is set — O(log power) multiplies.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement matrix_power(mat, power): write a helper that multiplies two n×n matrices, start the result at the identity, then loop — if the low bit of power is set, multiply the result by the current base; then square the base and shift power right.

HINTS — 4 IDEAS

First write matmul(A, B): entry [i][j] is the dot product of row i of A with column j of B.
Initialise the result as the identity matrix so that "multiply into result" starts correctly.
Fast exponentiation: while power > 0, if power is odd multiply result *= base; then base *= base and power //= 2.
This turns n multiplications into about log₂(n) — the same idea as fast exponentiation of plain numbers.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Compute M^n by exponentiation by squaring: M^n = (M^(n/2))² for even n, and M · M^(n−1) for odd. Iterate over the bits of n, squaring the matrix each step and multiplying it into an accumulating result whenever the current bit is set. Start the result at the identity matrix.

Complexity

Time O(k³ log n) for a k×k matrix — k³ per multiply, and only log n multiplies instead of n.

Common mistakes

Naive repeated multiplication O(n) instead of the O(log n) squaring.
Wrong base case — the accumulator must start as the identity matrix.
Integer overflow on large entries — apply a modulus if the problem calls for it.

Where this shows up

Matrix exponentiation evaluates linear recurrences in O(log n) — the classic [[1,1],[1,0]]^n computes Fibonacci fast. It also counts length-n paths in a graph (powers of the adjacency matrix) and advances Markov chains, making it a go-to for “huge n” recurrence and counting problems.

Finished this one? 0 / 75 Challenges done

Explore the topic

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

Algorithms & DSA