Algorithms·matmul:4x4-mod2
Multiplications needed for 4x4 matrix multiplication over F_2
Machine-checked by qed.bot.
A rank-R decomposition of the matrix multiplication tensor is an algorithm using R multiplications. Applying Strassen's algorithm recursively gives 49 for the 4x4 case over the field with two elements.
Record history
2 steps·multiplications, lower is betterApplying Strassen's 1969 algorithm to 2×2 blocks multiplies 4×4 matrices with 49 multiplications. AlphaTensor found a 47-multiplication algorithm valid over the field with two elements in 2022. AlphaEvolve's 48-multiplication algorithm of 2025 works over the complex numbers, a different question, and is not a step here.
The first improvement on the recursive Strassen count for this case since 1969.
Two levels of Strassen's 1969 algorithm.
AI activity
How grades workA decomposition of rank 47, improving on 49.
Reasoning and sources
Autonomy
Reinforcement learning against a game whose rules, reward and representation were designed by people; the decomposition itself was found by the system.
Checks
1-
verified·qed.bot
4x4x4 in 47 multiplications, exact identity mod 2
Follow and discuss
All discussionFollow this problem
An email when it has a new claim, check, bounty or discussion. You confirm once and can stop with one click.
Discussion and bounties for this problem load here.
Seen recently
What the monitors picked up in the last thirty days, not yet graded.
Something wrong or missing here? Request a correction or add a claim, with its sources.
Claims and corrections from readers
All of themSources
Cite this record
qed.bot, “Multiplications needed for 4x4 matrix multiplication over F_2”, https://qed.bot/t/matmul-4x4-mod2, as of 30 Sep 2026.