Matrix exponentiation

For a square matrix A of size n×n and a nonnegative integer k, the k-th power A^k is defined recursively: A⁰ = I (the identity matrix) and A^k = A·A^k−1. This operation satisfies the usual exponent laws: A^a+b = A^aA^b and (A^a)^b = A^ab, provided the matrices commute (which they do for powers of the same matrix).¹

For negative integers, A^−k is defined as the inverse of A^k, requiring A to be invertible. For real or complex exponents, the definition uses the matrix exponential and logarithm: A^t = exp(t log A), where log A is a matrix logarithm (not unique if A has nonpositive eigenvalues).²

The most common algorithm for integer powers is exponentiation by squaring (binary exponentiation), which computes A^k in O(log k) matrix multiplications, each costing O(n³) for dense matrices. This method is widely used in competitive programming and numerical linear algebra.³

For diagonalizable matrices, A^k = P D^k P⁻¹, where D is diagonal, reducing the problem to scalar exponentiation. For non-diagonalizable matrices, the Jordan normal form provides a similar decomposition, but the powers of Jordan blocks involve binomial coefficients.¹ The matrix exponential itself is often computed via Padé approximation or scaling-and-squaring, which is numerically stable for many applications.⁴

Matrix exponentiation is central to solving linear differential equations: the solution to dx/dt = Ax is x(t) = e^tAx(0). This appears in control theory, quantum mechanics (time evolution operators), and population dynamics.²

In discrete mathematics, the k-th power of an adjacency matrix of a graph gives the number of walks of length k between vertices, a fact used in network analysis and PageRank-like algorithms.⁵ In probability, the transition matrix of a Markov chain raised to the k-th power yields the k-step transition probabilities, enabling the study of long-run behavior.

Beyond the standard definitions, matrix powers appear in the computation of Fibonacci numbers in O(log n) time via the matrix [[1,1],[1,0]]ⁿ, a classic example of algorithmic exponentiation.³ The matrix logarithm, used for real powers, is not unique; for matrices with negative eigenvalues, multiple branches exist, leading to subtle issues in defining fractional powers.²

In numerical analysis, the condition number of matrix exponentiation can be large, and algorithms like the Schur–Parlett method handle non-diagonalizable cases by using a triangular form.⁴ Historically, the concept of matrix powers dates back to Cayley's 1858 memoir, where he used powers to study linear transformations.⁶

Matrix exponential

The infinite series e^A = Σ A^k/k!, generalizing the scalar exponential to matrices.

Diagonalizable matrix

A matrix that can be written as PDP⁻¹ with D diagonal.

Jordan normal form

A canonical form for non-diagonalizable matrices, with Jordan blocks on the diagonal.