Let $A \in \mathbb{R}^{n\times n}$ be symmetric and positive definite. What is the following maximum?
$$\max_{x\in\{\pm1\}^n}x^T A x$$
My attempt:
if all $a_{ij}\geq 0$, then
\begin{equation} \max_{x\in\{\pm1\}^n}x^TAx=\sum a_{ij} \end{equation}
and in this case $x=[1\quad 1\quad\cdots\quad 1]'$ or $x=[-1\quad -1\quad\cdots\quad -1]'$.
if some $a_{ij}<0$, then situation is not clear, but we know that $x^TAx\leq\sum{|a_{ij}|}$.
For example:
\begin{equation} A= \begin{bmatrix} 2 & 3 & 1 \\ 3 & 10 & -8 \\ 1 & -8 & 17 \end{bmatrix}. \end{equation} \begin{equation} \max_{x\in\{\pm1\}^n}x^TAx=49<\sum |a_{ij}|=53 \end{equation} and in this case $x=[1\quad1\quad-1]'$ or $x=[-1\quad-1\quad1]'$. So idea is to sacrifice $2a_{13}$ since it is smaller than $2a_{23}$ and $2a_{12}$.
Is there any systematic way to tell the maximum of $x^TAx$ for any $n$ if $A$ is given? and if yes how to find $x$ that will give the maximum? Any suggestions are welcome :)
I found an answer, maybe will be useful for someone.
For details go to this paper: http://users.isy.liu.se/en/rt/claal20/Publications/bipartite_consensus.pdf
Here $A$ represents an undirected graph. If $A$ is structurally balanced (condition of structurally balanced given in the paper), then $\max x^TAx = \sum |a_{ij}|$ and we can find at which corner objective function achieves maximum. However, if $A$ is not structurally balanced, $\sum |a_{ij}|$ can never be achieved. In this case, we have to go through all corners numerically to find the maximum.
For example, $\begin{equation} A= \begin{bmatrix} 2 & 3 & 1 \\ 3 & 10 & -8 \\ 1 & -8 & 17 \end{bmatrix} \end{equation}$ is structurally unbalanced so we can never achieve 53. However, $\begin{equation} A= \begin{bmatrix} 2 & 3 & -1 \\ 3 & 10 & -8 \\ -1 & -8 & 17 \end{bmatrix} \end{equation}$ is structurally balanced and for $x=[1\quad 1\quad -1]'$ or $x=[-1\quad -1\quad 1]'$ we can achieve 53.