Proving the max of a quadratic form ${\mathbf x}^T\mathbf A \mathbf x$ can be attained when $x$ is from $n$-dimensional hypercube

Question

updated: Maybe my original question is somewhat misleading. I rewrite some of the post.

This is some research problem I'm working on.

---

I have an $n\times n$ symmetric positive-definite matrix $\mathbf A$. I also have a set of $2^n$ vectors $\mathbf x_1,\cdots,\mathbf x_{2^n}$ from an $n$-dimensional hypercube $\gamma_n$ of $\{1, -1\}^n$.

I already know the maximum of the [quadratic form](http://mathworld.wolfram.com/QuadraticForm.html) of the matrix $\mathbf A$ and vectors $\mathbf x\in\{1, -1\}^n$ is a known constant $c$:

Using some kind of AM-GM like inequality, I know that the quadratic form is at most $c$

$$ \mathbf x^T \mathbf A \mathbf x \leq c \quad\text{subject to $\mathbf x \in \{1,-1\}^n$} $$

In this case, I want to show that

1. there exists a vector $\mathbf x\in\{1,-1\}^n$ that achieves $\mathbf x^T \mathbf A \mathbf x = c$, and
2. if that's possible, I'd like to show that this maximizer can be computed efficiently.

---

Some related problem is the '0-1 Positive-Definite Maximum Problem' from Girtzmann and Klee:

• Instance: a symmetric positive definite matrix $\mathbf B$ and an integer $\lambda$
• Question: Does there exist a vector $\mathbf x\in\{0,1\}^n$ such that $\mathbf x^T \mathbf B \mathbf x \geq \lambda$?

They showed that this problem is NP-Complete.

---

I think my problem is different from '0-1 Positive-Definite Maximum Problem' because I already know the upper bound of the quadratic form and ask whether this upper bound can be achieved from a vector from a hypercube.

My Question: Is there any trick for an existential proof that such a maximizer exists in my setting?

One trick I can come up on top of my head right now is the Averaging Argument, but this seems too strong: I'm afraid the averaging argument works only when all the $2^n$ quadratic form values amount to the desired maximum $c$.