Matrix multiplication: square, rectangular, and all-field exponents

Source and verification

This article explains family 107 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Arithmetic exponents and matrix shapes

Multiplying two $n\times n$ matrices by the entrywise formula uses order $n^3$ scalar operations. The matrix-multiplication exponent over a fixed field $F$ is the infimum ${\omega }_F$ of exponents attainable with arbitrarily small positive slack: a bound ${\omega }_F\le \tau$ means that for every $\epsilon >0$ there are algorithms using $O_{\epsilon }(n^{\tau +\epsilon })$ field operations.

This model counts operations, rather than the bit lengths of their inputs and outputs. Constants may depend on the fixed field and accuracy slack. An asymptotic exponent does not specify the matrix size at which the construction becomes useful.

Over the complex numbers, write $w(k)=\omega (1,k,1)$ for multiplying an $n\times \lceil n^k\rceil$ matrix by a $\lceil n^k\rceil \times n$ matrix. The dual exponent is

$$\alpha =\sup \{k\in [0,1]:w(k)=2\}.$$

The value two is the output-size scale. Rectangular results ask how large the inner dimension can be while retaining that scale.

🏷️ Three complementary claims

Family statements

The October manuscript claims ${\omega }_{\mathbb{C}}\le 9/4$, meaning $O_{\epsilon }(n^{9/4+\epsilon })$ arithmetic operations for every positive $\epsilon$. (OpenAI, 2026)

A September companion claims

$$\begin{array}{c}{\omega }_{\mathbb{C}}<2.258,\\ \alpha >0.465,\\ w(0.709)<\mathrm{2.092.}\end{array}$$

Its rectangular statements remain distinct contributions even though the October square bound is stronger. (OpenAI, 2026b)

A separate construction claims, for every fixed field $F$,

$${\omega }_F<\mathrm{2.371054886006746.}$$

It includes positive characteristic and supplies exact arithmetic algorithms over the original field. (OpenAI, 2026c)

The $9/4$ statement is over $\mathbb{C}$; the smaller all-field scope of the third numerical bound is not interchangeable with it. The rectangular companion transfers its strict square and $k=0.709$ bounds to characteristic zero and all but finitely many positive characteristics, without computing the exceptional primes. Its dual-exponent transfer is stated only in characteristic zero.

🏷️ Bilinear computations and separation costs

A bilinear algorithm forms products of linear combinations of the first and second inputs, then combines those products linearly into outputs. Pairing the output with a third vector records its coefficients as a trilinear array, or tensor. A rank-one tensor is a product of three linear forms; tensor rank counts the minimum number of such products in an exact expression.

A restriction substitutes linear forms independently in the three variable groups, called legs. A direct sum consists of computations using disjoint variables on all three legs. Tensor products encode repeated composition. A degeneration uses parameter-dependent substitutions and retains a leading coefficient; interpolation is needed to turn that limiting construction into exact asymptotic algorithms.

The shared issue in this family is separating candidate products that already have independent variables on two legs but still share the third. Paying for the separation matters: multiplying by an auxiliary tensor creates computational resources but also consumes rank. Merely counting the resulting matrix products would overstate the gain.

The October construction introduces tentative labels by a finite Fourier projection. A weighted degeneration retains the terms whose tentative and actual labels agree, using the square of their mismatch as the total weight. Each separated block gains an auxiliary dot product. At the exponential scale, the number of independent blocks compensates for the cost of the Fourier copies. The existence and locality of these substitutions are substantive lemmas, not consequences of the notation for a direct sum.

🏷️ A discrete growth mechanism behind nine fourths

The October proof uses numerical tensor invariants that add on direct sums, multiply on tensor products, and cannot increase under restriction. A detecting-invariant theorem relates bounds for all these invariants to arithmetic complexity. We use this theorem as an interface rather than developing the general spectral theory.

For each invariant, the manuscript defines a positive symmetric profile $P(a,b)$ from polynomial multiplication with coefficient lengths $a,b$. It obtains, for a positive parameter $t$,

$$\begin{array}{c}P(1,b)=b,\\ P(a,b)\le (a+b-1{)}^{1/t},\\ P(a,3h+a-1)\ge 3P(a,h).\end{array}$$

In addition, the increments $P(a,b+1)-P(a,b)$ decrease as $b$ increases; symmetry gives the analogous condition in the first argument. Interpolation gives the upper bound. A filtration and a three-sector separation give the concavity and shifted-tripling inequalities.

