Chapter 6 — Operator and Matrix Norms

Solution

Write \( \|T\| = \max\{ \|Tx\|_W : x \in V,\ \|x\|_V = 1 \} = \|Tv\|_W \) for some \(v\) that maximizes it.

• Clearly \( \|T\| \ge 0 \), as \( \|Tx\|_W \ge 0 \ \forall\, x \in V \). And \( \|T\| = 0 \iff \|Tx\|_W = 0 \ \forall\, x \in V,\ \|x\|_V = 1 \iff T = 0 \).
• \( \|aT\| = \max\{ \|(aT)(x)\|_W : x \in V,\ \|x\|_V = 1 \} = \max\{ |a|\,\|Tx\|_W : x \in V,\ \|x\|_V = 1 \} = |a|\,\|T\| \ \forall\, a \in \F \).
• For \( T, S \in \Lin(V, W) \), \( \|T + S\| = \max\{ \|(T+S)x\|_W : \|x\|_V = 1\} = \max\{ \|Tx + Sx\|_W : \|x\|_V = 1\} \le \max\{ \|Tx\|_W + \|Sx\|_W : \|x\|_V = 1\} \), so \( \|T + S\| \le \|T\| + \|S\| \).

Thus the operator norm is a valid norm on \( \Lin(V, W) \).

Submultiplicativity \( \|TS\| \le \|T\|\,\|S\| \ \forall\, T, S \in \Lin(V) \) (similar to Meyer, Ex 5.2.5). For \( x \neq 0 \), \( x \in V \), \( \big\|\tfrac{x}{\|x\|_V}\big\|_V = 1 \), so \( \dfrac{\|Tx\|_V}{\|x\|_V} = \big\|T\big(\tfrac{x}{\|x\|_V}\big)\big\|_V \le \|T\| \), giving \( \|Tx\|_V \le \|T\|\,\|x\|_V \ \forall\, x \in V \) (for \( x = 0 \) the inequality still holds). Then \[ \|TSx\|_V \le \|T\|\,\|Sx\|_V \le \|T\|\,\|S\|\,\|x\|_V \ \forall\, x \in V, \] so \( \max_{\|x\|=1}\|TSx\|_V \le \max_{\|x\|=1}\|T\|\,\|S\|\,\|x\|_V \), i.e. \( \|TS\| \le \|T\|\,\|S\| \).

Solution — (i) Frobenius norm is a matrix norm

• \( \|A\|_F \ge 0 \) as \( |a_{ij}| \ge 0 \ \forall\, i,j \); \( \|A\|_F = 0 \iff |a_{ij}| = 0 \ (1\le i\le m,\ 1\le j\le n) \iff A = 0 \).
• \( \|cA\|_F = \big(\sum_i\sum_j |c\,a_{ij}|^2\big)^{1/2} = \big(|c|^2 \sum_i\sum_j |a_{ij}|^2\big)^{1/2} \), so \( \|cA\|_F = |c|\,\|A\|_F \ \forall\, c \in \C \).

For the triangle inequality, \[\begin{aligned} \|A+B\|^2 &= \sum_{i=1}^{m}\sum_{j=1}^{n} |a_{ij} + b_{ij}|^2 \\ &= \sum_{i}\sum_{j}\big(|a_{ij}|^2 + |b_{ij}|^2 + 2|a_{ij}||b_{ij}|\big) \\ &= \|A\|_F^2 + \|B\|_F^2 + 2\sum_{i}\sum_{j}|a_{ij}||b_{ij}|. \end{aligned}\] Thinking of \( (a_{ij}) \) as a vector of length \( mn \) and applying the Cauchy–Schwarz inequality, \[\begin{aligned} &\le \|A\|_F^2 + \|B\|_F^2 + 2\Big(\sum_i\sum_j |a_{ij}|^2\Big)^{1/2}\Big(\sum_i\sum_j |b_{ij}|^2\Big)^{1/2} \\ &= \|A\|_F^2 + \|B\|_F^2 + 2\|A\|_F\|B\|_F = (\|A\|_F + \|B\|_F)^2, \end{aligned}\] so \( \|A+B\|_F \le \|A\|_F + \|B\|_F \).

