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

  • $\begingroup$ Your second and fourth max expression do not depend on $x$ and $y$. $\endgroup$
    – LinAlg
    Apr 16 '18 at 18:11
  • $\begingroup$ There is y dependence in both u and v. What do you mean? $\endgroup$
    – JohnKnoxV
    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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.