I have this problem to solve
$$\max_{\mathbf{v} \in \{-1,1\}^n} \mathbf{v}^T A \mathbf{v}$$
where $A$ is a $n$ by $n$ symmetric (real) square matrix where each element $a_{ij} \in [-b,+b]$.
I'd like to determine properties of $A$ where $\mathbf{v}^T A \mathbf{v} < 0$ holds. I know that I can check whether the eigenvalues of $A$ are all negative to see $\mathbf{v}^T A \mathbf{v} < 0$. But I want to determine properties of $A$ that gives $\mathbf{v}^T A \mathbf{v} < 0$ for all $\mathbf{v} \in \{-1,1\}^n$ only. In a sense, I'd like to know the structure of matrix $A$ that is 'negative definite' under only such binary vectors.
I did literature search but couldn't find anything much related to this particular problem. Perhaps someone can shed a light.
Let $\mathrm Q : = - \mathrm A$. Consider the following unconstrained binary quadratic program
$$\underset{\mathrm x \in \{\pm 1\}^n}{\text{minimize}} \quad \mathrm x^{\top} \mathrm Q \,\mathrm x$$
or, equivalently, the following quadratically constrained quadratic program (QCQP) in $\mathrm x \in \mathbb R^n$
$$\begin{array}{ll} \text{minimize} & \mathrm x^{\top} \mathrm Q \,\mathrm x\\ \text{subject to} & x_i^2 = 1 \quad \forall i \in [n]\end{array}\tag{QCQP}$$
where $[n] := \{1,2,\dots,n\}$. Both optimization problems above are hard (even when $\mathrm Q \succeq \mathrm O_n$).
The QCQP yields the following Lagrangian
$$\mathcal{L} (\mathrm x, \lambda) := \mathrm x^{\top} \mathrm Q \,\mathrm x - \sum_{i=1}^n \lambda_i (x_i^2 - 1) = \mathrm x^{\top} \left( \mathrm Q - \mbox{diag} (\lambda) \right) \mathrm x + 1_n^{\top} \lambda$$
The dual of the QCQP [PP&SL'03, PP&SL'06] is, thus,
$$\begin{array}{ll} \text{maximize} & 1_n^{\top} \lambda\\ \text{subject to} & \mbox{diag} (\lambda) \preceq \mathrm Q\end{array}$$
Hence, we have the following semidefinite program (SDP) in $\Lambda$
$$\begin{array}{ll} \text{maximize} & \mbox{tr} (\Lambda)\\ \text{subject to} & \Lambda_{ij} = 0 \quad \forall i \neq j\\ & \Lambda \preceq \mathrm Q\end{array}$$
which is convex and, thus, easy (unlike the QCQP). This SDP does provide a lower bound on the minimum of the QCQP. If the lower bound is positive, we can immediately conclude that
$$\mathrm x^{\top} \mathrm Q \,\mathrm x > 0$$
for all $\mathrm x \in \{\pm 1\}^n$. If the lower bound is non-positive, we cannot conclude anything, unfortunately.
References
[PP&SL'03] Pablo Parrilo, Sanjay Lall, Quadratically Constrained Quadratic Programming, 2003.
[PP&SL'06] Pablo Parrilo, Sanjay Lall, Quadratically Constrained Quadratic Programming, 2006.