For submultiplicativity \( \|AB\|_F \le \|A\|_F\|B\|_F \): for \( x \in \C^n \), \( (Ax)_i = \sum_{j=1}^{n} a_{ij} x_j \), so by Cauchy–Schwarz \( |(Ax)_i| \le \big(\sum_j |a_{ij}|^2\big)^{1/2}\big(\sum_j |x_j|^2\big)^{1/2} = \|A_i\|\,\|x\| \) (where \(A_i\) is the \(i\)-th row of \(A\)). Then \[ \|Ax\| = \Big(\sum_{i=1}^{m}(Ax)_i^2\Big)^{1/2} \le \Big(\sum_{i=1}^{m}\|A_i\|^2\|x\|^2\Big)^{1/2} \le \|x\|\Big(\sum_{i=1}^{m}\|A_i\|^2\Big)^{1/2} = \|A\|_F\,\|x\| \quad \forall\, x \in \C^n. \] Now for \( A, B \in \C^{n\times n} \), with \(B_j\) the \(j\)-th column of \(B\), \[ \|AB\|_F^2 = \sum_{j=1}^{n}\|AB_j\|^2 \le \sum_{j=1}^{n}\|A\|_F^2\|B_j\|^2 \le \|A\|_F^2\|B\|_F^2, \] so \( \|AB\|_F \le \|A\|_F\|B\|_F \). Thus the Frobenius norm is a valid matrix norm.

Solution — (ii) Frobenius norm is not an induced norm

An induced norm satisfies \( \|A\| = \max_{\|x\|=1}\|Ax\| \). If \( A = \mathrm{Id} \), then \( \|A\| = \max_{\|x\|=1}\|\mathrm{Id}(x)\| = 1 \). But \[ \|\mathrm{Id}\|_F = \Big(\sum_{i=1}^{n}(1)^2\Big)^{1/2} = \sqrt{n} \neq 1 \quad\text{for } n > 1. \] So the Frobenius norm is not an induced norm.

Solution — (i) \( \|A\|_2 \le \|A\|_F \)

For any \( x \in V \), \( x \neq 0 \), \( \tfrac{x}{\|x\|} \) has unit norm. With \( (Ax)_i = \sum_{j=1}^{n} a_{ij}x_j \), \[\begin{aligned} \|Ax\|_2^2 &= \sum_{i=1}^{m}\Big|\sum_{j=1}^{n}a_{ij}x_j\Big|^2 \\ &\le \sum_{i=1}^{m}\Big(\sum_{j=1}^{n}|a_{ij}x_j|\Big)^2 \\ &\le \sum_{i=1}^{m}\Big(\sum_{j=1}^{n}|a_{ij}|^2\Big)\Big(\sum_{j=1}^{n}|x_j|^2\Big) \\ &\le \|x\|_2^2\Big(\sum_{i=1}^{m}\sum_{j=1}^{n}|a_{ij}|^2\Big), \end{aligned}\] by the triangle and Cauchy–Schwarz inequalities. So \( \|Ax\|_2^2 \le \|x\|_2^2\,\|A\|_F^2 \), i.e. \( \dfrac{\|Ax\|_2^2}{\|x\|_2^2} \le \|A\|_F^2 \ \forall\, x \neq 0 \). Putting \( v = \tfrac{x}{\|x\|} \), \( \|Av\|_2 \le \|A\|_F \ \forall\, v \neq 0,\ \|v\|_2 = 1 \), so \( \max_{\|v\|=1}\|Av\|_2 \le \|A\|_F \), giving \( \|A\|_2 \le \|A\|_F \).

Solution — (ii) \( \|A\|_F \le \sqrt{r}\,\|A\|_2 \)

