Theorem: For all \(\x \in \real^d\),

\[\norm{\x}_2 \leq \norm{\x}_1 \leq \sqrt{d}\norm{\x}_2\]

Proof:

i)

\[\begin{alignat*}{2} \norm{\x}_2^2 &= \sum_i x_i^2 &\hspace{8em}& \\ &\leq \sum_i \abs{x_i} \sum_i \abs{x_i} && \sum_i \abs{x_i} \sum_i \abs{x_i} = \sum_i x_i^2 + \sum_{i \neq j} \abs{x_i}\abs{x_j} \\ &= \norm{\x}_1\norm{\x}_1 \\ \implies & \norm{\x}_2 \leq \norm{\x}_1 && \sqrt{\cdot} \text{ is monotone} \end{alignat*}\]

ii)

\[\begin{alignat*}{2} \norm{\x}_1 &= \a \Tr \b &\hspace{8em}& \text{Let } a_i = 1, b_i = \abs{x_i}\\ &\leq \norm{\a}_2 \norm{\b}_2 && \href{cauchy-schwarz.html}{\text{Cauchy-Schwarz}} \\ &= \sqrt{d}\norm{\x}_2 \end{alignat*}\]