## Subsection1.3.6Computing the matrix 1-norm and $\infty$-norm

The matrix 1-norm and matrix $\infty$-norm are of great importance because, unlike the matrix 2-norm, they are easy and relatively cheap to compute.. The following exercises show how to practically compute the matrix 1-norm and $\infty$-norm.

###### Homework1.3.6.1.

Let $A \in \C^{m \times n}$ and partition $A = \left( \begin{array}{c | c | c | c} a_0 \amp a_1 \amp \cdots \amp a_{n-1} \end{array} \right) \text{.}$ ALWAYS/SOMETIMES/NEVER: $\| A \|_1 = \max_{0 \leq j \lt n} \| a_j \|_1.$

Hint

Prove it for the real valued case first.

ALWAYS

Solution

Let $J$ be chosen so that $\max_{0 \leq j \lt n} \| a_j \|_1= \| a_{J} \|_1 \text{.}$ Then

\begin{equation*} \begin{array}{l} \| A \|_1 \\ ~~~ = ~~~~ \lt \mbox{ definition} \gt \\ \max_{\|x\|_1 = 1} \| A x \|_1 \\ ~~~=~~~~ \lt \mbox{ expose the columns of } A \mbox{ ~and~elements~of~} x \gt \\ \max_{\|x\|_1 = 1} \left\| \left( \begin{array}{c | c | c | c} a_0 \amp a_1 \amp \cdots \amp a_{n-1} \end{array} \right) \left( \begin{array}{c} \chi_0 \\ \chi_1 \\ \vdots \\ \chi_{n-1} \end{array} \right) \right\|_1 \\ ~~~=~~~~ \lt \mbox{ definition~of~matrix-vector~multiplication} \gt \\ \max_{\|x\|_1 = 1} \| \chi_0 a_0 + \chi_1 a_1 + \cdots + \chi_{n-1} a_{n-1} \|_1 \\ ~~~\leq~~~~ \lt \mbox{ triangle inequality } \gt \\ \max_{\|x\|_1 = 1} \left( \| \chi_0 a_0 \|_1 + \| \chi_1 a_1 \|_1 + \cdots + \| \chi_{n-1} a_{n-1} \|_1 \right) \\ ~~~=~~~~ \lt \mbox{ homogeneity } \gt \\ \max_{\|x\|_1 = 1} \left( \vert \chi_0 \vert \| a_0 \|_1 + \vert \chi_1 \vert \| a_1 \|_1 + \cdots + \vert \chi_{n-1} \vert \| a_{n-1} \|_1 \right) \\ ~~~\leq ~~~~ \lt \mbox{ choice of } a_J \gt \\ \max_{\|x\|_1 = 1} \left( \vert \chi_0 \vert \| a_{J} \|_1 + \vert \chi_1 \vert \| a_{J} \|_1 + \cdots + \vert \chi_{n-1} \vert \| a_{J} \|_1 \right) \\ ~~~=~~~~ \lt \mbox{ factor out } \| a_J \|_1 \gt \\ \max_{\|x\|_1 = 1} \left( \vert \chi_0 \vert + \vert \chi_1 \vert + \cdots + \vert \chi_{n-1} \vert \right) \| a_{J} \|_1 \\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ \| a_{J} \|_1. \end{array} \end{equation*}

Also,

\begin{equation*} \begin{array}{l} \| a_{J} \|_1 \\ ~~~ = ~~~~ \lt e_J \mbox{ picks out column } J \gt \\ \| A e_{J} \|_1 \\ ~~~ \leq ~~~~ \lt e_J \mbox{ is a specific choice of } x \gt \\ \max_{\|x\|_1 = 1} \| A x \|_1 . \end{array} \end{equation*}

Hence

\begin{equation*} \| a_{J} \|_1 \leq \max_{\|x\|_1 = 1} \| A x \|_1 \leq \| a_{J} \|_1 \end{equation*}

which implies that

\begin{equation*} \max_{\|x\|_1 = 1} \| A x \|_1 = \| a_{J} \|_1 = \max_{0 \leq j \lt n} \| a_j \|_1. \end{equation*}
###### Homework1.3.6.2.

Let $A \in \C^{m \times n}$ and partition $A = \left( \begin{array}{c} \widetilde a_0^T \\ \hline \widetilde a_1^T \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T \end{array} \right) \text{.}$

ALWAYS/SOMETIMES/NEVER:

\begin{equation*} \| A \|_\infty = \max_{0 \leq i \lt m} \| \widetilde a_i \|_1 ( = \max_{0 \leq i \lt m} \left( \vert \alpha_{i,0} \vert + \vert \alpha_{i,1} \vert + \cdots + \vert \alpha_{i,n-1} \vert \right) ) \end{equation*}

Notice that in this exercise $\widetilde a_i$ is really $( \widetilde a_i^T )^T$ since $\widetilde a_i^T$ is the label for the $i$th row of matrix $A \text{.}$

Hint

Prove it for the real valued case first.

ALWAYS

Solution

Partition $A = \left( \begin{array}{c} \widetilde a_0^T \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T \end{array} \right) \text{.}$ Then

