# Symmetric Grothendieck inequality

Grothendieck's inequality states that for all $$n \times n$$ matrices $$(a_{ij})$$ such that

$$\max_{x \in \{\pm 1\}^n,\, y \in \{\pm 1\}^n} \left|\sum_{ij} a_{ij}\, x_i\, y_j\right| \leq 1,$$

there exists a universal constant $$K$$, such that for $$u_i, v_j$$ in any Hilbert space, $$\max_{x \in \{\pm 1\}^n,\, y \in \{\pm 1\}^n} \left|\sum_{ij} a_{ij} \langle u_i , v_j \rangle \right| \leq K.$$ I would like to prove the symmetric statement. For all symmetric matrices $$(a_{ij})$$ such that $$\max_{x \in \{\pm 1\}^n} \left|\sum_{ij} a_{ij} \,x_i\, x_j\right| \leq 1,$$ there exists a universal constant such that $$\max_{x \in \{\pm 1\}^n} \left|\sum_{i,j} a_{ij} \langle u_i , v_j \rangle \right| \leq 2K$$ for $$u_i, v_j$$ in any Hilbert space. This should be a consequence of the original inequality. I tried to use the polarization identity $$\langle Ax, y\rangle = \langle Au, u\rangle - \langle Av, v \rangle$$ where $$u = (x+y)/2$$ and $$v = (x-y)/2$$. However, as $$x$$ and $$y$$ vary over $$\pm 1$$ vectors, $$u$$ and $$v$$ can be vectors in $$\{\pm 1, 0\}$$.

• Your second and fourth max expression do not depend on $x$ and $y$. Apr 16 '18 at 18:11
• There is y dependence in both u and v. What do you mean? Apr 16 '18 at 18:24

I think this is an exercise from Vershynin's book. The statement does not seem correct without further assumptions of $$A$$.

[Update in March 2020: The electronic version of the book, available on Vershynin's homepage, has corrected this problem.]

For example, take $$A = \begin{pmatrix} -1000 & 0 \\ 0 & 1000 \end{pmatrix}$$ Then it holds for any $$x\in \{-1,1\}^2$$ that $$\sum_{i,j} A_{ij} x_i x_j = 0.$$ But when $$x=(1,1)$$ and $$y=(-1,1)$$, we have $$\sum_{i,j} A_{ij} x_i y_j = 2000.$$

A possible remedy is to assume that

1. the diagonal entries of $$A$$ are all $$0$$s, or
2. $$A$$ is PSD.

Before we prove our results, we first prove the following claim.

Claim. Let $$I\subseteq \{1,\dots,n\}$$ be an arbitrary subset. Then it holds for all $$x\in \{-1,1\}^n$$ that $$-1 \leq \sum_i a_{ii} + \sum_{\substack{i,j\in I\\ i\neq j}} a_{ij}x_i x_j \leq 1.$$

Proof of Claim. Fill up the coordinates of $$x$$ outside $$I$$ using $$\{-1,1\}$$ and there are $$M = 2^{n-|I|}$$ possibilities, call those filled vectors $$x_1,x_2,\dots,x_M$$. Then we have for each $$\ell=1,\dots,M$$, $$-1 \leq \sum_i a_{ii} + \sum_{i\neq j} a_{ij} (x_\ell)_i (x_\ell)_j \leq 1.$$ Summing over all $$M$$ such inequalities we have $$-M \leq M\sum_i a_{ii} + M \sum_{\substack{i,j\in I\\ i\neq j}} a_{ij} x_i x_j \leq M,$$ which proves the claim.

Then we can prove the following: if $$|\langle Ax,x\rangle|\leq 1$$ for any $$x\in \{-1,1\}^n$$, then $$|\langle Ax,x\rangle|\leq 1$$ for any $$x\in \{-1,0,1\}^n$$. The final result will follow from Grothendieck's inequality immediately, using the polarization identity.

Now we prove the claim above in the two cases of remedy.

1. When $$A$$ has zero diagonal entries, we have for any subset $$I\subseteq \{1,\dots,n\}$$ that $$-1 \leq \sum_{i,j\in I} a_{ij} x_i x_j \leq 1,$$ The the earlier claim follows by setting $$I$$ to be the support of $$x$$.
2. When $$A$$ is PSD, then $$0\leq \langle Az,z\rangle$$ already holds and it suffices to show that $$\langle Az,z\rangle \leq 1$$. Since $$A$$ is PSD, the diagonal entries are nonnegative, it follows from the claim $$\langle Az,z\rangle + \sum_{i\not\in \operatorname{supp}(z)} A_{ii}\leq 1$$ that $$\langle Az,z\rangle\leq 1$$.

I would like to point you to this paper, and I feel there should be a satisfactory answer there. https://arxiv.org/abs/2003.07345