Grothendieck constant is norm of Strassen matrix multiplication tensor

摘要

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) : F-lxm x F-mxn -> F-lxn, (A, B) bar right arrow AB defined by matrix-matrix product over F = R or 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 is an element of N. Aside from relating the two celebrated quantities, this insight allows us to rewrite Grothendieck's inequality as a norm inequality