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.\)
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{.}\)
\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\|_\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 \\
~~~\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.
