ALAFF The matrix 2-norm

Subsection 1.3.5 The matrix 2-norm

Let us instantiate the definition of the vector \(p\) norm for the case where \(p=2 \text{,}\) giving us a matrix norm induced by the vector 2-norm or Euclidean norm:

Definition 1.3.5.1. Matrix 2-norm.

Define the matrix 2-norm \(\| \cdot \|_2 : \C^{m \times n} \rightarrow \mathbb R \) by

\begin{equation*} \| A \|_2 = \max_{x \neq 0} \frac{\| A x \|_2}{\| x \|_2} = \max_{\| x \|_2 = 1} \| A x \|_2. \end{equation*}

Remark 1.3.5.2.

The problem with the matrix 2-norm is that it is hard to compute. At some point later in this course, you will find out that if \(A \) is a Hermitian matrix (\(A = A^H \)), then \(\| A \|_2 = \vert \lambda_0 \vert \text{,}\) where \(\lambda_0 \) equals the eigenvalue of \(A \) that is largest in magnitude. You may recall from your prior linear algebra experience that computing eigenvalues involves computing the roots of polynomials, and for polynomials of degree three or greater, this is a nontrivial task. We will see that the matrix 2-norm plays an important role in the theory of linear algebra, but less so in practical computation.

Example 1.3.5.3.

Show that

\begin{equation*} \left\| \left( \begin{array}{c c} \delta_0 \amp 0 \\ 0 \amp \delta_1 \end{array} \right) \right\|_2 = \max( \vert \delta_0 \vert, \vert \delta_1 \vert ). \end{equation*}

Solution

[slides (PDF)] [LaTeX source]

Remark 1.3.5.4.

The proof of the last example builds on a general principle: Showing that \(\max_{x \in D} f(x) = \alpha \) for some function \(f: D \rightarrow R \) can be broken down into showing that both

\begin{equation*} \max_{x \in D} f(x) \leq \alpha \end{equation*}

and

\begin{equation*} \max_{x \in D} f(x) \geq \alpha. \end{equation*}

In turn, showing that \(\max_{x \in D} f(x) \geq \alpha \) can often be accomplished by showing that there exists a vector \(y \in D \) such that \(f(y) = \alpha \) since then

\begin{equation*} \alpha = f( y ) \leq \max_{x \in D} f(x) . \end{equation*}

We will use this technique in future proofs involving matrix norms.

Homework 1.3.5.1.

Let \(D \in \mathbb C^{m \times m} \) be a diagonal matrix with diagonal entries \(\delta_0, \ldots , \delta_{m-1} \text{.}\) Show that

\begin{equation*} \| D \|_2 = \max_{j=0}^{m-1} \vert \delta_j \vert. \end{equation*}

Solution

First, we show that \(\| D \|_2 = \max_{\| x \|_2 = 1} \| D x \|_2 \leq \max_{i=0}^{m-1} \vert \delta_i \vert \text{:}\)

\begin{equation*} \begin{array}{l} \| D \|_2^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \max_{\| x \|_2 = 1} \| D x \|_2^2 \\ ~~~=~~~~ \lt \mbox{ diagonal vector multiplication } \gt \\ \max_{\| x \|_2 = 1} \left\| \left( \begin{array}{c} \delta_0 \chi_0 \\ \vdots \\ \delta_{m-1} \chi_{m-1} \end{array}\right) \right\|_2^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \max_{\| x \|_2 = 1} \sum_{i=0}^{m-1} \vert \delta_i \chi_i \vert^2 \\ ~~~=~~~~ \lt \mbox{ homogeneity } \gt \\ \max_{\| x \|_2 = 1} \sum_{i=0}^{m-1} \vert \delta_i \vert^2 \vert \chi_i \vert^2 \\ ~~~\leq~~~~ \lt \mbox{ algebra } \gt \\ \max_{\| x \|_2 = 1} \sum_{i=0}^{m-1} \left[ \max_{j=0}^{m-1} \vert \delta_j \vert \right]^2 \vert \chi_i \vert^2 \\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ \left[ \max_{j=0}^{m-1} \vert \delta_j \vert \right]^2 \max_{\| x \|_2 = 1} \sum_{i=0}^{m-1} \vert \chi_i \vert^2 \\ ~~~=~~~~ \lt \| x \|_2 = 1 \gt \\ \left[ \max_{j=0}^{m-1} \vert \delta_j \vert \right]^2. \end{array} \end{equation*}