Once these inputs hold, the final growth calculation is elementary. Set $D_a=P(a,a)$ and $H_a=2D_a/(3a-1)$. Tripling at $h=a$ and decreasing increments imply

$$\begin{array}{c}2D_a\le P(a,4a-1)-D_a,\\ \begin{array}{rl}P(a,4a-1)-D_a& \le (3a-1){\Delta }_a,\end{array}\\ {\Delta }_a=P(a,a+1)-P(a,a).\end{array}$$

Hence the increment leaving the diagonal is at least $H_a$. Symmetry and concavity bound the two increments connecting successive diagonal entries by

$$D_a-D_{a-1}\ge H_{a-1}+H_a.$$

Substitution and rearrangement give, for $a\ge 2$,

$$H_a\ge \left(1+\frac{1}{3(a-1)}\right)H_{a-1}.$$

Since $H_1=1$ and $(1+1/(3j){)}^3\ge 1+1/j$, multiplication yields $H_a^3\ge a$. Also $(3a-1)/2\ge a$, so $D_a\ge a^{4/3}$. Comparing with the upper bound gives

$$a^{4/3}\le (2a-1{)}^{1/t}.$$

Taking logarithms and letting $a\to \infty$ forces $t\le 3/4$. The invariant has value $n^{3t}$ on square matrix multiplication, so the detecting theorem yields exponent at most $9/4$. The elementary endpoint calculation does not verify the preceding separation or detecting-invariant results.

🏷️ Rectangular dimensions and finite certificates

The September complex companion separates labels readable independently on two sides by adjoining an auxiliary tensor. Successive labels form conditional trees. Exact frequency counts give multinomial multiplicities, and their logarithms yield conditional entropies. The three reader pairs contribute separately to the three output dimensions.

For a finite construction using $n$ copies of a border-rank-three tensor and an auxiliary rank budget $R$, suppose the output contains $L$ independent products of dimensions $a\times b$ by $b\times c$. The relevant score at a proposed exponent $\beta$ is

$$\frac{\log L-\log R+(\beta /3)\log (abc)}{n}.$$

A score strictly above $\log 3$ gives the desired strict square improvement through the asymptotic sum inequality. The subtraction of $\log R$ records the full auxiliary charge.

The square proof builds an attainable-value function from finite constructions. Local count windows produce a differential comparison, and rational barrier estimates certify a strict gain. The rectangular argument instead optimizes a specified finite family of conditional-label trees. Explicit laws and rational entropy enclosures give the dual and $0.709$ claims. These are separate construction families; finite-family optimization is not a claim of globally optimal matrix multiplication.

🏷️ Staggering across extraction depths

The all-field paper starts with the parameter-five Coppersmith–Winograd tensor, splitting strands of lengths $8,4,2,1$. Each extraction has three directional capacities, and its guaranteed yield is their minimum. Pooling compatible stages can improve this minimum:

$$\sum _r\underset{j}{\min }{v}_{r,j}\le \underset{j}{\min }\sum _r{v}_{r,j}.$$

For example, capacities $(1,4,4)$, $(4,1,4)$, and $(4,4,1)$ give a sum of separate minima equal to three, but a pooled minimum equal to nine. This arithmetic illustrates the possible benefit; implementing it requires aligned priorities on the physical tensor legs.

The manuscript staggers different lots so that several splitting depths coexist. It retains their ancestry, inherited type restrictions, and physical placements. A recovery argument handles deleted variables orbit by orbit and reconstructs each coefficient exactly once over the original field. Fixed schedule boundary losses vanish by first sending the strand count to infinity and only then the number of lots to infinity.

Explicit rational parameters and logarithm intervals certify the reported exponent. The companion certificate programs were not executed for this article. We have reviewed the statements and selected mechanisms, including the full diagonal-growth argument, without independently verifying the tensor constructions or numerical certificates.

🏷️ Key steps and proof outlines

From a profile bound to one finite recursive algorithm

The final section “Discrete growth and the arithmetic exponent” separates two tasks. First, prove an upper bound for every detecting invariant; second, recover a finite bilinear algorithm to which ordinary divide-and-conquer applies. The inequality $t\le 3/4$ completes only the first task. (OpenAI, 2026a)

Let $T_d$ denote the tensor for multiplying square matrices of order $d$, and let $\nu$ denote the asymptotic rank exponent used in the source. Its detecting theorem says that for each integer $k<d^{\nu }$ some multiplicative invariant has value at least $k$ on $T_d$. The profile argument bounds every such value by $d^{9/4}$. Taking $k=\lceil d^{\nu }\rceil -1$ gives

