Equivalence of Two Norm and Infinity Norm
How could you show that:
$$\|x\|_\infty \le \|x\|_2 \le \sqrt{n} \|x\|_\infty. $$
I was able to show the left hand side but got stuck showing the right hand side. What would be the best way to approach it?
For the LHS: $$\|x_j\|_\infty = \max|x_j| \le \sqrt{\sum_i {x_i^2}} = \|x\|_2 $$.
$\endgroup$ 22 Answers
$\begingroup$For the RHS (since, for all $i$, $|x_i|\leq \sup_j |x_j|:=\|x\|_{\infty} \ \Rightarrow \ x_i^2 \leq \|x\|_{\infty}^2$) : \begin{align*} \|x\|_2=\sqrt{\sum_i x_i^2}& \leq \sqrt{\sum_i \|x\|_{\infty}^2} \\ & =\sqrt{n \|x\|_{\infty}^2}=\sqrt{n} \|x\|_{\infty} \end{align*}
$\endgroup$ 1 $\begingroup$Not really an answer, but too long for a comment
The proof of your LHS is not correct. Given a vector $x = (x_1, \ldots, x_n)$, we have the following definitions:$$\|x\|_\infty = \max \{|x_i|\}$$and $$\|x\|_2 = \sqrt{\sum x_i^2} = \sqrt{\sum |x_i|^2}.$$Hence we find that $$\|x\|_\infty^2 \leq \sum |x_i|^2 = \|x\|_2^2.$$The RHS is proven in a similar way, as has been shown in other answers.
$\endgroup$ 2