Next, we show that there is a vector \(y \) with \(\| y \|_2 = 1 \) such that \(\| D y \|_2 = \max_{i=0}^{m-1} \vert \delta_i \vert \text{:}\)

Let \(j \) be such that \(\vert \delta_j \vert = \max_{i=0}^{m-1} \vert \delta_i \vert \) and choose \(y = e_j \text{.}\) Then

\begin{equation*} \begin{array}{l} \| D y \|_2 \\ ~~~=~~~~ \lt y = e_j \gt \\ \| D e_j \|_2 \\ ~~~=~~~~ \lt D = \diag{ \delta_0, \ldots , \delta_{m-1} } \gt \\ \| \delta_j e_j \|_2 \\ ~~~=~~~~ \lt \mbox{ homogeneity } \gt \\ \vert \delta_j \vert \| e_j \|_2 \\ ~~~=~~~~ \lt \| e_j |_2 = 1 \gt \\ \vert \delta_j \vert \\ ~~~=~~~~ \lt \mbox{ choice of } j \gt \\ \max_{i=0}^{m-1} \vert \delta_i \vert \end{array} \end{equation*}

Hence \(\| D \|_2 = \max_{j=0}^{m-1} \vert \delta_j \vert \text{.}\)

Homework 1.3.5.2.

Let \(y \in \C^m \) and \(x \in \C^n \text{.}\)

ALWAYS/SOMETIMES/NEVER: \(\| y x^H \|_2 = \| y \|_2 \| x \|_2 \text{.}\)

Hint

Prove that \(\| y x^H \|_2 \leq \| y \|_2 \| x \|_2 \) and that there exists a vector \(z \) so that \(\frac{\| y x^H z \|_2}{\| z \|_2} =\| y \|_2 \| x \|_2 \text{.}\)

Answer

ALWAYS

Now prove it!

Solution

W.l.o.g. assume that \(x \neq 0 \text{.}\)

We know by the Cauchy-Schwarz inequality that \(\vert x^H z \vert \leq \| x \|_2 \| z \|_2 \text{.}\) Hence

\begin{equation*} \begin{array}{l} \| y x^H \|_2 \\ ~~~=~~~~ \lt \mbox{ definition} \gt \\ \max_{\| z \|_2 = 1 } \| y x^H z \|_2 \\ ~~~=~~~~ \lt \| \cdot \|_2 \mbox{ ~is~homogenius} \gt \\ \max_{\| z \|_2 =1 }\vert x^H z \vert \| y \|_2 \\ ~~~\leq~~~ \lt \mbox{ Cauchy-Schwarz~inequality} \gt \\ \max_{\| z \|_2 =1 } \| x \|_2 \| z \|_2 \|y \|_2 \\ ~~~=~~~~ \lt \| z \|_2 = 1 \gt \\ \| x \|_2 \|y\|_2 . \end{array} \end{equation*}

But also

\begin{equation*} \begin{array}{l} \| y x^H \|_2 \\ ~~~=~~~~ \lt \mbox{ definition} \gt \\ \max_{ z \neq 0 } \| y x^H z \|_2 / \| z \|_2 \\ ~~~\geq~~~~ \lt \mbox{ specific~} z \gt \\ \| y x^H x \|_2 / \| x \|_2 \\ ~~~=~~~~ \lt x^H x = \| x \|_2^2; \mbox{ homogeneity} \gt \\ \| x \|_2^2 \| y \|_2 / \| x \|_2 \\ ~~~=~~~~ \lt \mbox{ algebra} \gt \\ \| y \|_2 \| x \|_2. \end{array} \end{equation*}

Hence

\begin{equation*} \| y x^H \|_2 = \| y \|_2 \| x \|_2. \end{equation*}

Homework 1.3.5.3.

Let \(A \in \mathbb C^{m \times n} \) and \(a_j \) its column indexed with \(j \text{.}\) ALWAYS/SOMETIMES/NEVER: \(\| a_j \|_2 \leq \| A \|_2 \text{.}\)

Hint

What vector has the property that \(a_j = A x \text{?}\)

Answer

ALWAYS.

Now prove it!

Solution

\begin{equation*} \begin{array}{l} \| a_j \|_2 \\ ~~~=~~~~\\ \| A e_j \|_2 \\ ~~~\leq~~~ \\ \max_{\| x \|_2 = 1} \| A x \|_2 \\ ~~~ = ~~~ \\ \| A \|_2. \end{array} \end{equation*}

Homework 1.3.5.4.

Let \(A \in \mathbb C^{m \times n} \text{.}\) Prove that

