1
$\begingroup$

Given $A \in R^{m\times n}$, I need to prove:

$$||A||_2 \le \sqrt {m}||A||_\infty$$

I have tried a number of things and I just cant seem to get it to work.

Also, I need to prove:

$$||A||_2 \le \sqrt {n} ||A||_1$$

For this one, I have done: $e_i = [...,0,1,0,...] \in R^n$ where i is the position of the 1 in e.

$$||A||_1 = \max {\sum {|a_{ij}|}}=\max {||Ae_i||_1}$$ $$B => b_i = ||Ae_i||_1 \in R^n$$ $$||A||_1 = ||B||_\infty \le ||B||_2$$ $$||B||_2 = \sqrt {\sum {||Ae_i||_1^2}} \le \sqrt {\sum {||A||_1^2||e_i||_1^2}} = \sqrt {n}||A||_1$$

I dont know if this is correct or not because I have no idea how to get this to be greater than or equal to $||A||_2$. I feel like this is very close to what I need, just not quite there. Any help would be great.

  • 0
    What is matrix $B$?2012-12-04
  • 0
    @user1551: I defined B to be the vector containing the 1 norm of each column2012-12-04

1 Answers 1

2

For $y \in \mathbb{R}^m$ you have $\|y\|_2 = \sqrt{\sum_k y_k^2} \leq \sqrt{\sum_k \|y\|_\infty^2}= \sqrt{m} \|y\|_\infty$.

Hence $\|Ax\|_2 \leq \sqrt{m} \|Ax\|_\infty$, for all $x$. Now suppose $\|x\|_\infty\leq 1$, then we have $\|Ax\|_2 \leq \sup_{\|x\|_\infty\leq 1} \sqrt{m} \|Ax\|_\infty = \sqrt{m} \|A\|_\infty$. Now suppose $\|x\|_2\leq 1$. Then we have $\|x\|_\infty \leq 1$ and so $\|A\|_2 = \sup_{\|x\|_2\leq 1} \|Ax\|_2 \leq \sqrt{m} \|A\|_\infty$.

Now note that for any norm and any $\sigma>0$ we have $\sup_{\|x\|\leq \sigma} \|Ax\| = \sigma \|A\|$. It is straightforward to show that if $y \in \mathbb{R}^m$ you have $\|y\|_2 \leq \|y\|_1$. It is also straightforward to show that if $x \in \mathbb{R}^n$ and $\|x\|_2\leq 1$, then $\|x\|_1 \leq \sqrt{n}$ (ie, $B_2(0,1) \subset B_1(0,\sqrt{n})$).

Hence we have $\|Ax\|_2 \leq \|Ax\|_1$. Now suppose $\|x\|_1 \leq \sqrt{n}$, then we have $\|Ax\|_2 \leq \sup_{\|x\|_1 \leq \sqrt{n}}\|Ax\|_1 = \sqrt{n} \|A\|_1$, and since $B_2(0,1) \subset B_1(0,\sqrt{n})$, we have $\|A\|_2 = \sup_{\|x\|_2\leq 1} \|Ax\|_2 \leq \sqrt{n} \|A\|_1$.

  • 0
    how do you prove that if $||x||_2 \le 1$ then $||x||_1 \le \sqrt {n}$ ? I am a little lost on that part.2012-12-07
  • 1
    Use the Cauchy–Schwarz inequality on $x$ and the vector $y$ with $y_i = \mathbb{sgn}\, x_i$. Then $\langle y, x \rangle = \sum_i |x_i| \leq \|x\|_2 \|y\|_2$. Since $\|y\|_2 = \sqrt{n}$ we have the desired result.2012-12-07
  • 0
    sorry for all the questions but what is sgn $x_i$?2012-12-07
  • 0
    No problem. The sign of the number. If $x>0$, $\text{sgn}\, x = +1$, if $x<0$, $\text{sgn}\, x = -1$, and it doesn't matter here, but usually $\text{sgn}\, 0 = 0$.2012-12-07
  • 0
    is there a way to prove it without Cauchy-Schwarz? I am just trying to understand these norm equality questions from my class and my teacher doesnt allow us to use anything we have not proved in class unless we prove it ourselves.2012-12-07
  • 1
    Since $(|x_i|-|x_j|)^2 = |x_i|^2- 2 |x_i||x_j| + |x_j|^2 \geq 0$, you have $|x_i||x_j| \leq \frac{1}{2}( |x_i|^2 + |x_j|^2)$. Then $\|x\|_1^2 = (\sum_i |x_i|)(\sum_j |x_j|) = \sum_{i,j} |x_i||x_j| \leq \frac{1}{2}\sum_{i,j}(|x_i|^2 + |x_j|^2) = n \sum_i |x_i|^2 = n \|x\|_2^2$.2012-12-07
  • 0
    how does $1/2 \sum_{i,j}{(|x_i|^2 + |x_j|^2)} = n\sum_i {|x_i|^2}$? I thought $|x_i|^2 + |x_j|^2 = 2|x_i|^2$ so $1/2 \sum_{i,j}{(|x_i|^2 + |x_j|^2)}$ should equal $\sum_{i} {|x_i|^2}?$2012-12-07
  • 1
    $\frac{1}{2}\sum_{i,j}(|x_i|^2 + |x_j|^2) = \frac{1}{2}((\sum_i \sum_j |x_i|^2)+(\sum_i \sum_j |x_j|^2)) = \sum_i \sum_j |x_i|^2 = \sum_j (\sum_i |x_i|^2) = n \sum_i |x_i|^2$2012-12-07
  • 0
    doesnt that prove that $||x||_1 \le \sqrt {n}||x||_2$? I was wanting $||x||_2 \le \sqrt {n} ||x||_1$2012-12-07
  • 0
    I dont think you can say $(\sum_i {|x_i|})(\sum_j {|x_j|}) = \sum_{i,j} {|x_i||x_j|}$ because $||x||_1^2 \ne ||x||_2$2012-12-07
  • 0
    You need to do a little work. First, the above comment was to show that if $\|x\|_2 \leq 1$ then $\|x\|_1 \leq \sqrt{n}$. This follows immediately from the Cauchy–Schwarz inequality or from the comment above. Second, it is always true for finite sums that $(\sum_i a_i)(\sum_j b_j) = \sum_i \sum_j a_i b_j$.2012-12-07
  • 0
    ohhh ok that makes sense! thanks!2012-12-07
  • 0
    I'm not sure if your comment "any $\sigma>0$ we have $\sup_{\|x\|\leq \sigma} \|Ax\| = \sigma \|A\|$". is true. Could you please provide a brief proof? Certainly for " any $\sigma>0$ we have $\sup_{\|x\|\leq \sigma} \|Ax\| \leq \sigma \|A\|$". But I'm not sure about your equality symbol there...2018-09-29
  • 1
    @E.JHumphrey: Write $Ax = \sigma A {x \over \sigma}$. Note that $\{ x | \|x\| \le 1 \| = \{ {x \over \sigma} | \|x\| \le \sigma \}$. And $\|\sigma A y\| = \sigma \|Ay\|$.2018-09-29