This bound is cleanest through the singular value decomposition (Chapter 10). Let \( A = \sum_{i=1}^{r} \sigma_i\, u_i v_i\herm \) be the SVD, where \( \sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0 \) are the \( r = \operatorname{rank}(A) \) non-zero singular values. Then \[ \|A\|_F^2 = \operatorname{trace}(A\herm A) = \sum_{i=1}^{r}\sigma_i^2 \qquad\text{and}\qquad \|A\|_2 = \sigma_1 = \max_i \sigma_i. \] Since each \( \sigma_i^2 \le \sigma_1^2 \), \[ \|A\|_F^2 = \sum_{i=1}^{r}\sigma_i^2 \le r\,\sigma_1^2 = r\,\|A\|_2^2 \implies \|A\|_F \le \sqrt{r}\,\|A\|_2. \] Combining both, \( \|A\|_2 \le \|A\|_F \le \sqrt{r}\,\|A\|_2 \).

Solution — (i) \( \|A\|_1 \) is an induced norm

For \( x \in \C^n \), \( \|x\|_1 = \sum_{i=1}^{n}|x_i| \). Then \[\begin{aligned} \|Ax\|_1 &= \sum_{i=1}^{m}\Big|\sum_{j=1}^{n}a_{ij}x_j\Big| \\ &\le \sum_{i=1}^{m}\sum_{j=1}^{n}|a_{ij}||x_j| = \sum_{j=1}^{n}|x_j|\Big(\sum_{i=1}^{m}|a_{ij}|\Big) \\ &\le \Big(\sum_{j=1}^{n}|x_j|\Big)\max_j\sum_{i=1}^{m}|a_{ij}| \le \|x\|_1 \max_j\sum_{i=1}^{m}|a_{ij}|. \end{aligned}\] Equality is attained: if \( v_k \) is the column of \(A\) with the largest absolute sum and \( x = e_k \), then \( \|x\|_1 = 1 \) and \( \|Ax\|_1 = \|v_k\|_1 = \max_j\sum_i|a_{ij}| \). So \( \|A\|_1 = \max_{\|x\|_1 = 1}\|Ax\|_1 = \max_{1\le j\le n}\sum_{i=1}^{m}|a_{ij}| \).

Solution — (ii) \( \|A\|_\infty \) is an induced norm

For \( x \in \C^n \), \( \|x\|_\infty = \max_{1\le i\le n}|x_i| \). Then \[\begin{aligned} \|Ax\|_\infty &= \max_{1\le i\le m}\Big|\sum_{j=1}^{n}a_{ij}x_j\Big| \\ &\le \max_{1\le i\le m}\sum_{j=1}^{n}|a_{ij}||x_j| \\ &\le \max_{1\le i\le m}\sum_{j=1}^{n}|a_{ij}|\,\big(\max_j|x_j|\big), \end{aligned}\] so \( \|Ax\|_\infty \le \|x\|_\infty \max_{1\le i\le m}\sum_{j=1}^{n}|a_{ij}| \). Equality is attained: if \( v_k \) is the row of \(A\) with the largest absolute sum, and \(x\) is such that \( x_j = \begin{cases} 1 & a_{kj} \ge 0 \\ -1 & a_{kj} < 0 \end{cases} \), then \( \|x\|_\infty = 1 \) and \( |v_k \cdot x| = \sum_{j=1}^{n}|a_{kj}x_j| = \max_i\sum_{j=1}^{n}|a_{ij}| \). So \( \|A\|_\infty = \max_{\|x\|=1}\|Ax\|_\infty = \max_{1\le i\le m}\sum_{j=1}^{n}|a_{ij}| \).

Solution — (iii) Induced norms are valid matrix norms

\( \|A\|_p = \max_{\|x\|_p = 1}\|Ax\|_p \), \( p \ge 1 \), \( A \in \C^{m\times n} \).

