Introduction

In this article I’ll write about techniques in black box linear algebra that are useful in competitive programming—especially the approach due to Wiedemann.

Motivation

Counting problems form one large genre in competitive programming. In many cases we compute answers mod a prime like 1,000,000,007; here we’ll focus on the prime-modulus case.

Among the many ways to solve counting problems, one major family uses matrices—i.e. linear algebra. Two representative examples we’ll cover:

1. Speeding up DP via matrix exponentiation
2. Fast determinant computation

1. Speeding Up DP with Matrix Exponentiation

Matrix exponentiation is extremely common in counting problems. We encode the state‑transition as a matrix. If the initial state is a vector b and the transition matrix is A, then after K steps the state is

Using binary exponentiation, this takes

time for an $$$N\times N$$$ matrix.

Sometimes special structure lets us do even better. For example, if A is circulant, multiply two such matrices in $$$O(N^2)$$$ (or faster via FFT‑based polynomial multiplication), and exponentiation in $$$O(N^2\log K)$$$. Triangular Toeplitz matrices also admit similar speedups.

In this article we’ll vastly generalize these special‑case speedups to get faster “general” matrix exponentiation.

2. Computing Determinants Quickly

Determinant computations also appear frequently in contests. By Gaussian elimination one can compute $$$\det(A)$$$ of an $$$N\times N$$$ matrix in $$$\Theta(N^3)$$$. Special cases—e.g. a banded matrix with bandwidth $$$K$$$ — drop to $$$\Theta(N K^2)$$$.

We’ll show how to speed up determinant calculation for a much larger class of matrices.

Preliminaries

Linear Recurrences and Their Minimal Polynomial

Let $$$V$$$ be a vector space over a field $$$\mathbb F$$$. An infinite sequence $$${a_i}_{i=0}^\infty$$$ in $$$V$$$ is linearly recurrent if there is a polynomial

such that for every $$$i\ge0$$$,

We say $$$c$$$ annihilates the sequence. The set of all annihilating polynomials is an ideal in $$$\mathbb F[X]$$$, and since $$$\mathbb F[X]$$$ is a PID there is a unique monic generator (unless the ideal is zero—in which case we take the zero polynomial). That generator is the minimal polynomial of the sequence.

If $$$f$$$ is a linear map between two vector spaces, then the minimal polynomial of $$$f(a)$$$ divides that of $$$a$$$.

Matrix Minimal Polynomial vs. Characteristic Polynomial

For a square matrix $$$A$$$, consider the sequence of powers $$${A^i}_{i=0}^\infty$$$. Its minimal polynomial is called the minimal polynomial of $$$A$$$. The characteristic polynomial is

By Cayley–Hamilton, $$$A$$$ satisfies its own characteristic polynomial, so the minimal polynomial divides the characteristic polynomial, and its degree is at most $$$N$$$. Moreover, they share the same set of roots (eigenvalues).

Finding the Minimal Polynomial

Scalar Sequences

If the input sequence lives in the field $$$\mathbb F$$$, one can use the Extended Euclidean Algorithm or the Berlekamp–Massey algorithm to compute the minimal polynomial in $$$O(n^2)$$$ time. Berlekamp–Massey is especially simple to implement.

Vector Sequences

If the sequence $$${b_i}$$$ lives in $$$\mathbb F^m$$$, pick a random vector $$$u\in\mathbb F^m$$$ by selecting each coordinate from some finite subset $$$U\subset\mathbb F$$$. Compute the scalar sequence

With high probability the minimal polynomial of $$${a_i}$$$ equals that of $$${b_i}$$$. This takes $$$O(mn + n^2)$$$ time overall.

Matrix Case

To find the minimal polynomial of an $$$N\times N$$$ matrix $$$A$$$, pick a random vector $$$b$$$ and form the sequence $$${A^i b}_{i=0}^{2N-1}$$$. Reduce to the vector case above, giving high‑probability correctness in $$$O(N^2 + N\,T(N))$$$ time, where $$$T(N)$$$ is the cost of multiplying $$$A$$$ by a vector.

Applications of the Minimal Polynomial

Fast General Matrix Exponentiation

Given $$$A$$$, $$$b$$$, and $$$K$$$, we want $$$A^K b$$$. Because the sequence $$${A^i b}$$$ is linearly recurrent, let its minimal polynomial be $$$c(X)$$$. Then using polynomial‑recurrence techniques, one can express the $$$K$$$-th term as a linear combination of the first $$$N$$$ terms. Computing that takes

where $$$M(N)$$$ is the cost of multiplying degree-$$$N$$$ polynomials. For a dense matrix ($$$T(N)=\Theta(N^2)$$$), this is $$$O(N^3 + M(N)\log K)$$$, which beats plain exponentiation. For sparse or structured matrices it can be much faster.

Fast Determinant Computation

Recall $$$\det(A) = (-1)^N \chi_A(0)$$$. If the minimal polynomial has degree $$$N$$$, it equals the characteristic polynomial. Otherwise, we “preprocess” $$$A$$$ so that its minimal polynomial jumps to degree $$$N$$$. Concretely, if $$$A$$$ is nonsingular, choose a random diagonal matrix $$$D$$$ with $$$\det(D)\neq 0$$$. With high probability the minimal polynomial of $$$AD$$$ has degree $$$N$$$. Compute its minimal polynomial, then recover

This takes $$$O(N^2 + N\,T(N))$$$ time.

Conclusion

Even when a matrix isn’t given explicitly, as long as you have a “black box” that multiplies any vector by that matrix, these algorithms work. Such methods fall under black box linear algebra.

Beyond what we’ve covered, many more black‑box algorithms exist—for example, solving linear systems $$$Ax=b$$$ quickly via similar ideas.

In competitive programming, linear‑algebraic problems are abundant. Even if this approach isn’t the “intended” solution, it’s a powerful tool worth mastering.