# Rectangular matrix multiplication from polynomial products

Preprint · Przemyslaw Uznanski

- Archive id: arxiv:2610.10494
- Published: 2026-10-07
- arXiv: https://arxiv.org/abs/2610.10494
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.10494
- PDF: https://arxiv.org/pdf/2610.10494
- Provenance: arxiv

## Abstract

In this note, we extend the matrix-multiplication analysis by OpenAI to rectangular products and prove $ω(1,k,1)\\le2$ for $0\\le k\\le\\frac{1}{2}$, and $ω(1,k,1)\\le1+k+\\frac{1}{4k}$ for $k\\ge\\frac{1}{2}$. In particular, $ω(1, \\frac{1}{2},1)=2$ and the dual exponent satisfies $α\\ge\\frac{1}{2}$. The proof uses explicit degenerations of convolution tensors, multinomial counting, and Strassen's spectral theorem. An angular constraint on three dot-product parameters gives both the rectangular curve and a bound for $ω(a,b,c)$. As an application, Zwick's algorithm for all-pairs shortest paths in directed unweighted graphs runs in $O(n^{2.5})$ time. Combining the rectangular bound with the $(\\min,+)$-product improvement of Alman and Vassilevska Williams further gives $O(n^{2.4999})$ running time.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

Cited in dossiers:
- [Algorithms & Complexity Breakthroughs: State of the Field (October 2026)](https://space-kitty.com/dossiers/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.