Show that $|\sum_{i,j} a_{ij} x_i x_j|\le \max_i |x_i|\cdot \max_j |y_j|$ is equivalent to $|\sum_{i,j} a_{i,j} x_i y_j |\le 1$ Show that $|\sum_{i,j} a_{ij} x_i y_j|\le \max_i |x_i|\cdot \max_j |y_j|$ for all $x_i,y_j \in \mathbb{R}$ is equivalent to
$$
\bigg|\sum_{i,j} a_{i,j} x_i y_j \bigg|\le 1\quad \forall x_i,y_j \in \{+1,-1\}.$$
Source: this is exercise 3.5.2 from Vershynin's book which is supposed to be very simple but I spend a long time on it.
 A: We have 2 formulations. The first is:
$$
\forall x,y\in\mathbb{R}^n,\qquad \left\lvert \sum_{1\leq i,j\leq n} a_{ij} x_i y_j\right\rvert \leq \lVert x\rVert_\infty \lVert y\rVert_\infty \tag{1}
$$
We want to prove that this is equivalent to the following:
$$
\forall x,y\in\{-1,1\}^n,\qquad \left\lvert \sum_{1\leq i,j\leq n} a_{ij} x_i y_j\right\rvert \leq \lVert x\rVert_\infty \lVert y\rVert_\infty = 1 \tag{2}
$$
Now, it is easy to check that (1) is equivalent to (3):
$$
\forall x,y\in[-1,1]^n,\qquad \left\lvert \sum_{1\leq i,j\leq n} a_{ij} x_i y_j\right\rvert \leq 1 \tag{3}
$$
(One direction is clear, again, and for the other we can just consider $x'=x/\lVert x\rVert_\infty$ and $y'=y/\lVert y\rVert_\infty$ and apply (3) to them in order to get (1).)
So we want to prove that (2) and (3) are equivalent. (3) implies (2), so it remains to prove that (2) implies (3). To do so, assume (2), and pick any $x,y\in[-1,1]^n$: we want to show that $\left\lvert \sum_{1\leq i,j\leq n} a_{ij} x_i y_j\right\rvert \leq 1$. Without loss of generality, assume that $\sum_{1\leq i,j\leq n} a_{ij} x_i y_j\geq 0$, and rewrite
$$
0 \leq \sum_{1\leq i,j\leq n} a_{ij} x_i y_j = \sum_{i=1}^n x_i \left( \sum_{j=1}^n a_{ij}y_j \right)
$$
Define $u\in\{-1,1\}^n$ by
$$
u_i = \begin{cases}
1 &\text{ if } \sum_{j=1}^n a_{ij}y_j \geq 0\\
-1&\text{ if } \sum_{j=1}^n a_{ij}y_j < 0
\end{cases}
$$
and observe that
$$
0 \leq \sum_{i=1}^n x_i \left( \sum_{j=1}^n a_{ij}y_j \right)
\leq \sum_{i=1}^n \left| \sum_{j=1}^n a_{ij}y_j \right|
= \sum_{i=1}^n u_i \left( \sum_{j=1}^n a_{ij}y_j \right)
= \sum_{i=1}^n \sum_{j=1}^n a_{ij}u_i y_j \tag{4}
$$
Similarly, define $v\in\{-1,1\}^n$ by
$$
v_j = \begin{cases}
1 &\text{ if } \sum_{i=1}^n a_{ij}u_i \geq 0\\
-1&\text{ if } \sum_{i=1}^n a_{ij}u_i < 0
\end{cases}
$$
so that
and observe that
$$
0 \leq \sum_{i=1}^n \sum_{j=1}^n a_{ij}u_i y_j
= \sum_{j=1}^n y_j \left( \sum_{i=1}^n a_{ij}u_i \right)
\leq \sum_{j=1}^n \left| \sum_{i=1}^n a_{ij}u_i \right|
= \sum_{j=1}^n v_j \left( \sum_{i=1}^n a_{ij}u_i \right) \tag{5}
$$
Combining (4) and (5), we get
$$
0 \leq \sum_{i=1}^n \sum_{j=1}^n a_{ij}x_iy_j 
\leq \sum_{i=1}^n \sum_{j=1}^n a_{ij}u_i y_j
\leq \sum_{i=1}^n \sum_{j=1}^n a_{ij}u_i v_j
\leq 1 \tag{6}
$$
the very last inequality by assumption (2). This proves that (2) implies (3), as we wanted.
A: This is very easy as it turns out. Just replace $x_i, y_j$ to their "maxes" and show that $|\sum a_{i,j}| \le 1$ using the assumption.
