Skip to main content

Subsection 1.3.7 Equivalence of matrix norms

Homework 1.3.7.1.

Fill out the following table:

\begin{equation*} \begin{array}{| c | c | c | c | c |} \hline A \amp \| A \|_1 \amp \| A \|_\infty \amp \| A \|_F \amp \| A \|_2 \\ \hline \left( \begin{array}{r r r} 1 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \\ \end{array} \right) \amp \amp \amp \amp \\ \hline \left( \begin{array}{r r r} 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \\ \end{array} \right) \amp \amp \amp \amp \\ \hline \left( \begin{array}{r r r} 0 \amp 1 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 1 \amp 0 \\ \end{array} \right) \amp \amp \amp \amp \\ \hline \end{array} \end{equation*}
Hint

For the second and third, you may want to use Homework 1.3.5.2 when computing the 2-norm.

Solution
\begin{equation*} \begin{array}{| c | c | c | c | c |} \hline A \amp \| A \|_1 \amp \| A \|_\infty \amp \| A \|_F \amp \| A \|_2 \\ \hline \left( \begin{array}{r r r} 1 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \\ \end{array} \right) \amp 1 \amp 1 \amp \sqrt{3} \amp 1 \\ \hline \left( \begin{array}{r r r} 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \\ \end{array} \right) \amp 4 \amp 3 \amp 2\sqrt{3} \amp 2 \sqrt 3 \\ \hline \left( \begin{array}{r r r} 0 \amp 1 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 1 \amp 0 \\ \end{array} \right) \amp 3 \amp 1 \amp \sqrt{3} \amp \sqrt{3} \\ \hline \end{array} \end{equation*}

To compute the 2-norm of \(I \text{,}\) notice that

\begin{equation*} \| I \|_2 = \max_{\vert x \vert_2 = 1} \| I x \|_2 = \max_{\vert x \vert_2 = 1} \| x \|_2 = 1. \end{equation*}

Next, notice that

\begin{equation*} \left( \begin{array}{r r r} 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \\ \end{array} \right) = \left( \begin{array}{r} 1 \\ 1 \\ 1 \\ 1 \end{array} \right) \left( \begin{array}{r r r} 1 \amp 1 \amp 1 \end{array} \right) . \end{equation*}

and

\begin{equation*} \left( \begin{array}{r r r} 0 \amp 1 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 1 \amp 0 \\ \end{array} \right) = \left( \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \right) \left( \begin{array}{r r r} 0 \amp 1 \amp 0 \end{array} \right) . \end{equation*}

which allows us to invoke the result from Homework 1.3.5.2.

We saw that vector norms are equivalent in the sense that if a vector is "small" in one norm, it is "small" in all other norms, and if it is "large" in one norm, it is "large" in all other norms. The same is true for matrix norms.

The proof again builds on the fact that the supremum over a compact set is achieved and can be replaced by the maximum.

We will prove that there exists a \(\tau \) such that for all \(A \in \C^{m \times n} \)

\begin{equation*} \vert \vert \vert A \vert \vert \vert \leq \tau \| A \| \end{equation*}

leaving the rest of the proof to the reader.

Let \(A \in \C^{m \times n} \) be an arbitary matrix. W.l.o.g. assume that \(A \neq 0 \) (the zero matrix). Then

\begin{equation*} \begin{array}{l} \vert \vert \vert A \vert \vert \vert \\ ~~~ = ~~~~ \lt \mbox{ algebra } \gt \\ \frac{\vert \vert \vert A \vert \vert \vert}{\| A \|} \| A \| \\ ~~~ \le ~~~~ \lt \mbox{ definition of suppremum } \gt \\ \left( \sup_{Z \neq 0} \frac{\vert \vert \vert Z \vert \vert \vert}{\| Z \|} \right) \| A \| \\ ~~~ = ~~~~ \lt \mbox{ homogeneity } \gt \\ \left( \sup_{Z \neq 0} \vert \vert \vert \frac{Z}{\| Z \|} \vert \vert \vert \right) \| A \| \\ ~~~ = ~~~~ \lt \mbox{ change of variables } B = Z / \| Z \| \gt \\ \left( \sup_{\| B \| = 1} \vert \vert \vert B \vert \vert \vert \right) \| A \| \\ ~~~ = ~~~~ \lt \mbox{ the set }\| B \| = 1 \mbox{ is compact } \gt \\ \left( \max_{\| B \| = 1} \vert \vert \vert B \vert \vert \vert\right) \| A \| \end{array} \end{equation*}