\begin{equation*} \begin{array}{l} \| A \|_\infty \\ ~~~=~~~~ \lt \mbox{ definition} \gt \\ \max_{\| x \|_\infty = 1} \| A x \|_\infty \\ ~~~=~~~~ \lt \mbox{ expose~rows} \gt \\ \max_{\| x \|_\infty = 1} \left\| \left( \begin{array}{c} \widetilde a_0^T \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T \end{array} \right) x \right\|_\infty \\ ~~~=~~~~ \lt \mbox{ matrix-vector multiplication} \gt \\ \max_{\| x \|_\infty = 1} \left\| \left( \begin{array}{c} \widetilde a_0^T x \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T x \end{array} \right) \right\|_\infty \\ ~~~=~~~~\lt \mbox{ definition of } \| \cdots \|_\infty \gt \\ \max_{\| x \|_\infty = 1} \left( \max_{0 \leq i \lt m} \vert \widetilde a_i^T x \vert \right) \\ ~~~=~~~~ \lt \mbox{ expose } \widetilde a_i^T x \gt \\ \max_{\| x \|_\infty = 1} \max_{0 \leq i \lt m} \vert \sum_{p=0}^{n-1} \alpha_{i,p} \chi_p \vert \\ ~~~\leq~~~~\lt \mbox{ triangle inequality } \gt \\ \max_{\| x \|_\infty = 1} \max_{0 \leq i \lt m} \sum_{p=0}^{n-1} \vert \alpha_{i,p} \chi_p \vert \\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ \max_{\| x \|_\infty = 1} \max_{0 \leq i \lt m} \sum_{p=0}^{n-1} ( \vert \alpha_{i,p} \vert \vert \chi_p \vert ) \\ ~~~\leq~~~~ \lt \mbox{ algebra } \gt \\ \max_{\| x \|_\infty = 1} \max_{0 \leq i \lt m} \sum_{p=0}^{n-1} ( \vert \alpha_{i,p} \vert ( \max_k \vert \chi_k \vert ) ) \\ ~~~=~~~~ \lt \mbox{ definition of } \| \cdot \|_\infty \gt \\ \max_{\| x \|_\infty = 1} \max_{0 \leq i \lt m} \sum_{p=0}^{n-1} ( \vert \alpha_{i,p} \vert \| x \|_\infty ) \\ ~~~=~~~~ \lt \| x \|_\infty = 1 \gt \\ \max_{0 \leq i \lt m} \sum_{p=0}^{n-1} \vert \alpha_{i,p} \vert \\ ~~~=~~~~ \lt \mbox{ definition of } \| \cdot \|_1 \gt \\ \max_{0\leq i \lt m} \| \widetilde a_i \|_1 \end{array} \end{equation*}

so that $\| A \|_\infty \leq \max_{0 \leq i \lt m} \| \widetilde a_i \|_1 \text{.}$

We also want to show that $\| A \|_\infty \geq \max_{0 \leq i \lt m} \| \widetilde a_i \|_1\text{.}$ Let $k$ be such that $\max_{0 \leq i \lt m} \| \widetilde a_i \|_1 = \| \widetilde a_k\|_1$ and pick $y = \left( \begin{array}{c} \psi_0 \\ \vdots \\ \psi_{n-1} \end{array} \right)$ so that $\widetilde a_k^T y = \vert \alpha_{k,0} \vert + \vert \alpha_{k,1} \vert + \cdots + \vert \alpha_{k,n-1} \vert = \| \widetilde a_k \|_1 \text{.}$ (This is a matter of picking $\psi_j = \vert \alpha_{k,j} \vert/ \alpha_{k,j}$ if $\alpha_{k,j} \neq 0$ and $\psi_j = 1$ otherwise. Then $\vert \psi_j \vert =1 \text{,}$ and hence $\| y \|_\infty = 1$ and $\psi_j \alpha_{k,j} = \vert \alpha_{k,j} \vert \text{.}$) Then

\begin{equation*} \begin{array}{l} \| A \|_\infty \\ ~~~=~~~ \lt \mbox{ definition} \gt \\ \max_{\|x\|_1=1} \| A x\|_\infty \\ ~~~=~~~~ \lt \mbox{ expose rows } \gt \\ \max_{\|x\|_1=1} \left\| \left( \begin{array}{c} \widetilde a_0^T \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T \end{array} \right) x \right\|_\infty \\ ~~~\geq~~~~ \lt y \mbox{ is a specific } x \gt \\ \left\| \left( \begin{array}{c} \widetilde a_0^T \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T \end{array} \right) y \right\|_\infty \\ ~~~=~~~~ \lt \mbox{ matrix-vector multiplication } \gt \\ \left\| \left( \begin{array}{c} \widetilde a_0^T y\\ \hline \vdots \\ \hline \widetilde a_{m-1}^T y \end{array} \right) \right\|_\infty \\ ~~~\geq~~~~ \lt \mbox{ algebra} \gt \\ \vert \widetilde a_k^T y \vert \\ ~~~=~~~~\lt \mbox{ choice of } y \gt \\ \| \widetilde a_k \|_1.\\ ~~~=~~~~ \lt \mbox{ choice of } k \gt \\ \max_{0 \leq i \lt m} \| \widetilde a_i \|_1 \end{array} \end{equation*}
###### Remark1.3.6.1.

The last homework provides a hint as to how to remember how to compute the matrix 1-norm and $\infty$-norm: Since $\| x \|_1$ must result in the same value whether $x$ is considered as a vector or as a matrix, we can remember that the matrix 1-norm equals the maximum of the 1-norms of the columns of the matrix: Similarly, considering $\| x \|_\infty$ as a vector norm or as matrix norm reminds us that the matrix $\infty$-norm equals the maximum of the 1-norms of vectors that become the rows of the matrix.