• \( \|A\|_p \ge 0 \) as \( \|Ax\|_p \ge 0 \ \forall\, x \in \C^n \); \( \|A\|_p = 0 \iff \|Ax\|_p = 0 \iff A = 0 \) (since \( x \neq 0 \), as \( \|x\|_p = 1 \)).
• \( \|cA\|_p = \max_{\|x\|_p = 1}\|cAx\|_p = \max_{\|x\|_p=1}|c|\,\|Ax\|_p = |c|\,\|A\|_p \) for \( c \in \C \).
• \( \|A+B\|_p = \max_{\|x\|_p=1}\|(A+B)x\|_p \le \max_{\|x\|_p=1}\big(\|Ax\|_p + \|Bx\|_p\big) \le \|A\|_p + \|B\|_p \).
• With \( \|A\|_p = \max_{x\neq 0}\dfrac{\|Ax\|_p}{\|x\|_p} \), \( \|AB\|_p = \max_{x\neq 0}\dfrac{\|ABx\|_p}{\|x\|_p} = \max_{Bx\neq 0}\dfrac{\|ABx\|_p}{\|Bx\|_p}\dfrac{\|Bx\|_p}{\|x\|_p} \le \Big(\max_{y\neq 0}\dfrac{\|Ay\|_p}{\|y\|_p}\Big)\Big(\max_{x\neq 0}\dfrac{\|Bx\|_p}{\|x\|_p}\Big) \le \|A\|_p\|B\|_p \).

Thus induced norms are valid matrix norms.

Solution — \( I - A \) is invertible

\( A \in \C^{n\times n} \) is finite-dimensional, so \( I - A \) is finite-dimensional. Suppose \( x \in \C^n \), \( x \neq 0 \). Then \( \|x\| = \|Ix\| = \|Ix - Ax + Ax\| \le \|(I-A)x\| + \|Ax\| \), so \( 1 \le \dfrac{\|(I-A)x\|}{\|x\|} + \dfrac{\|Ax\|}{\|x\|} \). Since \( \|A\| < 1 \), \( \dfrac{\|Ax\|}{\|x\|} < 1 \ \forall\, x \neq 0 \), so \( 1 < \dfrac{\|(I-A)x\|}{\|x\|} + 1 \), giving \( \dfrac{1}{\|x\|}\|(I-A)x\| > 0 \ \forall\, x \neq 0 \). Hence \( (I-A)x \neq 0 \ \forall\, x \neq 0 \Rightarrow \Null(I-A) = \{0\} \Rightarrow I - A \) is injective; being finite-dimensional, it is invertible.

Solution — the bound on \( \|(I-A)^{-1}\| \)

With \( x \in \C^n \), \( x \neq 0 \): \( \|x\| \le \|(I-A)x\| + \|Ax\| \), so \( \|x\| - \|Ax\| \le \|(I-A)x\| \), giving \( \dfrac{\|(I-A)x\|}{\|x\|} \ge 1 - \dfrac{\|Ax\|}{\|x\|} \). Since \( \|\cdot\| \) is submultiplicative, \( \|Ax\| \le \|A\|\|x\| \), so \( \dfrac{\|(I-A)x\|}{\|x\|} \ge 1 - \|A\| \). Hence \( \min_{x\neq 0}\dfrac{\|(I-A)x\|}{\|x\|} \ge 1 - \|A\| \), so \[ \|(I-A)^{-1}\| \le \frac{1}{1 - \|A\|}, \] using the fact that \( \min_{\|x\|=1}\|Ax\| = \dfrac{1}{\|A^{-1}\|} \) for non-singular \(A\) (Meyer, Ex 5.2.7), since \[\begin{aligned} \frac{1}{\min_{\|x\|=1}\|Ax\|} &= \max_{\|x\|=1}\frac{1}{\|Ax\|} \\ &= \max_{y\neq 0}\frac{1}{\big\|A\frac{A^{-1}y}{\|A^{-1}y\|}\big\|} \\ &= \max_{y\neq 0}\frac{\|A^{-1}y\|}{\|AA^{-1}y\|} = \max_{y\neq 0}\frac{\|A^{-1}y\|}{\|y\|} = \|A^{-1}\|. \end{aligned}\]

Solution — the Neumann series

