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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
up vote 2 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|cite|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
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

Your Answer


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.