Grothendieck constant is norm of Strassen matrix multiplication tensor

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: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.