Non-zero real symmetric matrices that satisfy $2^{n-1}$ linear matrix equations

Question

Does there exist a nonzero symmetric matrix $X \in \mathbb R^{n \times n}$ such that $v^\top X v = 0$ for all $v \in \{-1,1\}^n$?

Answer 1

Note that

$$\mathrm v^\top \mathrm X \,\mathrm v = \mbox{tr} \left( \mathrm v^\top \mathrm X \,\mathrm v \right) = \mbox{tr} \left( \mathrm v \mathrm v^\top \mathrm X \right) = \langle \mathrm v \mathrm v^\top, \mathrm X \rangle$$

Although $\{\pm 1\}^n$ has cardinality $2^n$, there are only $2^{n-1}$ distinct symmetric , rank-$1$ matrices of the form $\mathrm v \mathrm v^\top$ with $\mathrm v \in \{\pm 1\}^n$. Note, for example, that $1_n 1_n^\top = (-1_n) (-1_n)^\top$. Hence, we have a total of $2^{n-1}$ linear equations in $\binom{n+1}{2}$ unknowns.

$$\langle \mathrm v \mathrm v^\top, \mathrm X \rangle = 0$$

Since $\mathrm v \in \{\pm 1\}^n$, matrix $\mathrm v \mathrm v^\top$ has only ones on its main diagonal. Thus, any matrix $\rm X$ that is both diagonal and traceless will be a solution. For example, one possible solution would be

$$\mathrm X = \mbox{diag} (1, \underbrace{0, \dots, 0}_{n-2 \text{ zeros}}, -1)$$