4

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.

Daniel Li
  • 3,200
  • This question is confusing. The "for all real numbers" is ambiguous. It sounds like maybe $a_{ij}$ are fixed, but the "for all real numbers" makes it sound like maybe they're not. Also, what does $|x|$ and $|y|$ mean? Euclidean distance? Infinity norm? You need to put context into your questions, otherwise it's left to us to try to guess what you mean. Please ask clear questions, or else your questions will be down-voted and closed. – user803264 Jun 28 '20 at 04:18
  • 1
    I posted the clarified question. – Daniel Li Jun 28 '20 at 04:19
  • Gotcha, that's a lot better (and not what I would have guessed). You've been on the site for $4$ years now, so you must have seen this: How to ask a good question. You should be including some working/thoughts/context for your questions. Share with us what you know/understand about the problem, otherwise it could be down-voted/closed. – user803264 Jun 28 '20 at 04:24
  • 1
    $\sum a_{ij}x_iy_j$ is linear in each $x_i$ and $y_j$, and so it attains the extreme value at the boundary – user58955 Jun 28 '20 at 04:30
  • Note: this is exercise 3.5.2, not 5.3.2. Aso, it should be $a_{ij}x_i y_j$, not $a_{ij}x_i x_j$ in the first inequality. – Clement C. Jun 28 '20 at 04:32
  • @ClementC. Thank you. Do you have a proof of this? I'm really stuck. – Daniel Li Jun 28 '20 at 05:03
  • @user58955 Can you give me a reference or more detailed explanation? Thank you. – Daniel Li Jun 28 '20 at 05:04
  • @DanielLi Suppose that $|x|\infty\leq 1$ and $|y|\infty\leq 1$. For now, vary $x_1$ while fixing all the other variables. Note that $\sum a_{ij}x_iy_j$ is linear in $x_1$, i.e., it is $Ax_1 + B$ for some $A$ and $B$. The max of $|Ax_1+B|$ is obtained when $x_1 = 1$ or $x_1 = -1$. Hence we know that the max of $|\sum a_{ij}x_iy_j|$ is obtained when all coordinates of $x$ and $y$ are $-1$ or $+1$. Does this tell you something? – user58955 Jun 28 '20 at 05:08
  • @DanielLi I was writing a proof, only saw your comment now :) There's probably shorter than what I did, however. – Clement C. Jun 28 '20 at 05:10
  • @DanielLi Did my answer solve your question? – Clement C. Jun 29 '20 at 06:22
  • @ClementC. Thank you very much for the solution. I was able to see it with some intuitions here in the comment section. It is apparent to me that we can see the whole sum as a linear operator on $x$ and $y$ respectively and $x,y$ can only take values in a hypercube--the extreme values necessarily locate at "corner". I think your solution just writes down this rigorously by optimizing x first and then y. – Daniel Li Jun 29 '20 at 19:02
  • 1
    @DanielLi Yes -- at the end of the day, you objective is linear in both y and x separately, so it works out. – Clement C. Jun 29 '20 at 19:05

2 Answers2

3

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.

Clement C.
  • 67,323
0

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.

Daniel Li
  • 3,200
  • 1
    This is not so easy, though: the absolute values are outside the sum, so the summands may not all be non-negative. Try to write down your proposed argument, and see where it fails. – Clement C. Jun 28 '20 at 05:10
  • Yeah, you are right. I'm fuzzy headed. But this exercise is marked as "one cup" which is supposed to be very easy. Let me check your answer. – Daniel Li Jun 28 '20 at 05:12