## Subsection1.2.6Equivalence of vector norms

###### Homework1.2.6.1.

Fill out the following table:

\begin{equation*} \begin{array}{| c | c | c | c |} \hline x \amp \| x \|_1 \amp \| x \|_\infty \amp \| x \|_2 \\ \hline \left( \begin{array}{r} 1 \\ 0 \\ 0 \end{array} \right) \amp \amp \amp \\ \hline \left( \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \right) \amp \amp \amp \\ \hline \left( \begin{array}{r} 1 \\ -2 \\ -1 \end{array} \right) \amp \amp \amp \\ \hline \end{array} \end{equation*}
Solution
\begin{equation*} \begin{array}{| c | c | c | c |} \hline x \amp \| x \|_1 \amp \| x \|_\infty \amp \| x \|_2 \\ \hline \left( \begin{array}{r} 1 \\ 0 \\ 0 \end{array} \right) \amp 1 \amp 1 \amp 1 \\ \hline \left( \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \right) \amp 3 \amp 1 \amp \sqrt{3} \\ \hline \left( \begin{array}{r} 1 \\ -2 \\ -1 \end{array} \right) \amp 4 \amp 2 \amp \sqrt{1^2 + (-2)^2 + (-1)^2 } = \sqrt{6} \\ \hline \end{array} \end{equation*}

In this course, norms are going to be used to reason that vectors are "small" or "large". It would be unfortunate if a vector were small in one norm yet large in another norm. Fortunately, the following theorem excludes this possibility:

The proof depends on a result from real analysis (sometimes called "advanced calculus") that states that $\sup_{x \in S} f( x )$ is attained for some vector $x \in S$ as long as $f$ is continuous and $S$ is a compact (closed and bounded) set. For any norm $\| \cdot \| \text{,}$ the unit ball $\| x \| = 1$ is a compact set. When a supremum is an element in $S \text{,}$ it is called the maximum instead and $\sup_{x \in S} f( x )$ can be restated as $\max_{x \in S} f( x ) \text{.}$

Those who have not studied real analysis (which is not a prerequisite for this course) have to take this on faith. It is a result that we will use a few times in our discussion.

We prove that there exists a $\tau$ such that for all $x \in \C^m$

\begin{equation*} \vert \vert \vert x \vert \vert \vert \leq \tau \| x \|, \end{equation*}

leaving the rest of the proof as an exercise.

Let $x \in \C^m$ be an arbitary vector. W.l.o.g. assume that $x \neq 0 \text{.}$ Then

\begin{equation*} \begin{array}{l} \vert \vert \vert x \vert \vert \vert \\ ~~~ = ~~~~ \lt \mbox{ algebra} \gt \\ \frac{\vert \vert \vert x \vert \vert \vert}{\| x \|} \| x \| \\ ~~~ \le ~~~~ \lt \mbox{ algebra} \gt \\ \left( \sup_{z \neq 0} \frac{ \vert \vert \vert z \vert \vert \vert} {\| z \|} \right) \| x \| \\ ~~~ = ~~~~ \lt \mbox{ change of variables: } y = z / \| z \| \gt \\ \left( \sup_{\| y \| = 1} \vert \vert \vert y \vert \vert \vert \right) \| x \| \\ ~~~ = ~~~~ \lt \mbox{ the set }\| y \| = 1 \mbox{ is compact } \gt \\ \left( \max_{\| y \| = 1} \vert \vert \vert y \vert \vert \vert\right) \| x \| \end{array} \end{equation*}

The desired $\tau$ can now be chosen to equal $\max_{\| y \| = 1} \vert \vert \vert y \vert \vert \vert \text{.}$

###### Homework1.2.6.2.

Complete the proof of Theorem 1.2.6.1.

Solution

We need to prove that

\begin{equation*} \sigma \| x \| \leq \vert\vert\vert x \vert \vert \vert. \end{equation*}

From the first part of the proof of Theorem 1.2.6.1, we know that there exists a $\rho > 0$ such that

\begin{equation*} \| x \| \leq \rho \vert\vert\vert x \vert \vert \vert \end{equation*}