\(\| A \|_2 = \max_{\| x \|_2=\| y \|_2=1} \vert y^H A x \vert \text{.}\)
\(\| A^H \|_2 = \| A \|_2 \text{.}\)
\(\| A^H A \|_2 = \| A \|_2^2 \text{.}\)

Hint

Proving \(\| A \|_2 = \max_{\| x \|_2=\| y \|_2=1} \vert y^H A x \vert \) requires you to invoke the Cauchy-Schwarz inequality from Theorem 1.2.3.3.

Solution

\(\| A \|_2 = \max_{\| x \|_2=\| y \|_2=1} \vert y^H A x \vert \text{:}\)

\begin{equation*} \begin{array}{l} \max_{\| x \|_2=\| y \|_2=1} \vert y^H A x \vert \\ ~~~\leq~~~~ \lt \mbox{ Cauchy-Schwarz } \gt \\ \max_{\| x \|_2=\| y \|_2=1} \| y \|_2 \| A x \|_2 \\ ~~~=~~~~ \lt \| y \|_2 = 1 \gt \\ \max_{\| x \|_2=1} \| A x \|_2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \| A \|_2. \end{array} \end{equation*}

Also, we know there exists \(x \) with \(\| x \|_2 = 1 \) such that \(\| A \|_2 = \| A x \|_2 \text{.}\) Let \(y = A x / \| A x \|_2 \text{.}\) Then

\begin{equation*} \begin{array}{l} \vert y^H A x \vert \\ ~~~=~~~~ \lt \mbox{ instantiate } \gt \\ \left\vert \frac{( A x )^H ( A x )}{\| A x \|_2} \right\vert \\ ~~~=~~~~ \lt z^H z = \| z \|_2^2 \gt \\ \left\vert \frac{\| A x \|_2^2}{\| A x \|_2} \right\vert \\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ \| A x \|_2 \\ ~~~=~~~~ \lt x \mbox{ was chosen so that } \| A x \|_2 = \| A \|_2 \gt \\ \| A \|_2 \end{array} \end{equation*}

Hence the bound is attained. We conclude that \(\| A \|_2 = \max_{\| x \|_2=\| y \|_2=1} \vert y^H A x \vert \text{.}\)
\(\| A^H \|_2 = \| A \|_2 \text{:}\)

\begin{equation*} \begin{array}{l} \| A^H \|_2 \\ ~~~=~~~~ \lt \mbox{ first part of homework } \gt \\ \max_{\| x \|_2=\| y \|_2=1} \vert y^H A^H x \vert \\ ~~~=~~~~ \lt \vert \overline \alpha \vert = \vert \alpha \vert \gt \\ \max_{\| x \|_2=\| y \|_2=1} \vert x^H A y \vert \\ ~~~=~~~~ \lt \mbox{ first part of homework } \gt \\ \| A \|_2 . \end{array} \end{equation*}
\(\| A^H A \|_2 = \| A \|_2^2 \text{:}\)

\begin{equation*} \begin{array}{l} \| A^H A \|_2 \\ ~~~=~~~~ \lt \mbox{ first part of homework } \gt \\ \max_{\| x \|_2=\| y \|_2=1} \vert y^H A^H A x \vert \\ ~~~\ge~~~~ \lt \mbox{ restricts choices of } y \gt \\ \max_{\| x \|_2=1} \vert x^H A^H A x \vert \\ ~~~=~~~~ \lt z^H z = \| z \|_2^2 \gt \\ \max_{\| x \|_2=1} \| A x \|_2^2 \\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ \left( \max_{\| x \|_2=1} \| A x \|_2 \right)^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \| A \|_2^2. \end{array} \end{equation*}

So, \(\| A^H A \|_2 \ge \| A \|_2^2 \text{.}\)

Now, let's show that \(\| A^H A \|_2 \leq \| A \|_2^2 \text{.}\) This would be trivial if we had already discussed the fact that \(\| \cdots \|_2 \) is a submultiplicative norm (which we will in a future unit). But let's do it from scratch. First, we show that \(\| A x \|_2 \leq \| A \|_2 \| x \|_2 \) for all (appropriately sized) matrices \(A \) and \(x \text{:}\)

\begin{equation*} \begin{array}{l} \| A x \|_2 \\ ~~~ = ~~~ \lt \mbox{ norms are homogeneus } \gt \\ \| A \frac{x}{\| x \|_2} \|_2 \| x \|_2\\ ~~~ \le ~~~ \lt \mbox{ algebra } \gt \\ \max_{\| y \|_2 = 1 } \| A y \|_2 \| x \|_2 \\ ~~~ = ~~~ \lt \mbox{ definition of 2-norm } \\ \| A \|_2 \| x \|_2. \end{array} \end{equation*}

