# Why is this true: $\|x\|_1 \le \sqrt n \cdot \|x\|_2$?

Stuck, help, please, I am really new to this. I opened the 2-norm and multiplied by $n$, then I am thinking to square both sides. The problem is that I do not know how to open $(x_1 + x_2 + ... + x_n)^2$

$\|x\|_1 \leqslant \sqrt n\cdot \|x\|_2$

-
$(|x_1| + \dots + |x_n|)^2 = \sum_{i=1}^n \sum_{j=1}^n |x_i||x_j|$. You want absolute values in the expansion of $\| x \|_1$. –  Patrick Da Silva Oct 7 '12 at 6:55
this is known, but how it is helping me to answer the main question? –  ASROMA Oct 7 '12 at 7:20
You wanted to know how to expand it, I did? =) –  Patrick Da Silva Oct 7 '12 at 7:52

Hint: This is Cauchy-Schwarz inequality applied to the vectors $x=(|x_k|)_{1\leqslant k\leqslant n}$ and $y=(y_k)_{1\leqslant k\leqslant n}$ defined by $y_k=1$ for every $k$.

-
OK thanks, got it –  ASROMA Oct 7 '12 at 8:24
The most elegant answer suggested. Thanks. –  Yonatan Jul 6 '14 at 19:16
Should it be $(|x_1|,\cdots,|x_n|)$? –  blue Aug 18 '14 at 7:45
@blue Yes, this is probably even simpler using these. Thanks. –  Did Aug 18 '14 at 7:46

We will expand and then complete squares Square up both sides and expand then you get $$\sum _{i=1}^{n} \sum _{j=1}^{n} |x_i| |x_j| \leq n\sum _ {i=1}^{n} x_i^2$$

$$\sum _{i=1}^{n} \sum _{j=1}^{n} |x_i| |x_j|= \sum_ {1\leq i<j\leq n}2|x_i||x_j| + \sum_ {i=1}^{n} x_i^2$$

So it suffices to prove $$\sum_ {1\leq i<j\leq n}2|x_i||x_j|\leq (n-1)\sum _ {i=1}^{n} x_i^2$$ But $$\sum_ {1\leq i<j\leq n}(|x_i|-|x_j|)^2 =\sum_ {1\leq i<j\leq n} (x_i^2+x_j^2 -2|x_i||x_j|)=$$ $$\sum_ {1\leq i<j\leq n} (x_i^2+x_j^2)+\sum_ {1\leq i<j\leq n}( -2|x_i||x_j|)\geq 0$$

But $$\sum_ {1\leq i<j\leq n} (x_i^2+x_j^2)=\sum_ {1\leq i<j\leq n}x_i^2+\sum_ {1\leq i<j\leq n}x_j^2=\sum_ {i=1}^{n-1}x_i^2 (n-i)+\sum_ {j=2}^{n} x_j^2(j-1)= \sum_ {i=2}^{n-1}x_i ^2 (n-i)+\sum_ {i=2}^{n-1}x_i^2 (i-1)+(n-1)x_1^2+x_n^2(n-1)=$$ $$=(n-1)\sum_ {i=1}^{n}x_i^2$$ And we are done

-

Here's a different approach if you don't know Cauchy-Schwarz.

It suffices to show the inequality in the case where all the coordinates are positive since both norms don't change when we swap signs of the coordinates. So consider $D = \{ x = (x_1, \dots, x_n) \, | \, x_i \ge 0 , \| (x_1, \dots, x_n) \|_1 = C \}$ for some $C > 0$ and the function $$f(x_1, \dots, x_n) = n \sum_{i=1}^n x_i^2 - \left( \sum_{i=1}^n x_i \right) \left( \sum_{j=1}^n x_j \right).$$ The set $D$ is compact, so $f$ attains a minimum over $D$ because $f$ is a polynomial, hence continuous. We will show this minimum is zero.

Using Lagrange multipliers, one can find where the minimum of $f$ lies at. We compute : $$\frac{\partial f}{\partial x_k} = 2n x_k - 2 \left( \sum_{i=1}^n x_i \right)$$ hence $$\nabla f(x_1, \dots, x_n) = 2n(x_1, \dots, x_n) - 2 \left( \sum_{i=1}^n x_i, \sum_{i=1}^n x_i, \dots, \sum_{i=1}^n x_i \right).$$ One can write the constraint as $g(x_1, \dots, x_n) = x_1 + \dots + x_n$, hence using Lagrange multipliers gives us the following constraint on the minimum : there exists $\lambda \in \mathbb R$ such that $$\lambda (1,\dots,1) = \lambda \nabla g(x_1, \dots, x_n) = \nabla f(x_1, \dots, x_n) = 2n (x_1, \dots, x_n) - \left( \sum_{i=1}^n x_i, \dots, \sum_{i=1}^n x_i \right)$$ This means all coordinates are equal, i.e. $x_1 = \dots = x_n = \frac{\lambda + \sum_{i=1}^n x_i}{2n}$. Plugging this into $f$ gives $f(x_1, \dots, x_1) = 0$. We know that the minimum of $f$ does not lie on the boundary of $D$, because on the boundary of $D$ one of the coordinates of $f$ is zero, thus we can use induction on $n$ (the case $n=1$ is trivial because then $\|x\|_1 = \|x\|_2$ for all $x$). Therefore the minimum of $f$ is zero, hence $f$ is always positive, which gives $$n \sum_{i=1}^n x_i^2 \ge \left( \sum_{i=1}^n x_i \right) \left( \sum_{j=1}^n x_j \right) \quad \Longrightarrow \quad \sqrt n \| x \|_2 \ge \| x \|_1.$$ Hope that helps!

-
There exists Lagrange multipliers provided the extremum is reached in the interior of the domain. Hence, to complete this approach, one should show that the extremum is not reached at one or at several boundary points. –  Did Oct 7 '12 at 7:43
@did : I did, by induction. On the boundary of the domain, one of the coordinates is zero. It's possible you read my question while I was still editing. Please read again if you are still in doubt. –  Patrick Da Silva Oct 7 '12 at 7:50
i think i need to go with Schwarz since i know that one :) –  ASROMA Oct 7 '12 at 7:57
Indeed you were still editing, sorry about that. You write *We know that the minimum of $f$ does not lie on the boundary of $D$*: sorry but I am not sure I follow the argument you provide in support (especially since this is not true for $n=1$ and you mention an induction over $n$...). –  Did Oct 7 '12 at 8:08
This argument looks fine to me, you definitely could include it in your post. (By the way, I am wondering why you are wondering who is the downvoter, since to wonder who is voting what on this site is to engage oneself in a recognizedly futile endeavour--and no I did not downvote, but I resent having been forced to declare this.) –  Did Oct 7 '12 at 8:19