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.
Best Answer
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$.