Exercise 6.2: Relations Between Matrix Operator Norms
We denote singular and eigenvalues respectively by \(\sigma\) and \(\gamma\). The superscripts min and max denote the smallest and largest such value (we only take eigenvalues of symmetric matrices, meaning they will all be in \(\R\)). For a matrix \(A \in \R^{m \times p}\), \(A_{i \cdot}\) denotes its \(i^\text{th}\) row, and \(A_{\cdot j}\) its \(j^\text{th}\) column.
(a)
-
\(\| A \|_2 = \sup_{\| x \|_2 = 1} \sqrt{x^\top A^\top A x} = \sigma_\text{max}(A)\) which is obtained by aligning \(x\) with the eigevector associated with \(\gamma_\text{max} (A^\top A) = \sigma_\text{max}(A)^2\).
-
\(\| A \|_1 = \sup_{\| x \|_1 = 1} \sum_{i} \bigl| \sum_j A_{ij} x_j \bigr| \leq \sup_{\| x \|_1 = 1} \sum_j |x_j| \| A_{\cdot j} \|_1 \leq \max_{j \in [p]} \| A_{\cdot j} \|_1\). Setting \(x\) to the canonical basis vector aligned with the maximising column, \(\| A \|_1 = \max_{j \in [m]} \| A_{\cdot j} \|_1\).
-
\(\| A \|_\infty = \sup_{\| x \|_\infty = 1} \max_{i \in [m]} \bigl|\sum_j A_{ij} x_j \bigr| \leq \max_{i \in [m]} \| A_{i \cdot} \|_1\) by Holder’s inequality. Setting \(x_j = \sign (A_{ij})\) for the maximising row, \(\| A \|_\infty = \max_{i \in [m]} \| A_{i \cdot} \|_1\).
(b)
\(\| A B x \|_q = \| A \frac{B x}{\| B x \|_q} \|_q \| B x \|_q \leq \| A \|_q \| B x \|_q \, ;\) the result thus follows by taking supremum over \(\|x\|_q = 1\).
(c)
From (a), \(\| A \|_2^2 = \| A^\top A \|_2 = \gamma_\text{max}(A^\top A)\). Take \(v\) to be the eigenevector associated with \(\gamma_\text{max}(A^\top A)\). By definition \(\| A^\top A v \|_1 = \gamma_\text{max}(A^\top A) \| v \|_1\), and thus by (b) \begin{align} \gamma_\text{max}(A^\top A) \| v \|_1 \leq \| A^\top A \|_1 \| v \|_1 \, , \end{align} i.e., \(\| A \|_2^2 \leq \|A^\top A\|_1\) as \(\| v \|_1 \neq 0\). Applying (b) again, \(\| A^\top A \|_1 \leq \|A^\top\|_1 \| A \|_1 = \|A\|_\infty \|A\|_1\).