1-norm is larger than the Euclidean norm

[Dr. Seafood]

"1-norm" is larger than the Euclidean norm

Define, for each [itex]\vec{x} = (x_1, \ldots, x_n) \in \mathbb{R}^n[/itex], the (usual) Euclidean norm [itex]\Vert{\vec{x}}\Vert = \sqrt{\sum_{j = 1}^n x_j^2}[/itex] and the 1-norm [itex]\Vert{\vec{x}}\Vert_1 = {\sum_{j = 1}^n |x_j|}[/itex].

How can we show that, for all [itex]\vec{x} \in \mathbb{R}^n[/itex], we have [itex]\Vert{\vec{x}}\Vert \leq \Vert{\vec{x}}\Vert_1[/itex]?

I'm thinking of writing [itex]\Vert{\vec{x}}\Vert^2 \leq \Vert{\vec{x}}\Vert_1^2[/itex] and then showing (probably inductively) that the sum of squares of (finitely) many numbers is not larger than the square of the sum of the absolute values of the same numbers; i.e. show [itex]{\sum_{j = 1}^n x_j^2} \leq (\sum_{j = 1}^n |x_j|)^2[/itex] by induction on n. For n = 1 and 2 this is simple enough. The inductive step is tricky, but I feel like using an induction argument is totally overdoing it.

I ask this because I read that this is trivial, but I don't see it immediately. Do you?

 

[CompuChip]

If you try writing out what
[tex]\left( \sum_{j = 1}^n |x_j| \right)^2 = \left( \sum_{i = 1}^n |x_i| \right) \cdot \left( \sum_{j = 1}^n |x_j| \right)[/tex]
really means, you will find that it is equal to
[tex]\sum_{j = 1}^n x_j^2 + A[/tex]
where you can quite easily show (from the explicit expression for A) that A > 0.

 

[lavinia]

Define, for each [itex]\vec{x} = (x_1, \ldots, x_n) \in \mathbb{R}^n[/itex], the (usual) Euclidean norm [itex]\Vert{\vec{x}}\Vert = \sqrt{\sum_{j = 1}^n x_j^2}[/itex] and the 1-norm [itex]\Vert{\vec{x}}\Vert_1 = {\sum_{j = 1}^n |x_j|}[/itex].

How can we show that, for all [itex]\vec{x} \in \mathbb{R}^n[/itex], we have [itex]\Vert{\vec{x}}\Vert \leq \Vert{\vec{x}}\Vert_1[/itex]?

I'm thinking of writing [itex]\Vert{\vec{x}}\Vert^2 \leq \Vert{\vec{x}}\Vert_1^2[/itex] and then showing (probably inductively) that the sum of squares of (finitely) many numbers is not larger than the square of the sum of the absolute values of the same numbers; i.e. show [itex]{\sum_{j = 1}^n x_j^2} \leq (\sum_{j = 1}^n |x_j|)^2[/itex] by induction on n. For n = 1 and 2 this is simple enough. The inductive step is tricky, but I feel like using an induction argument is totally overdoing it.

I ask this because I read that this is trivial, but I don't see it immediately. Do you?

work out the case for two variables first. Here you can see that the unit ball in the 1-norm is contained completely inside the unit ball for the 2 norm. Algebraically if x + y =1 then

x^2 + y^2 +2xy = 1 so the 2 norm is less than the 1 norm.