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


*

*the diagonal entries of $A$ are all $0$s, or

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


*

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

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

A: 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