With this, we can then show that

\begin{equation*} \begin{array}{l} \| A^H A \|_2 \\ ~~~ = ~~~~ \lt \mbox{ definition of 2-norm } \gt \\ \max_{\| x \|_2 = 1} \| A^H A x \|_2 \\ ~~~ \leq ~~~~ \lt \| Az \|_2 \leq \| A \|_2 \| z \|_2 \gt \\ \max_{\| x \|_2 = 1} ( \| A^H \|_2 \| A x \|_2 ) \\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ \| A^H \|_2 \max_{\| x \|_2 = 1} \| A x \|_2 ) \\ ~~~= ~~~~ \lt \mbox{ definition of 2-norm } \gt \\ \| A^H \|_2 \| A \|_2 \\ ~~~=~~~~ \lt \| A^H \|_2 = \| A \| \gt \\ \| A \|_2^2 \end{array} \end{equation*}

Alternatively, as suggested by one of the learners in the course, we can use the Cauchy-Schwarz inequality:

\begin{equation*} \begin{array}{l} \| A^H A \|_2 \\ ~~~ = ~~~~ \lt \mbox{ part (a) of this homework } \gt \\ \max_{\| x \|_2 = \| y \|_2 = 1} \vert x^H A^H A y \vert \\ ~~~ = ~~~~ \lt \mbox{ simple manipulation } \gt \\ \max_{\| x \|_2 = \| y \|_2 = 1} \vert ( A x )^H A y \vert \\ ~~~\leq ~~~~ \lt \mbox{ Cauchy-Schwarz inequality } \gt \\ \max_{\| x \|_2 = \| y \|_2 = 1} \| A x \|_2 \| A y \|_2 \\ ~~~ = ~~~~ \lt \mbox{ algebra } \gt \\ \max_{\| x \|_2 = 1} \| A x \|_2 \max_{\| y \|_2 = 1} \| A y \|_2 \\ ~~~ = ~~~~ \lt \mbox{ definition } \gt \\ \| A \|_2 \| A \|_2 \\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ \| A \|_2^2 \end{array} \end{equation*}

Homework 1.3.5.5.

Partition \(A = \left( \begin{array}{c | c | c} A_{0,0} \amp \cdots \amp A_{0,N-1} \\ \hline \vdots \amp \amp \vdots \\ \hline A_{M-1,0} \amp \cdots \amp A_{M-1,N-1} \end{array} \right). \)

ALWAYS/SOMETIMES/NEVER: \(\| A_{i,j} \|_2 \leq \| A \|_2 \text{.}\)

Hint

Using Homework 1.3.5.4 choose \(v_j \) and \(w_i \) such that \(\| A_{i,j} \|_2 = \vert w_i^H A_{i,j} v_j \vert \text{.}\)

Solution

Choose \(v_j \) and \(w_i \) such that \(\| A_{i,j} \|_2 = \vert w_i^H A_{i,j} v_j \vert \text{.}\) Next, choose \(v \) and \(w \) such that

\begin{equation*} v = \left( \begin{array}{c} 0 \\ \hline \vdots \\ \hline 0 \\ \hline v_j \\ \hline 0 \\ \hline \vdots \\ \hline 0 \end{array} \right), \quad w = \left( \begin{array}{c} 0 \\ \hline \vdots \\ \hline 0 \\ \hline w_i \\ \hline 0 \\ \hline \vdots \\ \hline 0 \end{array} \right) . \end{equation*}

You can check (using partitioned multiplication and the last homework) that \(w^H A v = w_i^H A_{i,j} v_j \text{.}\) Then, by Homework 1.3.5.4

\begin{equation*} \begin{array}{l} \| A \|_2 \\ ~~~=~~~~ \lt \mbox{ last homework } \gt \\ \max_{\| x \|_2=\| y \|_2=1} \vert y^H A x \vert \\ ~~~ \geq ~~~~ \lt w \mbox{ and } v \mbox{ are specific vectors }\gt \\ \vert w^H A v \vert \\ ~~~=~~~~ \lt \mbox{ partitioned multiplication } \gt \\ \vert w_i^H A_{i,j} v_j \vert \\ ~~~=~~~~ \lt \mbox{ how } w_i \mbox{ and } v_j \mbox{ were chosen } \gt \\ \| A_{i,j} \|_2. \end{array} \end{equation*}