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 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μ_{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 $\Vert {\mu }_{l,m,n}{\Vert }_{p,q,r}$ is uniformly bounded by a constant independent of $l,m,n$.

12 pages

References in corpus (5)

• Grothendieck's constant and local models for noisy entangled quantum states
• Better local hidden variable models for two-qubit Werner states and an upper bound on the Grothendieck constant $K_G(3)$
• Qutrit witness from the Grothendieck constant of order four
• Quantum Violation: Beyond Clauser-Horne-Shimony-Holt Inequality
• An elementary and unified proof of Grothendieck's inequality

Cited by in corpus (1)

• An elementary and unified proof of Grothendieck's inequality