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
    @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$.