Research · Papers · Direct sums, wedges and the p14 frontier · MF-149
A lower bound on multiplicative complexity of 2x2 matrix multiplication over F2
MC(M_2 over F2) >= 6, narrowing MC(M_2 over F2) to [6,7]
Published 2026-09-04
For everyone
Plain summary
Multiplying two 2x2 matrices is a fundamental operation in computer science. When working with binary arithmetic—where values are 0 and 1, addition is XOR, and multiplication is AND—multiplicative complexity measures how many AND operations a circuit needs, treating additions as free.
Decades ago, Shmuel Winograd proved that bilinear algorithms need at least 7 multiplications for 2x2 matrices, matching Volker Strassen's algorithm. Winograd's proof assumed bilinear steps, leaving open whether unrestricted circuits could multiply 2x2 matrices with fewer multiplications.
This result proves that any unrestricted binary circuit computing 2x2 matrix multiplication requires at least 6 multiplications. Combined with Strassen's 7-multiplication upper bound, the exact unrestricted multiplicative complexity over the two-element field is pinned to either 6 or 7.
Result
For 2x2 matrix multiplication over F2 (denoted M_2 over F2), the unrestricted multiplicative complexity satisfies:
MC(M_2 over F2) >= 6
Combined with Strassen's algorithm:
MC(M_2 over F2) ∈ [6, 7]
Setting and definitions
Let F2 denote GF(2). Let M_2(F_2) denote the space of 2x2 matrices over F2, with dim V = 4.
The multiplicative complexity MC(f) of a multi-output Boolean function or bilinear map f over F2 is the minimum number of AND operations required to compute f in a straight-line program over (XOR, AND, 1), with linear operations free over F2.
The target is matrix multiplication C = AB for A, B ∈ M_2(F_2).
Method
The lower bound is proved by functional classification of linear projections and certified by automated verification scripts.
The nine cheap rank-1 functional classes limit standard lower bound arguments (THEOREM A) to 5. To bypass this limit, evaluation is restricted to the 2-plane:
{Tr(Λ^T AB) : Λ in GF(4)*}
where GF(4)* denotes the non-zero elements of the field copy GF(4) embedded in M_2(F_2), in which all non-zero elements are invertible.
Evaluating across this 2-plane yields three distinct functional classes that each require multiplicative complexity mc = 4. Jointly, these requirements rule out any implementation with 5 or fewer multiplications, establishing m_2 >= 6.
Proof evidence: tier P (written proof) and FC (fully-certified tier evidence). Verification artifacts:
geometry/bilinear_targets.pyunder target namematmul2_targetsweep_results.jsonunder keymatmul2
Discussion
Winograd's rank-7 optimality proof applies strictly to bilinear algorithms. In unrestricted circuits, intermediate products may evaluate arbitrary non-linear combinations of inputs. Prior to this result, no unrestricted lower bound exceeded 5.
This result establishes that non-bilinear operations cannot drop the multiplication count for 2x2 matrix multiplication over F2 below 6. Whether an unrestricted 6-multiplication circuit exists or the unrestricted complexity matches the bilinear optimum of 7 remains open, bounding the value to [6, 7].
For everyone — the takeaway
What this means
Most matrix multiplication algorithms use bilinear formulas, forming products only between linear combinations of the inputs. Whether non-bilinear circuits could compute matrix products with fewer multiplications has been an open question.
This result shows that unrestricted binary circuits still need at least 6 multiplications for 2x2 matrices. Over the two-element field, the true complexity is narrowed to either 6 or 7.
Attribution and prior art
Prior art: Winograd’s rank-7 optimality result applies specifically to bilinear algorithms; no unrestricted bound has been established.
Register references
- Entry ID: MF-149
- Verification receipt:
geometry/bilinear_targets.py(matmul2_target) - Verification receipt:
sweep_results.json(keymatmul2) - Prior art: Winograd (bilinear rank-7 optimality)
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 2 of 2 receipt files bundled (2 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.