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

Explore the topic

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

Algorithms & DSA