We fix $A \in \mathcal{M}_{n}(\{-1,1\})$ and denote
$$m(A) := \min(S(A) \cap \mathbb{N}).$$
For $Y \in \{-1,1\}^{n}$, show that we have
$$\min\left\{\left|{}^{t}X A Y\right| \mid X \in \{-1,1\}^{n}\right\} \leqslant n$$
and deduce $m(A) \leqslant n$.