Matrix multiplication is associative. Repeated application of one linear transition becomes a matrix power computable by squaring.

A matrix is a state-moving machine. Squaring the machine builds a new machine that jumps twice as far, then four times, then eight.

What the function promises: Return Fibonacci F(n) for nonnegative n, using 2×2 matrix exponentiation over exact Python integers.

def multiply(a, b):
    return [[sum(a[i][k]*b[k][j] for k in range(len(b)))
             for j in range(len(b[0]))] for i in range(len(a))]

def matrix_power(matrix, exponent):
    size = len(matrix)
    answer = [[int(i == j) for j in range(size)] for i in range(size)]
    while exponent:
        if exponent & 1: answer = multiply(answer, matrix)
        matrix = multiply(matrix, matrix)
        exponent >>= 1
    return answer

def fibonacci(n):
    if n < 0: raise ValueError("Negative index")
    if n == 0: return 0
    return matrix_power([[1,1],[1,0]], n-1)[0][0]

assert [fibonacci(i) for i in range(8)] == [0,1,1,2,3,5,8,13]
assert fibonacci(50) == 12586269025

Work and storage: O(d³ log n) time and O(d²) space; here d=2. Integer arithmetic cost grows with result size.

When to recognize it: Repeated application of one linear transition becomes a matrix power computable by squaring.

Check before applying it: Nonlinear or position-dependent transitions cannot use one fixed matrix directly.

Compose one matrix for a full period, exponentiate periods, then apply the remaining transitions.