$$d^{\nu }\le d^{9/4}+1.$$

After logarithms and $d\to \infty$, $\nu \le 9/4$. The invariant may change with $d$; uniformity of the upper bound over all invariants makes that harmless.

Fix $ϵ>0$ and choose a smaller $\delta >0$. The definition of the exponent supplies one fixed order $u$ and one exact rank decomposition of length $r<u^{9/4+\delta }$. Applying that decomposition to matrix blocks produces

$$S(N)\le rS(N/u)+C(N/u{)}^2.$$

The second term charges the additions and scalar multiplications required to form and combine the blocks. If $r>u^2$, the geometric recursion sum is $O(N^{{\log }_{u}r})$; if $r=u^2$, it is $O(N^2\log N)$. Both fit $O_{ϵ}(N^{9/4+ϵ})$. Padding to the next power of fixed $u$ changes the input size by only a constant factor. This explains why an exponent theorem includes arbitrarily small slack and need not supply a practical small-size decomposition.

Why the detecting theorem keeps an auxiliary cost only once

The source’s detecting-character argument has a useful computational interpretation. A hypothetical failure of detection yields a fixed auxiliary tensor $D$ and a nonzero tensor $s$ with a conversion

$$D+ks⟶D+T_{d}s.$$

The plus sign denotes a direct sum of independent computations. The auxiliary computation $D$ is returned and can be reused. Repeating the conversion $n$ times pays for $D$ once, so an initial budget of $nk$ copies of $s$, plus the fixed auxiliary rank, produces $n$ copies of $T_{d}s$. Tensor-power amplification then compares the resulting matrix dimensions with the definition of $\nu$. After the amplification limit, divide by $n$ and let $n\to \infty$: the fixed auxiliary cost disappears, forcing $k\ge d^{\nu }$, a contradiction.

This is not cancellation of a tensor from both sides of an inequality. The proof explicitly repeats a conversion that returns its auxiliary object. Keeping that distinction prevents an invalid cancellation rule from being hidden inside the exponent deduction.

Entropy certificates and all-field recovery

The rectangular companion measures a finite construction by output dimensions, direct-sum multiplicity, and auxiliary rank. For a rational type $p=(p_1,\dots ,p_q)$ with $n{p}_i$ integers, the number of words of that type is $n!/{\prod }_i(n{p}_i)!$. Stirling’s estimate gives

$$\frac{1}{n}\log \frac{n!}{{\prod }_i(n{p}_i)!}=-\sum _i{p}_i\log p_i+O(\log n/n),$$

for a fixed alphabet. Conditional type counts produce the conditional entropies in the label-tree construction. The finite certificate must leave a strict margin after subtracting the auxiliary rank charge and all approximation errors; an attractive decimal objective without that margin is insufficient. The three dimensions must be retained separately for the rectangular claims. (OpenAI, 2026b)

The all-field companion uses its extraction and recovery lemmas to obtain exact products over each fixed field. Where a degeneration first isolates a coefficient in an auxiliary parameter, interpolation converts it into finitely many exact evaluations; extension-field arithmetic, when used, must then be implemented over the original field at its charged cost. The source’s numerical exponent belongs to this complete extraction-and-recovery calculation. It does not follow by transferring the complex $9/4$ argument through characteristic reduction. (OpenAI, 2026c)

See Also

• Integer multiplication measures bit operations on tapes, rather than scalar field operations.
• Permanent–determinant lower bounds studies the size of a restricted representation model, a different complexity parameter from fast matrix arithmetic.

🏷️ Manuscripts and verification scope

• An Upper Bound of 9/4 for the Matrix Multiplication Exponent — pinned manuscript and companion source.
• Complex Matrix Multiplication Below 2.258 and Rectangular Bounds — pinned manuscript and companion source.
• Staggered extraction for exact matrix multiplication over every field — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page states the complex bound 9/4 and the rectangular conclusions, even though its manuscript list names the September companions rather than the October nine-fourths paper. Its second comparator covers the all-field bound. These are arithmetic-operation statements, not bit-complexity guarantees. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. An Upper Bound of 9/4 for the Matrix Multiplication Exponent.

🐻  OpenAI 2026b. Complex Matrix Multiplication Below 2.258 and Rectangular Bounds.

🐻  OpenAI 2026c. Staggered extraction for exact matrix multiplication over every field.