Consider \( S_n = I + A + A^2 + \dots + A^n \). We show \( \lim_{n\to\infty}S_n = (I-A)^{-1} \), i.e. \( \|S_n - (I-A)^{-1}\| \to 0 \). Since \[ (I-A)S_n = (I-A)(I + A + \dots + A^n) = (I + A + \dots + A^n) - (A + A^2 + \dots + A^{n+1}) = I - A^{n+1}, \] we get \( S_n = (I-A)^{-1}(I - A^{n+1}) \), so \( S_n - (I-A)^{-1} = (I-A)^{-1}(I - A^{n+1}) - (I-A)^{-1} \) and \[\begin{aligned} \|S_n - (I-A)^{-1}\| &= \|(I-A)^{-1}(I - A^{n+1} - I)\| \\ &= \|(I-A)^{-1}A^{n+1}\| \\ &\le \|(I-A)^{-1}\|\,\|A^{n+1}\| \le \frac{1}{1-\|A\|}\|A\|^{n+1}, \end{aligned}\] using \( \|A^{n+1}\| \le \|A\|^{n+1} \). Since \( \|A\| < 1 \), \( \lim_{n\to\infty}\|A\|^{n+1} = 0 \), so \( \lim_{n\to\infty}\|S_n - (I-A)^{-1}\| = 0 \). Hence the series converges to \( (I-A)^{-1} \).

Solution

\(A\) is invertible. Let \(B\) be such that \( \|B - A\| = \delta \), and \( x \in \C^n \), \( x \neq 0 \). Then \[ \|Ax\| = \|Ax - Bx + Bx\| \le \|Ax - Bx\| + \|Bx\| \le \|(A-B)x\| + \|Bx\| \le \|A - B\|\,\|x\| + \|Bx\|, \] so \( \dfrac{\|Ax\|}{\|x\|} \le \delta + \dfrac{\|Bx\|}{\|x\|} \), i.e. \( \dfrac{\|Ax\|}{\|x\|} - \delta \le \dfrac{\|Bx\|}{\|x\|} \). For \(B\) to be invertible we need \( \|Bx\| > 0 \ \forall\, x \neq 0 \) (then \( \Null(B) = \{0\} \), so \(B\) is injective and, being finite-dimensional, invertible). So we need \( \dfrac{\|Ax\|}{\|x\|} - \delta > 0 \), i.e. \( \delta < \dfrac{\|Ax\|}{\|x\|} \ \forall\, x \neq 0 \), i.e. \( \delta < \min_{x\neq 0}\dfrac{\|Ax\|}{\|x\|} \). Therefore \[ \delta < \frac{1}{\|A^{-1}\|}. \] Thus \(B\) is invertible if \( \|B - A\| < \dfrac{1}{\|A^{-1}\|} \).

Solution

With \( p(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_k x^k \), \( p(A) = a_0 I + a_1 A + a_2 A^2 + \dots + a_k A^k \), so \[ p(A_n) - p(A) = a_1(A_n - A) + a_2(A_n^2 - A^2) + \dots + a_k(A_n^k - A^k), \] and \( \|p(A_n) - p(A)\| \le |a_1|\,\|A_n - A\| + \dots + |a_k|\,\|A_n^k - A^k\| \). We show each term \( \to 0 \) by induction.

Base case. \( \lim_{n\to\infty}\|A_n - A\| = 0 \) is given.

Inductive step. Assume \( \lim_{n\to\infty}\|A_n^{m-1} - A^{m-1}\| = 0 \) for \( 1 < m \le k \). Then \[ \|A_n^m - A^m\| = \|A_n A_n^{m-1} - A A_n^{m-1} + A A_n^{m-1} - A A^{m-1}\| \le \|A_n^{m-1}(A_n - A)\| + \|A(A_n^{m-1} - A^{m-1})\| \] \[ \le \|A_n^{m-1}\|\,\|A_n - A\| + \|A\|\,\|A_n^{m-1} - A^{m-1}\|, \] so \( \lim_{n\to\infty}\|A_n^m - A^m\| \le 0 + 0 = 0 \). Hence \( \lim_{n\to\infty}\|A_n^m - A^m\| = 0 \) for \( m = 1, \dots, k \), and therefore \( \lim_{n\to\infty}\|p(A_n) - p(A)\| = 0 \).