Integral maximization inequality

71 Views Asked by At

Is it true that for all symmetric $n \times n$ matrix, $(a_{ij})$, such that for $x \in \{\pm 1\}^n$ $$ \sum_{ij} a_{ij} x_i x_j \leq 1 $$ there exists a universal constant such that $$ \sum_{ij} a_{ij} x_i y_j \leq C $$ for all $x, y \in \{\pm 1\}^n$ . 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\}$.

1

There are 1 best solutions below

0
On

No, e.g. $x^T\pmatrix{n\\ &-n}x\equiv0$ for every $\{-1,1\}$-vector $x$, but $(1,1)\pmatrix{n\\ &-n}\pmatrix{1\\ -1}=2n$ is unbounded.