# prove matrix norm equivalence

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.

-
What is matrix $B$? – user1551 Dec 4 '12 at 15:35
@user1551: I defined B to be the vector containing the 1 norm of each column – user972276 Dec 4 '12 at 15:44

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

-
how do you prove that if $||x||_2 \le 1$ then $||x||_1 \le \sqrt {n}$ ? I am a little lost on that part. – user972276 Dec 7 '12 at 2:26
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. – copper.hat Dec 7 '12 at 2:34
sorry for all the questions but what is sgn $x_i$? – user972276 Dec 7 '12 at 2:41
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$. – copper.hat Dec 7 '12 at 4:51
$\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$ – copper.hat Dec 7 '12 at 5:08