# Vector Norms proof

At the moment I am trying to get my head around vector norms I have spent a lot of time trying to figure out how to show $\|x\|_1 \le \sqrt{n}\|X\|_2$

What I have got so far. $\|x\|_1^2=(\sum_i |x_i|)^2 = \sum_i|x_i|\sum_j|x_j|=\sum_i|x_i|^2 + \sum_i\sum_{j\neq i}|x_i||x_j|$

Is the following correct. If $\sum_i\sum_{j\neq i}|x_i||x_j| \le \frac{1}{2}\sum_i\sum_{j\neq i}(|x_i|+|x_j|)$

Then for the first term in the double summation we have $\frac{n-1}{2}\sum_{i=1}^{n}|x_i|^2$ and a similar result will apply to the second term. Which will lead to $\|x\|_1^2$ $\le$ $(n-1)\sum|x_i|^2$ $\le n \sum |x_i^2|$ and the result follows

• Do you mean vector norms? – Taufi Nov 23 '16 at 18:45
• Yes, apologies for the typo – user147825 Nov 23 '16 at 18:49
• I'm not sure about $\sum_i\sum_{j\neq i}|x_i||x_j| \le \frac{1}{2}\sum_i\sum_{j\neq i}(|x_i|+|x_j|)$. Maybe you mean: $\sum_i\sum_{j\neq i}|x_i||x_j| \le \frac{1}{2}\sum_i\sum_{j\neq i}(|x_i|^2+|x_j|^2)$. Besides you should add up $\sum_i|x_i|^2$ and $(n-1)\sum|x_i|^2$ to obtain $\n \sum |x_i^2|$. – MattG88 Nov 23 '16 at 20:47

Here is my proof: $$\|x\|_1^2=\left(\sum_i^n |x_i|\right)^2 = \sum_i|x_i|\sum_j|x_j|=\\=\sum_i|x_i|^2 + 2\sum_{i,j;\ i<j} |x_i||x_j|\le \sum_i|x_i|^2 +\sum_{i,j;\ i<j} \left(|x_i|^2+|x_j|^2\right)=\\=\sum_i|x_i|^2 +\sum_{i,j;\ i\ne j}|x_i|^2=\\=\sum_i|x_i|^2 +(n-1)\sum_i|x_i|^2 =n\sum_i|x_i|^2$$
where i have used $a^2+b^2\ge2ab$ in the second line. So taking the square root, it follows that $\|x\|_1\le\sqrt{n}\|x\|_2$.