and hence

\begin{equation*} \frac{1}{\rho} \| x \| \leq \vert\vert\vert x \vert \vert \vert . \end{equation*}

We conclude that

\begin{equation*} \sigma \| x \| \leq \vert\vert\vert x \vert \vert \vert \end{equation*}

where $\sigma = 1 / \rho \text{.}$

###### Example1.2.6.2.
• Let $x \in \R^2 \text{.}$ Use the picture

to determine the constant $C$ such that $\| x \|_1 \leq C \| x \|_\infty \text{.}$ Give a vector $x$ for which $\| x \|_1 = C \| x \|_\infty \text{.}$

• For $x \in \R^2$ and the $C$ you determined in the first part of this problem, prove that $\| x \|_1 \leq C \| x \|_\infty \text{.}$

• Let $x \in \Cm \text{.}$ Extrapolate from the last part the constant $C$ such that $\| x \|_1 \leq C \| x \|_\infty$ and then prove the inequality. Give a vector $x$ for which $\| x \|_1 = C \| x \|_\infty \text{.}$

Solution
• Consider the picture

• The red square represents all vectors such that $\| x \|_\infty = 1$ and the white square represents all vectors such that $\| x \|_1 = 2 \text{.}$

• All points on or outside the red square represent vectors $y$ such that $\| y \|_\infty \ge 1 \text{.}$ Hence if $\| y \|_1 = 2$ then $\| y \|_\infty \geq 1 \text{.}$

• Now, pick any $z \neq 0 \text{.}$ Then $\left\| 2 z / \| z \|_1 \right\|_1= 2) \text{.}$ Hence

\begin{equation*} \left\| 2 z / \| z \|_1 \right\|_\infty \ge 1 \end{equation*}

which can be rewritten as

\begin{equation*} \| z \|_1 \le 2 \| z \|_\infty. \end{equation*}

Thus, $C = 2$ works.

• Now, from the picture it is clear that $x = \left( \begin{array}{c} 1 \\ 1 \end{array} \right)$ has the property that $\| x \|_1 = 2 \| x \|_\infty \text{.}$ Thus, the inequality is "tight."

• We now prove that $\| x \|_1 \leq 2 \| x \|_\infty$ for $x \in \R^2 \text{:}$

\begin{equation*} \begin{array}{l} \| x \|_1 \\ ~~~ = ~~~~ \lt \mbox{ definition} \gt \\ \vert \chi_0 \vert + \vert \chi_1 \vert \\ ~~~ \leq ~~~~ \lt \mbox{ algebra} \gt \\ \max(\vert \chi_0 \vert, \vert \chi_1 \vert ) + \max(\vert \chi_0 \vert, \vert \chi_1 \vert ) \\ ~~~ = ~~~~ \lt \mbox{ algebra} \gt \\ 2 \max(\vert \chi_0 \vert, \vert \chi_1 \vert ) \\ ~~~ = ~~~~ \lt \mbox{ definition} \gt \\ 2 \| x \|_\infty. \end{array} \end{equation*}
• From the last part we extrapolate that $\| x \|_1 \leq m \| x \|_\infty \text{.}$

\begin{equation*} \begin{array}{l} \| x \|_1 \\ ~~~ = ~~~~ \lt \mbox{ definition} \gt \\ \sum_{i=0}^{m-1} \vert \chi_i \vert \\ ~~~ \leq ~~~~ \lt \mbox{ algebra} \gt \\ \sum_{i=0}^{m-1} \left( \max_{j=0}^{m-1} \vert \chi_j \vert \right) \\ ~~~ = ~~~~ \lt \mbox{ algebra} \gt \\ m \max_{j=0}^{m-1} \vert \chi_j \vert \\ ~~~ = ~~~~ \lt \mbox{ definition} \gt \\ m \| x \|_\infty. \end{array} \end{equation*}

Equality holds (i.e., $\| x \|_1 = m \| x \|_\infty$) for $x = \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) \text{.}$

Some will be able to go straight for the general result, while others will want to seek inspiration from the picture and/or the specialized case where $x \in \R^2 \text{.}$

