# 1 and 2 norm inequality

While looking over my notes, my lecturer stated the following inequality; $$\|x\|_2 \leq \|x\|_1 \leq \sqrt{n}\|x\|_2$$ where $x \in \mathbb{R^n}.$ There was no proof given, and I've been trying to prove it for a while now. I know the definitions of the $1$ and $2$ norm, and, numerically the inequality seems obvious, although I don't know where to start rigorously.

Thank you.

We will show the more general case:

$\|\ \cdot \|_1$ , $\|\ \cdot \|_2$, and $\|\ \cdot \|_{\infty}$ are all equivalent on $\mathbb{R}^{n}$. And we have $$\|\ x \|_{\infty} \leq \|\ x \|_{2} \leq \|\ x \|_{1} \leq n \|\ x \|_{\infty}\$$

Every $x \in \mathbb{R}^{n}$ has the representation $x = ( x_1 , x_2 , \dots , x_n )$. Using the canonical basis of $\mathbb{R}^{n}$, namely $e_{i}$, where $e_i = (0, \dots , 0 , 1 , 0 , \dots , 0 )$ for $1$ in the $i^{\text{th}}$ position and otherwise $0$, we have that $$\|\ x \|_{\infty} = \max_{1\leq i \leq n} | x_i | = \max_{1\leq i \leq n} \sqrt{ | x_i |^{2} } \leq \sqrt{ \sum_{i=1}^{n} | x_ i |^{2} } = \|\ x \|_2$$ Additionally, $$\|\ x \|_2 = \sqrt{ \sum_{i=1}^{n} | x_i |^{2} } \leq \sum_{i=1}^{n} \sqrt{ | x_ i |^{2} } = \sum_{i=1}^{n} |x_i| = \|\ x \|_1$$ Finally, $$\|\ x_1 \|\ = \sum_{i=1}^{n} |x_i| \leq \sum_{i=1}^{n} | \max_{1 \leq j \leq n} x_j | = n \max_{i \leq j \leq n} | x_j | = n \|\ x \|_{\infty}$$ showing the chain of inequalities as desired. Moreover for any norm on $\mathbb{R}^{n}$ we have that $$\|\ x - x_{n} \|\ \to 0 \hspace{1cm} \text{as} \space\ \space\ n \to \infty$$ so that they are equivalent as this holds for any $x \in \mathbb{R}^{n}$ under any norm actually.

• If I wanted to more explicitly show that $\|\cdot\|_1$ was equivalent to $\|\cdot\|_2$ could I use the fact that $\|x\|_1\le\ n|x\|_\infty\iff\frac1n \|x\|_1\le\|x\|_\infty$ to deduce that $\frac1n \|x\|_1\le \|x\|_2\le \|x\|_1$? Or would I need to do something more explicit? – Jeremy Jeffrey James Mar 13 '18 at 22:05
• @JeremyJeffreyJames This should work: $$\|\ x \|_2 = \sqrt{ \sum_{i=1}^{n} | x_i |^{2} } \leq \sum_{i=1}^{n} \sqrt{ | x_ i |^{2} } = \sum_{i=1}^{n} |x_i| = \|\ x \|_1.$$ Then, using the Cauchy–Schwarz inequality we get for all $x\in\mathbb{R}^n$: $$\Vert x\Vert_1= \sum\limits_{i=1}^n|x_i|= \sum\limits_{i=1}^n|x_i|\cdot 1\leq \left(\sum\limits_{i=1}^n|x_i|^2\right)^{1/2}\left(\sum\limits_{i=1}^n 1^2\right)^{1/2}= \sqrt{n}\Vert x\Vert_2,$$ – Dragonite Mar 19 '18 at 12:50
• @Dragonite it is not clear how you get $\sqrt{ \sum_{i=1}^{n} | x_i |^{2} } \leq \sum_{i=1}^{n} \sqrt{ | x_ i |^{2} }$. Could you please offer more details? – johnny09 Apr 20 at 23:42

The inequality $||x||_1 \leq \sqrt{n} ||x||_2$ is a consequence of Cauchy-Schwarz. To see this

$$\sqrt{n} ||x||_2 =\sqrt{1+1+\cdots+1}\sqrt{\sum_{i} x_i^2 }\geq ||x||_1$$

For the first, the function $f(x)=\sqrt{x}$ is concave and $f(0)=0$, hence $f$ is subadditive

Therefore $f(\sum_{i} x_i^2 )\leq \sum_{i} f(x_i^2) =||x||_1$

Hint: Bound $\left \lVert x\right \rVert_2$ by $\left \lVert x'\right \rVert_2$ where $x'$ is the vector with all its components equal to the maximum of the components of $x$.