4×4 complex matrix multiplication: AlphaEvolve finds a 48-multiplication algorithm

AlphaEvolve found an algorithm that multiplies 4×4 complex matrices with 48 scalar multiplications, one fewer than the 49 needed by applying Strassen's method recursively.

Problem
The fewest scalar multiplications needed to multiply two 4×44 \times 4 complex matrices
Credit
AlphaEvolve (Google DeepMind) · LLM-driven evolutionary code search
Checked
Can be checked directly
Timeline
Strassen 1969 → improved by AI 2025-05
Sources
DeepMind blog
PARTIALImproved upper bound

The problem

In 1969, Strassen found that two 2×22 \times 2 matrices can be multiplied with 7 scalar multiplications instead of the naive 8. Applying his method recursively to 4×44 \times 4 matrices takes 72=497^2 = 49 multiplications. For complex matrices, no one found a way to do it with fewer for more than half a century.

What AI did

AlphaEvolve has a large language model repeatedly propose and rewrite the code of a search algorithm, while an automatic evaluator checks correctness and counts multiplications. It found an algorithm that multiplies 4×44 \times 4 complex matrices with 48 scalar multiplications.

How it was checked

The algorithm is an explicit list of linear combinations and products. Substituting symbolic matrices checks term by term that the result equals the matrix product.

Limitations

This improves an upper bound: whether 48 is the minimum is still unknown. The result is specific to complex numbers, and a constant-factor saving of this size has limited effect on practical computation speed.

∎