###### Homework1.2.6.3.

Let $x \in \Cm \text{.}$ The following table organizes the various bounds:

\begin{equation*} \begin{array}{c | c | c } \amp \| x \|_1 \leq C_{1,2} \| x \|_2 \amp {\color{black} {\| x \|_1 \leq C_{1,\infty} \| x \|_\infty}} \\ \hline \| x \|_2 \leq C_{2,1} \| x \|_1 \amp \amp \| x \|_2 \leq C_{2,\infty} \| x \|_\infty \\ \hline \| x \|_\infty \leq C_{\infty, 1} \| x \|_1 \amp \| x \|_\infty \leq C_{\infty, 2} \| x \|_2 \amp \end{array} \end{equation*}

For each, determine the constant $C_{x,y}$ and prove the inequality, including that it is a tight inequality.

Hint: look at the hint!

Hint

$\| x \|_1 \leq \sqrt{m} \| x \|_2 \text{:}$

This is the hardest one to prove. Do it last and use the following hint:

Consider $y = \left( \begin{array}{c} \chi_0 / \vert \chi_0 \vert \\ \vdots \\ \chi_{m-1} / \vert \chi_{m-1} \vert \end{array} \right)$ and employ the Cauchy-Schwarz inequality.

(How do you modify this hint to cover the case where one or more elements equal zero?)

Solution 1 $\| x \|_1 \leq C_{1,2} \| x \|_2$

$\| x \|_1 \leq \sqrt{m} \| x \|_2 \text{:}$

Consider $y = \left( \begin{array}{c} \psi_0 \\ \vdots \\ \psi_{m-1} \end{array} \right) = \left( \begin{array}{c} \chi_0 / \vert \chi_0 \vert \\ \vdots \\ \chi_{m-1} / \vert \chi_{m-1} \vert \end{array} \right).$ Then

\begin{equation*} \vert x^H y \vert = \left\vert \sum_{i=0}^{m-1} \overline{\chi_i} \chi_i / \vert \chi_i \vert \right\vert = \left\vert \sum_{i=0}^{m-1} \vert \chi_i \vert^2 / \vert \chi_i \vert \right\vert = \left\vert \sum_{i=0}^{m-1} \vert \chi_i \vert \right\vert = \| x \|_1. \end{equation*}

We also notice that $\| y \|_2 = \sqrt{m} \text{.}$

From the Cauchy-Swartz inequality we know that

\begin{equation*} \| x \|_1 = \vert x^H y \vert \leq \| x \|_2 \| y \|_2 = \sqrt{m} \| x \|_2. \end{equation*}

The problem with the above argument is that one of more $\chi_i$ may equal zero. The argument can be fixed by choosing

