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.

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$

share|improve this question
    
$(|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
add comment

3 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
OK thanks, got it –  ASROMA Oct 7 '12 at 8:24
add comment

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

share|improve this answer
add comment

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!

share|improve this answer
    
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
1  
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
show 2 more comments

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.