# Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries

My question concerns the NP-hardness of the following discrete optimization problem:

Given a matrix $$A \in \{ \pm 1 \}^{m\times n}$$,

$$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm 1 \}^n}{\text{maximize}} & x^T A \, y\end{array}$$

Is this problem known to be NP-hard?

• If $A$ can also have zero entries, then it is NP-hard. I doubt this is really necessary, but I don't have an immediate argument for this.
– J.G
Jun 23, 2021 at 19:24