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 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 $\mu_{ 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 $\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 \[ \lVert\mu_{ 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\mu_{ 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\mu_{ l,m,n}\rVert_{ p,q,r}$ is uniformly bounded by a constant independent of $l,m,n$.
Categories: cs.CC