# Grothendieck constant is norm of Strassen matrix multiplication tensor

Preprint · Jinjie Zhang, Shmuel Friedland, Lek-Heng Lim

- Archive id: arxiv:1711.04427
- Published: 2017-11-13
- arXiv: https://arxiv.org/abs/1711.04427
- Source URL: https://arxiv.org/abs/1711.04427
- PDF: https://arxiv.org/pdf/1711.04427
- Provenance: arxiv

## Abstract

We show that two important quantities from two disparate areas of complexity theory --- Strassen's exponent of matrix multiplication $ω$ and Grothendieck's constant $K\_G$ --- are intimately related. They are different measures of size for the same underlying object --- the matrix multiplication tensor, i.e., the $3$-tensor or bilinear operator $μ\_{l,m,n} : \\mathbb{F}^{l \\times m} \\times \\mathbb{F}^{m \\times n} \\to \\mathbb{F}^{l \\times n}$, $(A,B) \\mapsto AB$ defined by matrix-matrix product over $\\mathbb{F} = \\mathbb{R}$ or $\\mathbb{C}$. It is well-known that Strassen's exponent of matrix multiplication is the greatest lower bound on (the log of) a tensor rank of $μ\_{l,m,n}$. We will show that Grothendieck's constant is the least upper bound on a tensor norm of $μ\_{l,m,n}$, taken over all $l, m, n \\in \\mathbb{N}$. Aside from relating the two celebrated quantities, this insight allows us to rewrite Grothendieck's inequality as a norm inequality \\\[ \\lVertμ\_{l,m,n}\\rVert\_{1,2,\\infty} =\\max\_{X,Y,M\\neq0}\\frac{\|\\operatorname{tr}(XMY)\|}{\\lVert X\\rVert\_{1,2}\\lVert Y\\rVert\_{2,\\infty}\\lVert M\\rVert\_{\\infty,1}}\\le K\_G. \\\] We prove that Grothendieck's inequality is unique: If we generalize the $(1,2,\\infty)$-norm to arbitrary $p,q, r \\in \[1, \\infty\]$, \\\[ \\lVertμ\_{l,m,n}\\rVert\_{p,q,r}=\\max\_{X,Y,M\\neq0}\\frac{\|\\operatorname{tr}(XMY)\|}{\\\|X\\\|\_{p,q}\\\|Y\\\|\_{q,r}\\\|M\\\|\_{r,p}}, \\\] then $(p,q,r )=(1,2,\\infty)$ is, up to cyclic permutations, the only choice for which $\\lVertμ\_{l,m,n}\\rVert\_{p,q,r}$ is uniformly bounded by a constant independent of $l,m,n$.

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

---
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.