Scalar multiplication complexity of 4×4 matrices over F₂

How many scalar multiplications are needed for a bilinear algorithm multiplying two 4×4 matrices over the two-element field F₂? Two recursive levels of Strassen’s algorithm use 49. The arithmetic takes place in F₂, so an algorithm over ℂ is a separate result.

Why it matters and what counts as progress

Why it matters: Small-matrix algorithms provide concrete tests of the multiplication complexity achievable in a specified field.

What counts as progress: Construct and verify a bilinear algorithm using fewer multiplications, or prove a stronger lower bound in this field and dimension. A fixed-size operation count does not by itself give a better general asymptotic exponent or wall-clock speed on every processor.

How the problem developed

1969 · Algorithm [1]
Volker Strassen Introduced the seven-product bilinear algorithm for 2×2 matrix multiplication, which gives a 49-multiplication recursive baseline for 4×4 matrices.
5 Oct 2022 · Algorithm [2]
Alhussein Fawzi and collaborators Reported an algorithm using 47 scalar multiplications for 4×4 matrices over the two-element field F₂.

AI contribution

Discovering faster matrix multiplication algorithms with reinforcement learning

Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, David Silver, Demis Hassabis, Pushmeet Kohli

The authors report an algorithm multiplying 4×4 matrices over the two-element field using 47 scalar multiplications, compared with 49 from two levels of Strassen’s algorithm.

AI involvementAI-centered

ImportanceNotable

Technical verificationFormal (exact computation)

Human understandingFull