Symmetric Grothendieck inequality

Question

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\}$.

Answer 1

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$.

Answer 2

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