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

  • $\begingroup$ Do you mean vector norms? $\endgroup$ – Taufi Nov 23 '16 at 18:45
  • $\begingroup$ Yes, apologies for the typo $\endgroup$ – user147825 Nov 23 '16 at 18:49
  • 1
    $\begingroup$ 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|$. $\endgroup$ – MattG88 Nov 23 '16 at 20:47

Here is my proof: \begin{equation} \|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 \end{equation}

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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