Matrix multiplication exponent

A matrix is a rectangular grid of numbers. Multiply a grid with rows (1, 2) and (3, 4) by one with rows (5, 6) and (7, 8): the result has rows (19, 22) and (43, 50). Its first entry is $1\times5+2\times7=19$, pairing a row with a column. The usual method repeats this work for every output entry. For large square grids, can the arithmetic cost grow almost as slowly as the number of entries in the answer?[1] [3]

A matrix is a rectangular grid of numbers. Multiplying two square $n\times n$ matrices produces another square grid: each output entry sums the pairwise products from one row of the first matrix and one column of the second. There are $n^2$ output entries. Can multiplying arbitrary such inputs require arithmetic work with a growth rate as close to this square-growth scale as desired?

The usual row-column rule computes each output independently. A different approach first splits each matrix into four blocks. Strassen’s method multiplies seven pairs of suitable block combinations, then adds or subtracts the results to cancel unwanted terms; direct block multiplication needs eight block products. Repeating this structure on smaller blocks changes the growth rate to $O(n^{\log_2 7})$, with additions included. More sophisticated constructions lower upper bounds further. The arithmetic exponent $\omega$ is the infimum of achievable asymptotic powers: $\omega=2$ allows $O(n^{2+\varepsilon})$ operations for every positive $\varepsilon$. Arithmetic operations here are field additions, subtractions, multiplications and divisions; their count is not a count of bit operations or elapsed seconds.[1] [3]

Making each table twice as wide and twice as tall quadruples its number of entries. The target is an arithmetic-operation count whose growth can approach this square-growth scale as closely as desired. That target is called exponent two; it need not give a single exact square-growth bound. No proof reaches it or rules it out. Shortcuts that assume few nonzero entries do not settle the problem for arbitrary dense matrices—tables without that sparsity guarantee.[1] [2]

No known construction establishes $\omega=2$, and no lower bound proves $\omega>2$. The August 2026 sparse-multiplication preprint imposes bounds on nonzero input and output entries. Even its nearly quadratic case with dense inputs restricts output sparsity, unlike the unrestricted product here. A faster fixed-size algorithm or a barrier for an existing construction method also leaves the general limiting exponent open.[1] [2]

Matrix products combine transformations used in scientific computation and neural networks. They also combine connection information in graph algorithms. A cheaper general multiplication method could reduce a recurring cost in these larger computations; whether it helps a particular program still depends on its data and implementation.[1] [3]

Matrix multiplication composes linear transformations: applying $B$ and then $A$ to a vector $v$ gives $(AB)v$. Forming the combined transformation is itself a reusable computational task. Matrix products also feed graph-path and clique algorithms, so improving the relevant product can improve a larger method’s guarantee. The exponent addresses scaling for arbitrarily large inputs; practical speed also depends on extra additions, matrix size, data movement and hardware. This is why asymptotic breakthroughs and useful implementations are related goals with different tests.[1] [3]