Please prove or disprove that, for symmetric matrix $A=A^T$, we have

$$\max_{x \in \{\pm 1\}^n} x^T A x \geq \mbox{Tr}(A)$$

2

$\begingroup$
$\endgroup$

Please prove or disprove that, for symmetric matrix $A=A^T$, we have

$$\max_{x \in \{\pm 1\}^n} x^T A x \geq \mbox{Tr}(A)$$

2

$\begingroup$
$\endgroup$

We have $$ \sum_{x\in\{\pm1\}^n}x^TAx =2^{n-1}\sum_i\sum_{x_i\in\{\pm1\}}a_{ii}x_i^2 +2^{n-2}\cdot 2\sum_{i<j}\sum_{x_i,x_j\in\{\pm1\}}x_ix_ja_{ij} =2^n\operatorname{tr} A+0, $$ so one of the summands is at least $\operatorname{tr}A$.