PaperfootJoin free
arXiv

Constructive proof caps the cost of multiplying matrices

An explicit algorithm shows the matrix multiplication exponent is at most 9/4, matching a bound recently claimed by OpenAI through non-constructive arguments.

Paper by Rafael Pass
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

In a theory preprint, researchers provide a self-contained constructive proof that the matrix multiplication exponent, a measure of how computational steps scale with matrix size, is at most 9/4. OpenAI recently claimed this bound through non-constructive arguments in Strassen's asymptotic spectral framework, counting exact scalar arithmetic operations over the complex numbers.

The authors explicitly construct a Strassen-style matrix multiplication identity and obtain the bound through ordinary block recursion, a technique of dividing matrices into smaller blocks. For every positive value gamma, the resulting algorithm multiplies two n-by-n integer matrices using integer arithmetic operations scaling on the order of n raised to the power of 9/4 plus gamma.

Why it matters

The proof demonstrates that the 9/4 bound on matrix multiplication can be achieved with a concrete algorithm rather than only non-constructive existence arguments. It establishes a direct theoretical guarantee for integer matrix multiplication using basic recursive blocking.

Caveats

The guarantee is a theoretical proof governing asymptotic operation counts rather than a benchmark of real-world execution speed on physical hardware. Furthermore, the findings are described in a preprint that has not yet undergone peer review.

In this paper

matrix multiplication exponent bound

Methods
polynomial packings (PP) (this paper)same-left polynomial packings (SL-PP) (this paper)

Results

polynomial packings (PP), integer arithmetic operations, for every γ>0: O(n^(9/4+γ))

For every γ>0, the resulting algorithm multiplies two n× n integer matrices using O(n^(9/4+γ)) integer arithmetic operations.

Abstract

What it shows

The matrix multiplication exponent satisfies ω≤9/4 via a self-contained constructive proof.

We give a self-contained constructive proof that the matrix multiplication exponent satisfies ω≤9/4.

Abstract

For every positive integer L, GL,L can be computed exactly using O(L^(6d)) matrix multiplications of the original coefficient sizes.

For every positive integer L, G_{L,L} can be computed exactly using O(L^{6d}) matrix multiplications of the original coefficient sizes.

Lemma 3.3 (Terminal evaluation).

For positive integers a,b,c,t with ct≥ a+2b-1, there is a same-left packing modulo ε of c+1 full products and one middle product using c copies of Full_{a,b+t}.

For positive integers a,b,c,t with ct≥ a+2b-1, there is a same-left packing modulo \varepsilon of

Lemma 2.4 (Primal packing).

Exchanging a and b in Ga,b corresponds to fixed reorderings of input and output coefficients without changing coefficient-matrix sizes.

For all positive integers a,b, exchanging a and b in G_{a,b} amounts to fixed reorderings of the coefficients of its inputs and output; the coefficient-matrix sizes remain unchanged.

Lemma 3.2 (Symmetry).

Quoted word for word from the full text on arXiv.

The paper

Matrix Multiplication from Polynomial Packings: A Constructive and Elementary Proof of ω≤9/4

Rafael Pass

arXiv, Oct 20, 2026, Open access, CC BY, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.28627

arXiv:2610.28627v1 in cs.CC

AbstractPDFHTML

Cite as BibTeX
@misc{pass2026matrix,
  title = {Matrix Multiplication from Polynomial Packings: A Constructive and Elementary Proof of $\omega\le9/4$},
  author = {Pass, Rafael},
  year = {2026},
  eprint = {2610.28627},
  archivePrefix = {arXiv},
  primaryClass = {cs.CC},
  doi = {10.48550/arxiv.2610.28627},
  url = {https://arxiv.org/abs/2610.28627}
}

Related