Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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
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. –  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
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$. –  copper.hat Dec 7 '12 at 4:51
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$ –  copper.hat Dec 7 '12 at 5:08

Could you provide a proof for your statement that:

Now note that for any norm and any $\sigma>0$ we have sup$_{\|x\|≤σ}$$\|Ax\|$=$\sigma$$\|A\|$

share|improve this answer
    
Can you please check formatting, I think there is some problem with double slashes –  Ram Mar 21 '13 at 15:36
    
I believe I just answered my own question. The above statement is due to the fact that a vector norm and its induced matrix norm satisfy the inequality: $\|Ax| \leq \|A\| \|x\|$ –  Ann Marie Mar 21 '13 at 16:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.