\begin{equation*} \psi_i = \left\{ \begin{array}{ll} \chi_i / \vert \chi_i \vert \amp ~ \mbox{if } \chi_i \neq 0 \\ 0 \amp \mbox{otherwise} \end{array} \right. \end{equation*}

or

\begin{equation*} \psi_i = \left\{ \begin{array}{ll} \chi_i / \vert \chi_i \vert \amp ~ \mbox{if } \chi_i \neq 0 \\ 1 \amp \mbox{otherwise.} \end{array} \right. \end{equation*}

To demonstrate that equality is attained for at least one non-zero vector, we choose

\begin{equation*} x = \left( \begin{array}{c} 1 \\ \vdots \\ 1 \end{array} \right) \end{equation*}

then $\| x \|_1 = m$ and $\| x \|_2 = \sqrt{m}$ so that $\| x \|_1 = \sqrt{m} \| x \|_2 \text{.}$

Solution 2 $\| x \|_1 \leq C_{1,\infty} \| x \|_\infty$

$\| x \|_1 \leq m \| x \|_\infty \text{:}$

See Example 1.2.6.2.

Solution 3 $\| x \|_2 \leq C_{2,1} \| x \|_1 \text{:}$

$\| x \|_2 \leq \| x \|_1 \text{:}$

\begin{equation*} \begin{array}{l} \| x \|_2^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \sum_{i=0}^{m-1} \vert \chi_i \vert^2 \\ ~~~\leq~~~~ \lt \mbox{ algebra } \gt \\ \left( \sum_{i=0}^{m-1} \vert \chi_i \vert \right)^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \| x \|_1^2. \end{array} \end{equation*}

Taking the square root of both sides yields $\| x \|_2 \leq \| x \|_1 \text{.}$

If we now choose

\begin{equation*} x = \left( \begin{array}{c} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{array} \right) \end{equation*}

then $\| x \|_2 = \| x \|_1 \text{.}$

Solution 4 $\| x \|_2 \leq C_{2,\infty} \| x \|_\infty$

$\| x \|_2 \leq \sqrt{m} \| x \|_\infty \text{:}$

\begin{equation*} \begin{array}{l} \| x \|_2^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \sum_{i=0}^{m-1} \vert \chi_i \vert^2 \\ ~~~\leq~~~~ \lt \mbox{ algebra } \gt \\ \sum_{i=0}^{m-1} \left( \max_{j=0}^{m-1} \vert \chi_j \vert \right)^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \sum_{i=0}^{m-1} \| x \|_\infty^2 \\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ m \| x \|_\infty^2. \end{array} \end{equation*}

Taking the square root of both sides yields $\| x \|_2 \leq \sqrt{m} \| x \|_\infty \text{.}$

Consider

\begin{equation*} x = \left( \begin{array}{c} 1 \\ \vdots \\ 1 \end{array} \right) \end{equation*}

then $\| x \|_2 = \sqrt{m}$ and $\| x \|_\infty = 1$ so that $\| x \|_2 = \sqrt{m} \| x \|_\infty \text{.}$

Solution 5 $\| x \|_\infty \leq C_{\infty,1} \| x \|_1 \text{:}$

$\| x \|_\infty \leq \| x \|_1 \text{:}$

\begin{equation*} \begin{array}{l} \| x \|_\infty \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \max_{i=0}^{m-1} \vert \chi_i \vert \\ ~~~\leq~~~~ \lt \mbox{ algebra } \gt \\ \sum_{i=0}^{m-1} \vert \chi_i \vert \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \| x \|_1. \end{array} \end{equation*}

Consider

\begin{equation*} x = \left( \begin{array}{c} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{array} \right) . \end{equation*}

Then $\| x \|_\infty = 1 = \| x \|_1 \text{.}$

Solution 6 $\| x \|_\infty \leq C_{\infty,2} \| x \|_2$

$\| x \|_\infty \leq \| x \|_2 \text{:}$

\begin{equation*} \begin{array}{l} \| x \|_\infty^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \left( \max_{i=0}^{m-1} \vert \chi_i \vert \right)^2\\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ \max_{i=0}^{m-1} \vert \chi_i \vert^2\\ ~~~\leq~~~~ \lt \mbox{ algebra } \gt \\ \sum_{i=0}^{m-1} \vert \chi_i \vert^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \| x \|_2^2. \end{array} \end{equation*}

Taking the square root of both sides yields $\| x \|_\infty \leq \| x \|_2 \text{.}$

Consider

\begin{equation*} x = \left( \begin{array}{c} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{array} \right) . \end{equation*}

Then $\| x \|_\infty = 1 = \| x \|_2 \text{.}$

Solution 7 Table of constants
\begin{equation*} \begin{array}{c | c | c } \amp \| x \|_1 \leq \sqrt{m} \| x \|_2 \amp {\color{black} {\| x \|_1 \leq m \| x \|_\infty}} \\ \hline \| x \|_2 \leq \| x \|_1 \amp \amp \| x \|_2 \leq \sqrt{m} \| x \|_\infty \\ \hline \| x \|_\infty \leq \| x \|_1 \amp \| x \|_\infty \leq \| x \|_2 \amp \end{array} \end{equation*}
###### Remark1.2.6.3.

The bottom line is that, modulo a constant factor, if a vector is "small" in one norm, it is "small" in all other norms. If it is "large" in one norm, it is "large" in all other norms.