The desired \(\tau \) can now be chosen to equal \(\max_{\| B \| = 1} \vert \vert \vert B \vert \vert \vert \text{.}\)

Remark 1.3.7.2.

The bottom line is that, modulo a constant factor, if a matrix is "small" in one norm, it is "small" in any other norm.

Homework 1.3.7.2.

Given \(A \in \mathbb C^{m \times n} \)show that \(\| A \|_2 \leq \| A \|_F \text{.}\) For what matrix is equality attained?

Hmmm, actually, this is really easy to prove once we know about the SVD... Hard to prove without it. So, this problem will be moved...

Solution

Next week, we will learn about the SVD. Let us go ahead and insert that proof here, for future reference.

Let \(A = U \Sigma V^H \) be the Singular Value Decomposition of \(A \text{,}\) where \(U \) and \(V\) are unitary and \(\Sigma = \diag{ \sigma_0, \ldots, \sigma_{\min(m,n)}} \) with \(\sigma_{0} \geq \sigma_1 \geq \ldots \geq \sigma_{\min( m,n )} \geq 0 \text{.}\) Then

\begin{equation*} \| A \|_2 = \| U \Sigma V^H \|_2 = \sigma_0 \end{equation*}

and

\begin{equation*} \| A \|_F = \| U \Sigma V^H \|_F = \| \Sigma \|_F = \sqrt{\sigma_0^2 + \ldots + \sigma_{\min( m,n )}^2 }. \end{equation*}

Hence, \(\| A \|_2 \leq \| A \|_F \text{.}\)

Homework 1.3.7.3.

Let \(A \in \mathbb C^{m \times n} \text{.}\) The following table summarizes the equivalence of various matrix norms:

\begin{equation*} \begin{array}{c | c | c | c } \amp \| A \|_1 \leq \sqrt m \| A \|_2 \amp {\color{black} {\| A \|_1 \leq m \| A \|_\infty}} \amp {\color{black} {\| A \|_1 \leq \sqrt m \| A \|_F}} \\ \hline \| A \|_2 \leq \sqrt n \| A \|_1 \amp \amp \| A \|_2 \leq \sqrt m \| A \|_\infty \amp \| A \|_2 \leq \| A \|_F \\ \hline \| A \|_\infty \leq n \| A \|_1 \amp \| A \|_\infty \leq \sqrt n \| A \|_2 \amp \amp \| A \|_\infty \leq \sqrt n \| A \|_F \\ \hline \| A \|_F \leq \sqrt n \| A \|_1 \amp \| A \|_F \leq ? \| A \|_2 \amp \| A \|_F \leq \sqrt m \| A \|_\infty \amp \end{array} \end{equation*}

For each, prove the inequality, including that it is a tight inequality for some nonzero \(A \text{.}\)

(Skip \(\| A \|_F \leq ? \| A \|_2 \text{:}\) we will revisit it in Week 2.)

