Equality involving infinity norm Say $A \in \mathbb{R}^{n \times m}$ is a real matrix and let
\begin{align}
 \left|\left| A \right|\right|_{\infty \rightarrow 1} = \max_{\substack{x \in \mathbb{R}^{n}\\\left|\left|x\right|\right|_\infty=1}} \left|\left| Ax\right|\right|_1
\end{align}
where $\left|\left| \cdot \right| \right|_1$ is the usual 1-norm.
It is claimed that
$$
\left|\left| A \right|\right|_{\infty \rightarrow 1}=\max_{\substack{x\in \{1,-1\}^n\\y\in \{1,-1\}^m }} \sum_{i,j} A_{ij}x_iy_j
 $$
It is not clear to me why this is true.
 A: I will assume $A\in\mathbb{R}^{m\times n}$, $y\in\mathbb{R}^{m}$ and $x\in\mathbb{R}^n$ as your notation is not quite clear (but does not affect the conclusion).
Note that for some $y = [y_1, y_2, \cdots, y_m]^T$,
$$ \|Ax\|_1 = \sum_{i = 1}^{m}\left|\sum_{j = 1}^{n}{A_{ij}x_j}\right| = \sum_{i = 1}^{m}\left(y_i\sum_{j = 1}^{n}{A_{ij}x_j}\right) $$
actually $y_i = sign(\sum_{j = 1}^{n}{A_{ij}x_j}) \in \{\pm 1\}$.
After that we have
$$ \|Ax\|_1 = \sum_{i = 1}^{m}\left(y_i\sum_{j = 1}^{n}{A_{ij}x_j}\right) = \sum_{j = 1}^{n}\left(x_j\sum_{i = 1}^{m}{A_{ij}y_i}\right) \le \sum_{j = 1}^{n}\left|\sum_{i = 1}^{m}{A_{ij}y_i}\right| $$
where $x_j \le |x_j| \le 1$ as $\|x\|_{\infty} = 1$, and obviously the equality holds when $x_j = sign(\sum_{i = 1}^{m}{A_{ij}y_i}) \in \{\pm 1\}$.
Now to this end, it should be clear that the original problem can be solved by some $x$ and $y$ with their elements taking values from $\{\pm 1\}$.
And this leads to the second form of your problem:
$$ \|A\|_{\infty\to 1} = \max_{x\in\{\pm 1\}^{n} \\ y\in\{\pm 1\}^{m}} {\sum_{i = 1}^{m}\left(y_i\sum_{j = 1}^{n}{A_{ij}x_j}\right)} = \max_{x\in\{\pm 1\}^{n} \\ y\in\{\pm 1\}^{m}} \sum_{i, j}y_iA_{ij}x_j $$
