# What is the maximum value of $x^TAx$ subject to $x\in\{\pm1\}^n$?

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

$$$$\max_{x\in\{\pm1\}^n}x^TAx=\sum a_{ij}$$$$

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:

$$$$A= \begin{bmatrix} 2 & 3 & 1 \\ 3 & 10 & -8 \\ 1 & -8 & 17 \end{bmatrix}.$$$$ $$$$\max_{x\in\{\pm1\}^n}x^TAx=49<\sum |a_{ij}|=53$$$$ 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 :)

• in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong – Lee Nov 15 '18 at 7:39
• so $|x_i|$=1 and $||x||_{\infty}=1$ are similar? – Lee Nov 15 '18 at 7:49
• what I wanted to say is that all elements of $x$ are equal to 1 or -1, so I think I will better stick to $|x_i|=1$ – Lee Nov 15 '18 at 7:54
• – Rodrigo de Azevedo Nov 15 '18 at 7:59
• This is known as a Binary Quadratic Problem and is hard. There are some solvers for it, for instance www-lipn.univ-paris13.fr/BiqCrunch and you can have some success solving a sequence of semidefinite relaxations. – Michal Adamaszek Nov 15 '18 at 10:00

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, $$$$A= \begin{bmatrix} 2 & 3 & 1 \\ 3 & 10 & -8 \\ 1 & -8 & 17 \end{bmatrix}$$$$ is structurally unbalanced so we can never achieve 53. However, $$$$A= \begin{bmatrix} 2 & 3 & -1 \\ 3 & 10 & -8 \\ -1 & -8 & 17 \end{bmatrix}$$$$ is structurally balanced and for $$x=[1\quad 1\quad -1]'$$ or $$x=[-1\quad -1\quad 1]'$$ we can achieve 53.