Solution

  • \(\| A \|_1 \leq \sqrt{m} \| A \|_2 \text{:}\)

    \begin{equation*} \begin{array}{l} \| A \|_1 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \max_{x \neq 0} \frac{\| A x \|_1}{\| x \|_1} \\ ~~~\leq~~~~ \lt \| z \|_1 \leq \sqrt m \| z \|_2 \gt \\ \max_{x \neq 0} \frac{\sqrt{m} \| A x \|_2}{\| x \|_1} \\ ~~~\leq~~~~ \lt \| z \|_1 \geq \| z \|_2 \gt \\ \max_{x \neq 0} \frac{\sqrt{m} \| A x \|_2}{\| x \|_2} \\ ~~~=~~~~ \lt \mbox{ algebra; definition } \gt \\ \sqrt m \| A \|_2 \end{array} \end{equation*}

    Equality is attained for \(A = \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) \text{.}\)

  • \(\| A \|_1 \leq m \| A \|_\infty \text{:}\)

    \begin{equation*} \begin{array}{l} \| A \|_1 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \max_{x \neq 0} \frac{\| A x \|_1}{\| x \|_1} \\ ~~~\leq~~~~ \lt \| z \|_1 \leq m \| z \|_\infty \gt \\ \max_{x \neq 0} \frac{m \| A x \|_\infty}{\| x \|_1} \\ ~~~\leq~~~~ \lt \| z \|_1 \geq \| z \|_\infty \gt \\ \max_{x \neq 0} \frac{m \| A x \|_\infty}{\| x \|_\infty} \\ ~~~=~~~~ \lt \mbox{ algebra; definition } \gt \\ m \| A \|_\infty \end{array} \end{equation*}

    Equality is attained for \(A = \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) \text{.}\)

  • \(\| A \|_1 \leq \sqrt{m} \| A \|_F \text{:}\)

    It pays to show that \(\| A \|_2 \leq \| A \|_F \) first. Then

    \begin{equation*} \begin{array}{l} \| A \|_1 \\ ~~~\leq~~~~ \lt \mbox{ last part } \gt \\ \sqrt{m} \| A \|_2 \\ ~~~\leq~~~~ \lt \mbox{ some other part:} \| A \|_2 \leq \| A \|_F \gt \\ \sqrt{m} \| A \|_F. \end{array} \end{equation*}

    Equality is attained for \(A = \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) \text{.}\)

  • \(\| A \|_2 \leq \sqrt{n} \| A \|_1 \text{:}\)

    \begin{equation*} \begin{array}{l} \| A \|_2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \max_{x \neq 0} \frac{ \| A x \|_2 }{ \| x \|_2 } \\ ~~~\leq~~~~ \lt \| z \|_2 \leq \| z \|_1 \gt \\ \max_{x \neq 0} \frac{ \| A x \|_1 }{ \| x \|_2 } \\ ~~~\leq~~~~ \lt \sqrt{n} \| z \|_2 \geq \| z \|_1 \mbox{ when } z \mbox{ is of size } n \gt \\ \max_{x \neq 0} \frac{ \sqrt{ n } \| A x \|_1 }{ \| x \|_1 } \\ ~~~=~~~~ \lt \mbox{ algebra; definition } \gt \\ \sqrt{n} \| A \|_1. \end{array} \end{equation*}

    Equality is attained for \(A = \left( \begin{array}{c| c | c | c} 1 \amp 1 \amp \cdots \amp 1 \end{array} \right) \text{.}\)

  • \(\| A \|_2 \leq \sqrt{m} \| A \|_\infty \text{:}\)

    \begin{equation*} \begin{array}{l} \| A \|_2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \max_{x \neq 0} \frac{ \| A x \|_2 }{ \| x \|_2 } \\ ~~~\leq~~~~ \lt \| z \|_2 \leq \sqrt m \| z \|_\infty \gt \\ \max_{x \neq 0} \frac{ \sqrt m \| A x \|_\infty }{ \| x \|_2 } \\ ~~~\leq~~~~ \lt \| z \|_2 \geq \| z \|_\infty \gt \\ \max_{x \neq 0} \frac{ \sqrt{ m } \| A x \|_\infty }{ \| x \|_\infty } \\ ~~~=~~~~ \lt \mbox{ algebra; definition } \gt \\ \sqrt{m} \| A \|_\infty. \end{array} \end{equation*}

    Equality is attained for \(A = \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) \text{.}\)

  • \(\| A \|_2 \leq \| A \|_F \text{:}\)

    (See Homework 1.3.7.2, which requires the SVD, as mentioned...)

  • Please share more solutions!

login