Research · Papers · Direct sums, wedges and the p14 frontier · MF-180
Multiplicative complexity bounds for 2x2 matrix multiplication over GF(2)
6 ≤ MC(M_2(F_2)) ≤ 7 in sequential XAG over F_2, with qMC(W) ≥ 6 for an invariant 2-plane W ⊂ Λ^2(F_2^8)
Published 2026-09-04
For everyone
Plain summary
Matrix multiplication is a fundamental task across computer science. Over GF(2), where numbers are restricted to 0 and 1, circuit operations consist of addition (XOR gates) and multiplication (AND gates). Multiplicative complexity measures the minimum number of AND gates required when XOR gates are free. For multiplying two 2x2 matrices, classical results proved that 7 multiplications are necessary and sufficient if intermediate products must be bilinear combinations of the inputs. Unrestricted logic circuits can compute arbitrary non-bilinear combinations, leaving open whether fewer multiplications could suffice. This work establishes the first non-bilinear lower bound of 6 multiplications for general circuits over GF(2), narrowing the exact multiplicative complexity of 2x2 matrix multiplication to either 6 or 7. The lower bound is proved by analyzing invariant quadratic forms over the field extension F_4, alongside verification of Strassen's 7-gate upper bound across all 256 inputs.
Result
For 2x2 matrix multiplication M_2(F_2) over F_2 in the sequential exclusive-or/AND graph (XAG) model:
6 <= MC(M_2(F_2)) <= 7
Specifically:
- Upper Bound: MC(M_2(F_2)) <= qMC(M_2(F_2)) <= 7, achieved by Strassen's algorithm.
- Invariant Lower Bound: For the 2-plane W ⊂ Lambda^2(F_2^8) of quadratic forms defined by {Tr(Lambda^T AB) : Lambda ∈ F_4^*}, the quadratic multiplicative complexity satisfies qMC(W) >= 6, implying MC(M_2(F_2)) >= 6.
Setting and definitions
Let F_2 denote the Galois field of two elements. The matrix multiplication mapping M_2(F_2): F_2^4 x F_2^4 -> F_2^4 maps two 2x2 matrices A, B to product C = AB, parameterized by 8 Boolean input variables. The sequential XAG model evaluates Boolean functions using two-input XOR gates, two-input AND gates, and NOT gates, where XOR and NOT gates have zero cost and each AND gate incurs unit cost.
Multiplicative complexity MC(f) is the minimum number of AND gates in an XAG computing f. For a linear subspace of quadratic forms V ⊂ Lambda^2(F_2^n), quadratic multiplicative complexity qMC(V) is the minimum number of product gates needed to simultaneously evaluate a basis of V.
The 4 coordinate functions of AB span a 4-dimensional space of bilinear forms V ⊂ Lambda^2(F_2^8). Embedding the finite field F_4 as a subfield copy inside M_2(F_2) associates each non-zero element Lambda ∈ F_4^* with the trace form Tr(Lambda^T AB). These forms span a 2-dimensional invariant subspace W ⊂ V.
Method
- Bilinear and Upper Bound Verification:
Strassen's 1969 construction yields an explicit 7-AND XAG computing M_2(F_2). The circuit was checked against the specification across all 2^8 = 256 input configurations in F_2^8 using m2_qmc.py, confirming zero mismatches and establishing MC(M_2(F_2)) <= qMC(M_2(F_2)) <= 7.
- Subfield Invariant Lower Bound:
Restricting V to the F_4 copy inside M_2(F_2) isolates the invariant 2-plane W = {Tr(Lambda^T AB) : Lambda ∈ F_4^*}. The three non-zero forms in W each possess maximal polar rank 8, giving individual multiplicative complexity mc = 4. Lemma B (MF-145) gives: qMC(W) >= ceil((4 + 4 + 4) / 2) = ceil(12 / 2) = 6. Because W is a linear subspace of the outputs of M_2(F_2), any circuit computing M_2(F_2) must compute W, yielding MC(M_2(F_2)) >= qMC(W) >= 6. This refines the full-space packing lower bound of 5.
- Complete SAT Decision Encoding:
The decision problem MC(M_2(F_2)) <= 6 in unrestricted XAGs was encoded into propositional logic via multi_satlib.py. The resulting formula m2_k6.cnf contains 33,345 variables and 155,669 clauses, providing an exact automated search target.
Discussion
Winograd (1971) and Hopcroft and Kerr (1971) proved that the bilinear tensor rank of 2x2 matrix multiplication is 7 over any field. Bilinear rank restricts intermediate multiplications to linear combinations of A multiplied by linear combinations of B. General XAGs allow arbitrary non-bilinear intermediate products, so bilinear rank lower bounds do not transfer directly to MC.
The bound MC(M_2(F_2)) >= 6 is the first non-bilinear lower bound of 6 for unrestricted XAGs over F_2, constraining the exact complexity to {6, 7}. Deciding between 6 and 7 remains open; m2_k6.cnf provides the canonical target for exact automated search.
For everyone — the takeaway
What this means
Multiplying two 2x2 matrices is a central benchmark in algebraic complexity. Bilinear algorithms are proven to require 7 multiplications, but general digital circuits can compute non-bilinear intermediate combinations, leaving open whether 6 multiplications might work over GF(2). This work proves that fewer than 6 multiplications is impossible in any circuit, narrowing the exact cost over GF(2) strictly to 6 or 7.
Attribution and prior art
Prior art: This is a partial and apparently new result, establishing the first non-bilinear lower bound >= 6 for unrestricted XAG over F_2.
Register references
- Entry: MF-180
- Prior art: Winograd (1971); Hopcroft and Kerr (1971); Strassen (1969); Lemma B (MF-145)
- Receipt artifacts:
- programs/corridor-sweep-20260901/wave2-m2-closure/m2_qmc.py
- programs/corridor-sweep-20260901/wave2-m2-closure/multi_satlib.py
- programs/corridor-sweep-20260901/wave2-m2-closure/m2_k6.cnf
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 3 receipt files bundled (4 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.