2
$\begingroup$

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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .