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 $\omega$ and Grothendieck’s constant $K_G$ — are different measures of size for the same underlying object: the matrix multiplication tensor, i.e., the 3-tensor or bilinear operator $\mu _{l,m,n} : {\mathbb {F}}^{l \times m} \times {\mathbb {F}}^{m \times n} \rightarrow {\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) the tensor rank of $\mu _{l,m,n}$. We will show that Grothendieck’s constant is the least upper bound on a tensor norm of $\mu _{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

$$\begin{aligned} ||\mu _{l,m,n}||_{1,2,\infty } =\max _{X,Y,M\ne 0}\frac{|{{\,\mathrm{tr}\,}}(XMY)|}{||X||_{1,2}||Y||_{2,\infty }||M||_{\infty ,1}}\leqslant K_G. \end{aligned}$$

We prove that Grothendieck’s inequality is unique in the sense that if we generalize the $(1,2,\infty )$-norm to arbitrary $p,q, r \in [1, \infty ]$,

$$\begin{aligned} ||\mu _{l,m,n}||_{p,q,r}=\max _{X,Y,M\ne 0}\frac{|{{\,\mathrm{tr}\,}}(XMY)|}{||X||_{p,q}||Y||_{q,r}||M||_{r,p}}, \end{aligned}$$

then $(p,q,r )=(1,2,\infty )$ is, up to cyclic permutations, the only choice for which $||\mu _{l,m,n}||_{p,q,r}$ is uniformly bounded by a constant independent of l, m, n.