Matrix Inequality involving bilinear forms

Question

For an $m \times n$ matrix $(a_{ij})$ of real numbers, we want to show that the following two conditions are equivalent:

1) $|\sum_{ij} a_{ij} x_i y_j | \leq 1$ for $x_i, y_j \in \{\pm 1\}$

2) $|\sum_{ij} a_{ij} x_i y_j| \leq \max |x_i| \max |y_j|$ for all numbers $x_i$, $y_j$.

Clearly, 2 implies 1. I would like to know why the reverse is true.

Answer 1

Let $S = \{(x,y)\in \mathbb{R}^m{\times\,}\mathbb{R}^n\mid x_i,y_j\in \{-1,1\},\;\text{for all}\;i,j\}$.

Let $D = \{(x,y)\in \mathbb{R}^m{\times\,}\mathbb{R}^n\mid x_i,y_j\in [-1,1],\;\text{for all}\;i,j\}$.

Let $f:\mathbb{R}^m{\times\,}\mathbb{R}^n\to \mathbb{R}$ be given by $$f(x,y)=\sum a_{ij}x_iy_j$$ for $1\le i \le m,\;1\le j \le n$.

Assume $|f(x,y)|\le 1$, for all $(x,y)\in S$.

For each each coordinate $v\in \{x_i\}\cup \{y_j\}$, regarding $v$ as unknown, with the other coordinates held fixed, $f$ is a linear polynomial in $v$. It follows that the maximum and minimum values of $f$ on $D$ can be realized at points of $S$.

Hence, $|f(x,y)|\le 1$, for all $(x,y)\in D$.

The desired result $$|f(x,y)|\le \max |x_i| \max |y_j|$$ for all $(x,y)\in \mathbb{R}^m{\times\,}\mathbb{R}^n$ follows by an appropriate scaling of $x$ and $y$.

Explicitly . . .

Let $(x,y)\in \mathbb{R}^m{\times\,}\mathbb{R}^n$.

Let $X=\max(|x_i|)$, and let $Y=\max(|y_j|)$.

We want to show $|f(x,y)|\le XY$.

If $X=0$ or $Y=0$, then $x=0$ or $y=0$, so $f(x,y)=0=XY$.

Next, assume $X,Y > 0$.

Then $\bigl({\large{\frac{x}{X}}},{\large{\frac{y}{Y}}}\bigr)\in D$, hence $$ |f(x,y)| = XY \left|f \bigl( {\small{\frac{x}{X}}},{\small{\frac{y}{Y}}} \bigr)\right| \le (XY)(1) =XY $$

Answer 2

Suppose 2) holds. Then $x,y$ (or possibly $-x,y$) solve $\max \{ y^T Ax | x \in [-1,1]^n, y \in [-1,1]^m \}$.

It is straightforward to show that we can always choose $x \in \{-1,1\}^n$, $y \in \{-1,1\}^m$.

Suppose $y_k \in (-1,1)$ then for sufficiently small $t$ we have $(y+t e_k)^T Ax \ge y^TAx$ and $y_k +t e_k \in \{-1,1\}$. Similarly for $x$.

Hence there is always a maximising $x,y$ such that $x \in \{-1,1\}^n$, $y \in \{-1,1\}^m$.

It follows that we need only consider $x \in \{-1,1\}^n$, $y \in \{-1,1\}^m$, from which it follows that 1) implies 2).

Actually, the above is too complicated.

We have $[-1,1]^p = \operatorname{co} E_p$, where $E_p= \{ \pm e_1 \pm \cdots \pm e_p \}$ and that $\max_{x \in [0,1]^p} a^T x = \max_{x \in E_p} a^T x$.

\begin{eqnarray} \max_{x \in [0,1]^n, y \in [0,1]^m} y^TAx &=& \max_{x \in [0,1]^n} \max_{ y \in [0,1]^m} y^TAx \\&=& \max_{x \in [0,1]^n} \max_{ y\in E_m} y^TAx \\&=& \max_{ y\in E_m} \max_{x \in [0,1]^n} y^TAx \\&=& \max_{ y\in E_m} \max_{x \in E_n} y^TAx \\&=& \max_{x \in E_n, y\in E_m} y^TAx \end{eqnarray}

Answer 3

Let $(x, y) \in \mathbb R^n \times \mathbb R ^m $, we define $$u_j = \left\{ \begin{array}{cc} 1~& \text{if $\sum_{i=1}^n a_{ij}x_i \ge 0$}\\ -1& \text{otherwise} \end{array}\right.$$ Now $$\left|\sum_{i=1}^n a_{ij} x_i\right| = \sum_{i=1}^n a_{ij} x_iu_j$$ Now we define $$v_i = \left\{ \begin{array}{cc} 1~& \text{if $\sum_{j=1}^m a_{ij}u_j \ge 0$}\\ -1& \text{otherwise} \end{array}\right.$$ so we have $$\left|\sum_{j=1}^m a_{ij} u_j\right| = \sum_{j=1}^m a_{ij} v_iu_j$$ Now $$\left|\sum_{j=1}^m\sum_{i=1}^n a_{ij}x_iy_j\right| \le \sum_{j=1}^m \left|\sum_{i=1}^n a_{ij} x_i\right||y_j| = \max |y_j| \left(\sum_{j=1}^m \left|\sum_{i=1}^n a_{ij} x_i\right|\right) = \max |y_j| \left(\sum_{j=1}^m \sum_{i=1}^n a_{ij} x_iu_j\right) \le \max |y_j| \left(\sum_{i=1}^n \left|\sum_{j=1}^m a_{ij} u_j\right||x_i|\right) \le \max |y_j| \max |x_i| \sum_{i=1}^n \left|\sum_{j=1}^m a_{ij} u_j\right| = \max |y_j| \max |x_i| \sum_{j=1}^m\sum_{i=1}^n a_{ij}v_iu_j$$

Then assume that 1) holds so 2) holds also.