16.5 Inverting a Perturbation of the Identity

Chapter 10 §10 summed the series $\mathbf{I} + \mathbf{A} + \mathbf{A}^2 + \dots$ and identified its sum as $(\mathbf{I} - \mathbf{A})^{-1}$ , under the exact hypothesis that every eigenvalue of $\mathbf{A}$ has modulus less than $1$ . What it could not say is how large that inverse is. This section reruns the argument with a norm in hand. The hypothesis becomes cruder — $\left\| \mathbf{A} \right\| < 1$ instead of $\rho(\mathbf{A}) < 1$ — and the conclusion becomes quantitative, which is the trade this chapter keeps making. The payoff is immediate: the invertible matrices turn out to form an open set, inversion turns out to be continuous, and a first estimate appears for how far the solution of $\mathbf{A}\mathbf{x} = \mathbf{b}$ moves when $\mathbf{A}$ and $\mathbf{b}$ are disturbed.

Throughout, $\left\| \cdot \right\|$ is the operator norm on $M_n(\mathbb{C})$ induced by a norm on $\mathbb{C}^{n}$ (Definition 16.3.2), so that $\left\| \mathbf{I} \right\| = 1$ and $\left\| \mathbf{X}\mathbf{Y} \right\| \le \left\| \mathbf{X} \right\|\left\| \mathbf{Y} \right\|$ by Theorem 16.3.2 (c) and (d). Both properties are used in every proof below, and the first of them is not free: the closing warning shows what happens without it.

16.5.1. The geometric series, with a number attached

The scalar identity behind everything here is $1 + r + r^2 + \dots = 1/(1-r)$ for $0 \le r < 1$ . Chapter 10 §10 gave the matrix version of the identity. What a norm adds is the matrix version of the inequality $\lvert 1 + r + \dots\rvert \le 1/(1-r)$ : a ceiling on the inverse, expressed in the data.

Theorem 16.5.1 (Neumann Series with a Bound)

Let $\mathbf{A} \in M_n(\mathbb{C})$ with $\left\| \mathbf{A} \right\| < 1$ , and write $a = \left\| \mathbf{A} \right\|$ . Then:

(a) $\mathbf{I} - \mathbf{A}$ is invertible, and $\sum_{k \ge 0}\mathbf{A}^{k} = (\mathbf{I} - \mathbf{A})^{-1}$ ;
(b) $\displaystyle \left\| (\mathbf{I} - \mathbf{A})^{-1} \right\| \le \frac{1}{1 - a}$ ;
(c) for every $K \ge 0$ , the partial sum $\mathbf{S}_K = \sum_{k=0}^{K}\mathbf{A}^{k}$ satisfies $\left\| (\mathbf{I} - \mathbf{A})^{-1} - \mathbf{S}_K \right\| \le \frac{a^{K+1}}{1 - a} ;$
(d) $\displaystyle \left\| (\mathbf{I} - \mathbf{A})^{-1} \right\| \ge \frac{1}{1 + a}$ .

Idea. Part (a) is not new work: $\left\| \mathbf{A} \right\| < 1$ forces $\rho(\mathbf{A}) < 1$ by Theorem 16.4.1, which is exactly the hypothesis of Chapter 10’s Theorem 10.10.6. Everything else is the tail-bounding move. Submultiplicativity turns $\left\| \mathbf{A}^{k} \right\|$ into $a^{k}$ , so each partial sum is bounded by a scalar geometric sum; the bound then has to be carried across the limit, and what carries it is the fact that a norm is continuous. For (c), the tail of the series factors as $\mathbf{A}^{K+1}$ times the whole series again, so (b) bounds it. For (d), read $\mathbf{I} = (\mathbf{I} - \mathbf{A})(\mathbf{I} - \mathbf{A})^{-1}$ through submultiplicativity.

Proof.

(a) By Theorem 16.4.1 (a), $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\| = a < 1$ , so every eigenvalue of $\mathbf{A}$ has modulus less than $1$ . That is the hypothesis of Theorem 10.10.6, which gives both the invertibility of $\mathbf{I} - \mathbf{A}$ and the value of the sum.
(b) Submultiplicativity (Theorem 16.3.2 (d)) gives $\left\| \mathbf{A}^{k} \right\| \le a^{k}$ for every $k \ge 1$ , by induction on $k$ ; and $\left\| \mathbf{A}^{0} \right\| = \left\| \mathbf{I} \right\| = 1 = a^{0}$ by part (c) of the same theorem. Hence, by subadditivity applied $K$ times, $\left\| \mathbf{S}_K \right\| \le \sum_{k=0}^{K}\left\| \mathbf{A}^{k} \right\| \le \sum_{k=0}^{K}a^{k} = \frac{1 - a^{K+1}}{1 - a} \le \frac{1}{1-a},$ the last step because $a^{K+1} \ge 0$ and $1 - a > 0$ . By (a) the sequence $(\mathbf{S}_K)$ converges entrywise to $(\mathbf{I} - \mathbf{A})^{-1}$ , so $\left\| \mathbf{S}_K - (\mathbf{I}-\mathbf{A})^{-1} \right\| \to 0$ by Corollary 16.2.4. Then Lemma 16.1.1 gives $\bigl\lvert\,\left\| \mathbf{S}_K \right\| - \left\| (\mathbf{I}-\mathbf{A})^{-1} \right\|\,\bigr\rvert \le \left\| \mathbf{S}_K - (\mathbf{I}-\mathbf{A})^{-1} \right\| \to 0,$ so $\left\| \mathbf{S}_K \right\| \to \left\| (\mathbf{I} - \mathbf{A})^{-1} \right\|$ . A non-strict inequality survives a limit, so a limit of numbers each at most $1/(1-a)$ is at most $1/(1-a)$ , which proves (b).
(c) Fix $K$ . For every $M \ge 1$ , multiplying out and canceling, $\mathbf{S}_{K+M} - \mathbf{S}_K = \sum_{k=K+1}^{K+M}\mathbf{A}^{k} = \mathbf{A}^{K+1}\,\mathbf{S}_{M-1} .$ Let $M \to \infty$ . The left-hand side tends to $(\mathbf{I}-\mathbf{A})^{-1} - \mathbf{S}_K$ by (a). The right-hand side tends to $\mathbf{A}^{K+1}(\mathbf{I}-\mathbf{A})^{-1}$ , because $\left\| \mathbf{A}^{K+1}\mathbf{S}_{M-1} - \mathbf{A}^{K+1}(\mathbf{I}-\mathbf{A})^{-1} \right\| \le \left\| \mathbf{A}^{K+1} \right\|\,\left\| \mathbf{S}_{M-1} - (\mathbf{I}-\mathbf{A})^{-1} \right\| ,$ which tends to $0$ by (a) and Corollary 16.2.4 again. A sequence has at most one limit, so $(\mathbf{I} - \mathbf{A})^{-1} - \mathbf{S}_K = \mathbf{A}^{K+1}(\mathbf{I} - \mathbf{A})^{-1} .$ Taking norms and using submultiplicativity together with (b), $\left\| (\mathbf{I}-\mathbf{A})^{-1} - \mathbf{S}_K \right\| \le \left\| \mathbf{A}^{K+1} \right\|\,\left\| (\mathbf{I}-\mathbf{A})^{-1} \right\| \le \frac{a^{K+1}}{1-a} .$
(d) $1 = \left\| \mathbf{I} \right\| = \left\| (\mathbf{I} - \mathbf{A})(\mathbf{I}-\mathbf{A})^{-1} \right\| \le \left\| \mathbf{I} - \mathbf{A} \right\|\,\left\| (\mathbf{I}-\mathbf{A})^{-1} \right\|$ , and $\left\| \mathbf{I} - \mathbf{A} \right\| \le \left\| \mathbf{I} \right\| + \left\| \mathbf{A} \right\| = 1 + a$ by subadditivity. Since $1 + a > 0$ we may divide, which proves (d). This proves the theorem.

Parts (b) and (d) together pin the inverse between two numbers computed from $a$ alone: $\frac{1}{1+a} \le \left\| (\mathbf{I}-\mathbf{A})^{-1} \right\| \le \frac{1}{1-a} .$ As $a$ approaches $1$ the upper bound escapes to infinity while the lower one stays near $\tfrac12$ , and the gap is real rather than an artifact of the proof: $\mathbf{A} = a\mathbf{I}$ attains the upper bound, and $\mathbf{A} = -a\mathbf{I}$ attains the lower one.

Example (The bound and the truth)

Let $\mathbf{A} = \begin{pmatrix} 0 & 1/2 \\ 1/3 & 0 \end{pmatrix} .$ Using the $\infty$ -norm, check the hypothesis, compute $(\mathbf{I} - \mathbf{A})^{-1}$ exactly, and compare it with the bound of Theorem 16.5.1 (b). Then compare $\mathbf{S}_3$ with the true inverse and with the tail bound of (c).

Solution. The hypothesis. The absolute row sums are $\tfrac12$ and $\tfrac13$ , so $\left\| \mathbf{A} \right\|_{\infty} = \tfrac12 < 1$ by Theorem 16.3.3 (b). So Theorem 16.5.1 applies with $a = \tfrac12$ .

The inverse. $\mathbf{I} - \mathbf{A} = \begin{psmallmatrix} 1 & -1/2 \\ -1/3 & 1\end{psmallmatrix}$ has determinant $1 - \tfrac16 = \tfrac56$ , so by Theorem 0.9.8 $(\mathbf{I} - \mathbf{A})^{-1} = \tfrac65\begin{pmatrix} 1 & 1/2 \\ 1/3 & 1 \end{pmatrix} = \begin{pmatrix} 6/5 & 3/5 \\ 2/5 & 6/5 \end{pmatrix},$ whose largest absolute row sum is $\tfrac65 + \tfrac35 = \tfrac95 = 1.8$ . The bound is $1/(1 - \tfrac12) = 2$ . So the estimate is correct and loses only ten percent.

The partial sum. Here $\mathbf{A}^{2} = \tfrac16\mathbf{I}$ , so $\mathbf{A}^{3} = \tfrac16\mathbf{A}$ and $\mathbf{S}_3 = \bigl(1 + \tfrac16\bigr)(\mathbf{I} + \mathbf{A}) = \tfrac76\begin{pmatrix} 1 & 1/2 \\ 1/3 & 1\end{pmatrix} .$ Hence $(\mathbf{I}-\mathbf{A})^{-1} - \mathbf{S}_3 = \bigl(\tfrac65 - \tfrac76\bigr)(\mathbf{I} + \mathbf{A}) = \tfrac1{30}(\mathbf{I} + \mathbf{A})$ , with $\infty$ -norm $\tfrac1{30}\cdot\tfrac32 = \tfrac1{20} = 0.05$ . The bound of (c) with $K = 3$ is $(\tfrac12)^{4}/(1 - \tfrac12) = \tfrac18 = 0.125$ . Again correct, and this time loose by a factor of $2.5$ — the price of replacing four matrices by four copies of one number.

16.5.2. Which theorem is stronger

The two Neumann theorems must be compared honestly, because neither contains the other.

Chapter 10’s Theorem 10.10.6 assumes $\rho(\mathbf{A}) < 1$ and concludes that the series converges, with sum $(\mathbf{I}-\mathbf{A})^{-1}$ ; and its hypothesis is sharp, since the statement is an “if and only if”. Theorem 16.5.1 assumes $\left\| \mathbf{A} \right\| < 1$ , which by Theorem 16.4.1 is a strictly stronger demand: $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|$ always, and the inequality is often strict. For $\mathbf{A} = \begin{pmatrix} 0 & 2 \\ 0 & 0 \end{pmatrix}$ we have $\rho(\mathbf{A}) = 0$ , so Chapter 10’s theorem applies and returns $\sum_k \mathbf{A}^{k} = \mathbf{I} + \mathbf{A}$ ; but $\left\| \mathbf{A} \right\| = 2$ in each of the $1$ -, $2$ - and $\infty$ -norms, so this section’s theorem says nothing at all about it.

In the other direction, when this section’s theorem does apply it says strictly more: a ceiling on the inverse, a rate at which the partial sums approach it, and a floor as well. Chapter 10 could not have stated any of the three, having no way to measure a matrix.

There is a third thing to say, and it dissolves most of the apparent conflict. If $\rho(\mathbf{A}) < 1$ , then by Theorem 16.4.3 there is a norm $\left\| \cdot \right\|_t$ with $\left\| \mathbf{A} \right\|_t \le \rho(\mathbf{A}) + \varepsilon < 1$ , and Theorem 16.5.1 applies in that norm. For the matrix above, taking $\mathbf{D} = \operatorname{diag}(1, 4)$ and $\left\| \mathbf{x} \right\|_t = \left\| \mathbf{D}\mathbf{x} \right\|_{\infty}$ gives $\left\| \mathbf{A} \right\|_t = \left\| \mathbf{D}\mathbf{A}\mathbf{D}^{-1} \right\|_{\infty} = \tfrac12$ , so the bound reads $\left\| (\mathbf{I}-\mathbf{A})^{-1} \right\|_t \le 2$ ; and indeed $\mathbf{D}(\mathbf{I} + \mathbf{A})\mathbf{D}^{-1} = \begin{psmallmatrix} 1 & 1/2 \\ 0 & 1\end{psmallmatrix}$ has $\infty$ -norm $\tfrac32 \le 2$ . So the quantitative theorem can always be brought to bear on a matrix Chapter 10 accepts — at the cost of changing the norm, and the bound it then produces is a bound in that new norm, which may be a strange unit of measurement.

Quick check. Both theorems need a hypothesis. Which of the two hypotheses, $\rho(\mathbf{A}) < 1$ and $\left\| \mathbf{A} \right\| < 1$ , can be checked by looking at the entries of $\mathbf{A}$ and doing no linear algebra?

Solution. The second, for a suitable norm: $\left\| \mathbf{A} \right\|_1$ and $\left\| \mathbf{A} \right\|_{\infty}$ are the largest absolute column and row sums (Theorem 16.3.3), read straight off the entries. Deciding $\rho(\mathbf{A}) < 1$ requires the eigenvalues, that is, the roots of a degree- $n$ polynomial. This is the practical reason the cruder hypothesis is worth having: it is the one a reader can verify at a glance, and Corollary 16.4.2 is the same observation used in the other direction.

Warning. The hypothesis $\left\| \mathbf{A} \right\| < 1$ is sufficient and never necessary. A matrix can be as far from $\mathbf{I}$ as one likes and still have $\mathbf{I} - \mathbf{A}$ invertible: $\mathbf{A} = 5\mathbf{I}$ gives $(\mathbf{I} - \mathbf{A})^{-1} = -\tfrac14\mathbf{I}$ . What fails when $\left\| \mathbf{A} \right\| \ge 1$ is not the invertibility but the argument, and with it the bound. Read $\left\| \mathbf{A} \right\| < 1$ as “ $\mathbf{A}$ is a small perturbation”, not as a criterion.

16.5.3. The invertible matrices form an open set

The theorem above concerns perturbations of $\mathbf{I}$ . Every invertible matrix can be moved to $\mathbf{I}$ by multiplication, so the general statement follows at once, and it is the statement several earlier arguments wanted: a matrix near an invertible matrix is invertible, and its inverse is near.

Corollary 16.5.2 (Invertibility Is an Open Condition, and Inversion Is Continuous)

Let $\mathbf{B} \in M_n(\mathbb{C})$ be invertible and let $\mathbf{E} \in M_n(\mathbb{C})$ satisfy $\left\| \mathbf{E} \right\| < \frac{1}{\left\| \mathbf{B}^{-1} \right\|} .$ Write $r = \left\| \mathbf{B}^{-1} \right\|\left\| \mathbf{E} \right\| < 1$ . Then:

(a) $\mathbf{B} + \mathbf{E}$ is invertible, and $\displaystyle \left\| (\mathbf{B}+\mathbf{E})^{-1} \right\| \le \frac{\left\| \mathbf{B}^{-1} \right\|}{1 - r}$ ;
(b) $\displaystyle \left\| (\mathbf{B}+\mathbf{E})^{-1} - \mathbf{B}^{-1} \right\| \le \frac{\left\| \mathbf{B}^{-1} \right\|^{2}\left\| \mathbf{E} \right\|}{1 - r}$ .

Consequently $\operatorname{GL}_n(\mathbb{C})$ is an open subset of $M_n(\mathbb{C})$ : around every invertible $\mathbf{B}$ the ball of radius $1/\left\| \mathbf{B}^{-1} \right\|$ consists of invertible matrices. And inversion is continuous on it: if $\mathbf{B}_m \to \mathbf{B}$ with $\mathbf{B}$ invertible, then $\mathbf{B}_m$ is invertible for all large $m$ and $\mathbf{B}_m^{-1} \to \mathbf{B}^{-1}$ .

Idea. Factor the perturbed matrix as $\mathbf{B} + \mathbf{E} = \mathbf{B}(\mathbf{I} + \mathbf{B}^{-1}\mathbf{E})$ — legitimate because $\mathbf{B}$ is invertible — and notice that $\left\| \mathbf{B}^{-1}\mathbf{E} \right\| \le r < 1$ , so the second factor is a perturbation of the identity of exactly the kind Theorem 16.5.1 handles, with $\mathbf{A} = -\mathbf{B}^{-1}\mathbf{E}$ . For (b), the difference of two inverses always factors as $\mathbf{X}^{-1} - \mathbf{Y}^{-1} = \mathbf{X}^{-1}(\mathbf{Y} - \mathbf{X})\mathbf{Y}^{-1}$ , and both inverses are now bounded.

Proof. Put $\mathbf{A} = -\mathbf{B}^{-1}\mathbf{E}$ . By submultiplicativity, $\left\| \mathbf{A} \right\| \le \left\| \mathbf{B}^{-1} \right\|\left\| \mathbf{E} \right\| = r < 1$ .

(a) Since $\mathbf{B}$ is invertible, $\mathbf{B} + \mathbf{E} = \mathbf{B}(\mathbf{I} + \mathbf{B}^{-1}\mathbf{E}) = \mathbf{B}(\mathbf{I} - \mathbf{A})$ . By Theorem 16.5.1 (a) the factor $\mathbf{I} - \mathbf{A}$ is invertible, so $\mathbf{B} + \mathbf{E}$ is a product of invertible matrices and is invertible, with $(\mathbf{B} + \mathbf{E})^{-1} = (\mathbf{I} - \mathbf{A})^{-1}\mathbf{B}^{-1} .$ By submultiplicativity and Theorem 16.5.1 (b), $\left\| (\mathbf{B}+\mathbf{E})^{-1} \right\| \le \left\| (\mathbf{I}-\mathbf{A})^{-1} \right\|\,\left\| \mathbf{B}^{-1} \right\| \le \frac{\left\| \mathbf{B}^{-1} \right\|}{1 - \left\| \mathbf{A} \right\|} \le \frac{\left\| \mathbf{B}^{-1} \right\|}{1 - r} ,$ the last step because $\left\| \mathbf{A} \right\| \le r$ and $t \mapsto 1/(1-t)$ increases on $[0,1)$ .
(b) Multiplying the identity $\mathbf{B} - (\mathbf{B} + \mathbf{E}) = -\mathbf{E}$ on the left by $(\mathbf{B}+\mathbf{E})^{-1}$ and on the right by $\mathbf{B}^{-1}$ gives $(\mathbf{B}+\mathbf{E})^{-1} - \mathbf{B}^{-1} = -(\mathbf{B}+\mathbf{E})^{-1}\mathbf{E}\,\mathbf{B}^{-1} .$ Taking norms and applying submultiplicativity twice and then (a), $\left\| (\mathbf{B}+\mathbf{E})^{-1} - \mathbf{B}^{-1} \right\| \le \frac{\left\| \mathbf{B}^{-1} \right\|}{1-r}\,\left\| \mathbf{E} \right\|\,\left\| \mathbf{B}^{-1} \right\| = \frac{\left\| \mathbf{B}^{-1} \right\|^{2}\left\| \mathbf{E} \right\|}{1-r} .$

For the two consequences: openness is the statement of (a) with $\mathbf{E}$ ranging over the ball of radius $1/\left\| \mathbf{B}^{-1} \right\|$ . For continuity, let $\mathbf{B}_m \to \mathbf{B}$ with $\mathbf{B}$ invertible, and put $\mathbf{E}_m = \mathbf{B}_m - \mathbf{B}$ . By Corollary 16.2.4, $\left\| \mathbf{E}_m \right\| \to 0$ , so $\left\| \mathbf{E}_m \right\| < 1/(2\left\| \mathbf{B}^{-1} \right\|)$ for all large $m$ ; for those $m$ , part (a) applies with $r \le \tfrac12$ and $\mathbf{B}_m$ is invertible, and part (b) gives $\left\| \mathbf{B}_m^{-1} - \mathbf{B}^{-1} \right\| \le 2\left\| \mathbf{B}^{-1} \right\|^{2}\left\| \mathbf{E}_m \right\| \to 0 .$ This proves the corollary.

Example (How far an invertible matrix can be pushed)

Take $\mathbf{B} = \begin{psmallmatrix} 2 & 1 \\ 0 & 2\end{psmallmatrix}$ and work with $\left\| \cdot \right\|_\infty$ . Then $\mathbf{B}^{-1} = \begin{psmallmatrix} \tfrac12 & -\tfrac14 \\ 0 & \tfrac12\end{psmallmatrix}$ , whose largest absolute row sum is $\tfrac12 + \tfrac14 = \tfrac34$ , so $\left\| \mathbf{B}^{-1} \right\|_\infty = \tfrac34$ . Corollary 16.5.2 therefore keeps $\mathbf{B} + \mathbf{E}$ invertible for every $\mathbf{E}$ with $\left\| \mathbf{E} \right\|_\infty < \frac{1}{\left\| \mathbf{B}^{-1} \right\|_\infty} = \frac43 .$ For a perturbation of size $\left\| \mathbf{E} \right\|_\infty \le \tfrac12$ we get $r = \tfrac34\cdot\tfrac12 = \tfrac38$ , and part (a) bounds $\left\| (\mathbf{B}+\mathbf{E})^{-1} \right\|_\infty \ \le\ \frac{3/4}{1 - 3/8} \ =\ \frac65 .$ The bound is honest rather than tight: pushing every entry of $\mathbf{E}$ to $\pm\tfrac14$ gives at worst $\left\| (\mathbf{B}+\mathbf{E})^{-1} \right\|_\infty = \tfrac{12}{11} \approx 1.09$ , against the promised $1.2$ . What the corollary buys is not the sharpest constant but a radius inside which no invertibility check is needed at all.

Part (a) has a reading worth recording, since the relative-error theorem of §08 is the same sentence with the constant named: the distance from an invertible $\mathbf{B}$ to the nearest singular matrix is at least $1/\left\| \mathbf{B}^{-1} \right\|$ . A large $\left\| \mathbf{B}^{-1} \right\|$ is therefore not an abstract complaint; it says that $\mathbf{B}$ is close, in the literal sense of the norm, to a matrix that cannot be inverted at all.

Remark. Chapter 12 §01 proved that every matrix has diagonalizable matrices arbitrarily close to it (Corollary 12.1.6) and used the word “close” before this chapter existed. Corollary 16.5.2 is the first of the two facts that argument needs; the second is the continuity of the eigenvalues, and the two are put together in §07.

16.5.4. Perturbing a solve

The question the rest of the chapter circles is this. A linear system $\mathbf{A}\mathbf{x} = \mathbf{b}$ is solved; the data $\mathbf{A}$ and $\mathbf{b}$ were only known approximately; how wrong can $\mathbf{x}$ be? With Corollary 16.5.2 available the answer is three lines, and it already contains the quantity §08 will name.

Theorem 16.5.3 (Relative Error in a Perturbed Solve)

Let $\mathbf{A} \in M_n(\mathbb{C})$ be invertible, let $\mathbf{b} \ne \mathbf{0}$ , and let $\mathbf{x}$ be the solution of $\mathbf{A}\mathbf{x} = \mathbf{b}$ . Let $\mathbf{E} \in M_n(\mathbb{C})$ and $\mathbf{f} \in \mathbb{C}^{n}$ be perturbations with $r = \left\| \mathbf{A}^{-1} \right\|\left\| \mathbf{E} \right\| < 1 ,$ and let $\widetilde{\mathbf{x}}$ be the solution of $(\mathbf{A} + \mathbf{E})\widetilde{\mathbf{x}} = \mathbf{b} + \mathbf{f}$ , which exists and is unique by Corollary 16.5.2. Then $\frac{\left\| \widetilde{\mathbf{x}} - \mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \le \frac{\left\| \mathbf{A} \right\|\,\left\| \mathbf{A}^{-1} \right\|}{1 - r} \left( \frac{\left\| \mathbf{E} \right\|}{\left\| \mathbf{A} \right\|} + \frac{\left\| \mathbf{f} \right\|}{\left\| \mathbf{b} \right\|} \right) .$

Idea. Subtract the two equations to isolate $\mathbf{A}(\widetilde{\mathbf{x}} - \mathbf{x})$ ; what is left on the other side is $\mathbf{f} - \mathbf{E}\widetilde{\mathbf{x}}$ . Apply $\mathbf{A}^{-1}$ and take norms. The one awkward term is $\left\| \widetilde{\mathbf{x}} \right\|$ , which is not data; write $\widetilde{\mathbf{x}} = \mathbf{x} + (\widetilde{\mathbf{x}} - \mathbf{x})$ and move the resulting copy of $\left\| \widetilde{\mathbf{x}} - \mathbf{x} \right\|$ to the left, which is where the factor $1/(1-r)$ comes from. Finally $\left\| \mathbf{b} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{x} \right\|$ converts $1/\left\| \mathbf{x} \right\|$ into $\left\| \mathbf{A} \right\|/\left\| \mathbf{b} \right\|$ , and the two perturbations appear only through their relative sizes.

Proof. Write $\mathbf{d} = \widetilde{\mathbf{x}} - \mathbf{x}$ . Subtracting $\mathbf{A}\mathbf{x} = \mathbf{b}$ from $(\mathbf{A}+\mathbf{E})\widetilde{\mathbf{x}} = \mathbf{b} + \mathbf{f}$ gives $\mathbf{A}\widetilde{\mathbf{x}} + \mathbf{E}\widetilde{\mathbf{x}} - \mathbf{A}\mathbf{x} = \mathbf{f}$ , that is, $\mathbf{A}\mathbf{d} = \mathbf{f} - \mathbf{E}\widetilde{\mathbf{x}}$ . Since $\mathbf{A}$ is invertible, $\mathbf{d} = \mathbf{A}^{-1}(\mathbf{f} - \mathbf{E}\widetilde{\mathbf{x}})$ , and Theorem 16.3.2 (a) with subadditivity gives $\left\| \mathbf{d} \right\| \le \left\| \mathbf{A}^{-1} \right\|\bigl(\left\| \mathbf{f} \right\| + \left\| \mathbf{E} \right\|\,\left\| \widetilde{\mathbf{x}} \right\|\bigr) .$ Now $\left\| \widetilde{\mathbf{x}} \right\| \le \left\| \mathbf{x} \right\| + \left\| \mathbf{d} \right\|$ , so $\left\| \mathbf{d} \right\| \le \left\| \mathbf{A}^{-1} \right\|\left\| \mathbf{f} \right\| + \left\| \mathbf{A}^{-1} \right\|\left\| \mathbf{E} \right\|\left\| \mathbf{x} \right\| + r\left\| \mathbf{d} \right\| ,$ using $\left\| \mathbf{A}^{-1} \right\|\left\| \mathbf{E} \right\| = r$ on the last term. Since $r < 1$ we may subtract $r\left\| \mathbf{d} \right\|$ and divide by $1 - r > 0$ : $\left\| \mathbf{d} \right\| \le \frac{\left\| \mathbf{A}^{-1} \right\|}{1-r}\bigl(\left\| \mathbf{f} \right\| + \left\| \mathbf{E} \right\|\left\| \mathbf{x} \right\|\bigr) .$ Divide by $\left\| \mathbf{x} \right\|$ , which is non-zero because $\mathbf{b} \ne \mathbf{0}$ : $\frac{\left\| \mathbf{d} \right\|}{\left\| \mathbf{x} \right\|} \le \frac{\left\| \mathbf{A}^{-1} \right\|}{1-r} \left( \frac{\left\| \mathbf{f} \right\|}{\left\| \mathbf{x} \right\|} + \left\| \mathbf{E} \right\| \right) .$ Finally $\left\| \mathbf{b} \right\| = \left\| \mathbf{A}\mathbf{x} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{x} \right\|$ , so $1/\left\| \mathbf{x} \right\| \le \left\| \mathbf{A} \right\|/\left\| \mathbf{b} \right\|$ . Substituting this in the first term and writing $\left\| \mathbf{E} \right\| = \left\| \mathbf{A} \right\|\cdot\left\| \mathbf{E} \right\|/\left\| \mathbf{A} \right\|$ in the second gives the stated inequality. This proves the theorem.

The shape of the conclusion is the point. On the right, the two perturbations appear only as relative sizes, $\left\| \mathbf{E} \right\|/\left\| \mathbf{A} \right\|$ and $\left\| \mathbf{f} \right\|/\left\| \mathbf{b} \right\|$ ; on the left is the relative size of the error. Between them stands one number built from $\mathbf{A}$ alone, $\left\| \mathbf{A} \right\|\,\left\| \mathbf{A}^{-1} \right\| ,$ inflated slightly by $1/(1-r)$ , which is close to $1$ whenever the perturbation of $\mathbf{A}$ is small. That number is the condition number of §08. Everything that section does is to give it a name, compute it for the $2$ -norm, and show that the bound is attained.

Example (A perturbation of the matrix)

Let $\mathbf{A} = \begin{pmatrix} 2 & 1 \\ 1 & 1\end{pmatrix}, \quad \mathbf{b} = \begin{pmatrix} 3 \\ 2\end{pmatrix}, \quad \mathbf{E} = \begin{pmatrix} 0 & 0 \\ 0 & 1/10 \end{pmatrix}, \quad \mathbf{f} = \mathbf{0} .$ Solve both systems in the $\infty$ -norm, compute the relative error, and compare it with Theorem 16.5.3.

Solution. The two solutions. $\det \mathbf{A} = 1$ , so $\mathbf{A}^{-1} = \begin{psmallmatrix} 1 & -1 \\ -1 & 2\end{psmallmatrix}$ by Theorem 0.9.8, and $\mathbf{x} = \mathbf{A}^{-1}\mathbf{b} = (3 - 2,\ -3 + 4) = (1, 1)$ . For the perturbed matrix, $\mathbf{A} + \mathbf{E} = \begin{psmallmatrix} 2 & 1 \\ 1 & 11/10 \end{psmallmatrix}$ has determinant $\tfrac{22}{10} - 1 = \tfrac65$ , so $\widetilde{\mathbf{x}} = \tfrac56\begin{pmatrix} 11/10 & -1 \\ -1 & 2 \end{pmatrix}\begin{pmatrix} 3 \\ 2\end{pmatrix} = \tfrac56\begin{pmatrix} 13/10 \\ 1 \end{pmatrix} = \begin{pmatrix} 13/12 \\ 5/6 \end{pmatrix} .$

The error. $\widetilde{\mathbf{x}} - \mathbf{x} = (\tfrac1{12}, -\tfrac16)$ , so $\left\| \widetilde{\mathbf{x}} - \mathbf{x} \right\|_{\infty} = \tfrac16$ and, since $\left\| \mathbf{x} \right\|_{\infty} = 1$ , the relative error is $\tfrac16 \approx 0.167$ .

The bound. The absolute row sums give $\left\| \mathbf{A} \right\|_{\infty} = 3$ and $\left\| \mathbf{A}^{-1} \right\|_{\infty} = 3$ , so $\left\| \mathbf{A} \right\|_{\infty}\left\| \mathbf{A}^{-1} \right\|_{\infty} = 9$ . Also $\left\| \mathbf{E} \right\|_{\infty} = \tfrac1{10}$ and $r = 3\cdot\tfrac1{10} = \tfrac3{10} < 1$ . With $\mathbf{f} = \mathbf{0}$ the bound is $\frac{9}{1 - \tfrac3{10}}\cdot\frac{1/10}{3} = \frac{9}{7/10}\cdot\frac1{30} = \frac37 \approx 0.429 .$ So $0.167 \le 0.429$ : correct, and loose by a factor of about $2.6$ . Note the accounting. The matrix was disturbed by $3.3\%$ of its size and the answer moved by $16.7\%$ , an amplification of about $5$ ; the theorem promised at most $9/(1 - 0.3) \approx 12.9$ .

Warning. All four bounds of this section need $\left\| \mathbf{I} \right\| = 1$ , which is a property of induced norms only. The Frobenius norm is submultiplicative (Example (The Frobenius norm is submultiplicative)) but has $\left\| \mathbf{I}_n \right\|_F = \sqrt n$ . Take $\mathbf{A} = 0$ in $M_2(\mathbb{C})$ : then $\left\| \mathbf{A} \right\|_F = 0 < 1$ , while $\left\| (\mathbf{I} - \mathbf{A})^{-1} \right\|_F = \left\| \mathbf{I}_2 \right\|_F = \sqrt2 > 1 = \frac{1}{1 - \left\| \mathbf{A} \right\|_F} ,$ so Theorem 16.5.1 (b) is false for it. The repair is easy — Exercise (C3: Without $\left\| \mathbf{I} \right\| = 1$ ) — but it is not the same inequality, and using the Frobenius norm here is the most common way to arrive at a wrong constant.

16.5.5. Exercises

A. Check your understanding

Exercise (A1)

(a) State Theorem 16.5.1 in full, including which kind of norm it assumes.
(b) Chapter 10 §10 already proved that $\sum_k\mathbf{A}^{k}$ converges to $(\mathbf{I}-\mathbf{A})^{-1}$ when $\rho(\mathbf{A}) < 1$ . Say precisely what this section adds, and what it gives up.
(c) Determine whether the following statement is correct, and justify your answer: if $\mathbf{I} - \mathbf{A}$ is invertible then $\left\| \mathbf{A} \right\| < 1$ .
(d) Where in the proof of Theorem 16.5.1 is $\left\| \mathbf{I} \right\| = 1$ used?
(e) State what Corollary 16.5.2 says about the distance from an invertible matrix to the singular matrices.

Solution.

(a) If $\left\| \cdot \right\|$ is the operator norm induced by a vector norm and $\left\| \mathbf{A} \right\| = a < 1$ , then $\mathbf{I} - \mathbf{A}$ is invertible with $\sum_{k\ge0}\mathbf{A}^{k} = (\mathbf{I}-\mathbf{A})^{-1}$ ; moreover $\left\| (\mathbf{I}-\mathbf{A})^{-1} \right\| \le 1/(1-a)$ , the partial sums satisfy $\left\| (\mathbf{I}-\mathbf{A})^{-1} - \mathbf{S}_K \right\| \le a^{K+1}/(1-a)$ , and $\left\| (\mathbf{I}-\mathbf{A})^{-1} \right\| \ge 1/(1+a)$ .
(b) It adds three numbers: a ceiling on the inverse, a geometric rate for the partial sums, and a floor. It gives up sharpness of the hypothesis: $\rho(\mathbf{A}) < 1$ is necessary and sufficient for convergence, whereas $\left\| \mathbf{A} \right\| < 1$ is only sufficient, and strictly stronger by Theorem 16.4.1.
(c) Incorrect. $\mathbf{A} = 5\mathbf{I}$ has $\mathbf{I} - \mathbf{A} = -4\mathbf{I}$ , invertible, while $\left\| \mathbf{A} \right\| = 5$ in every induced norm. Invertibility of $\mathbf{I} - \mathbf{A}$ says only $1 \notin \operatorname{spec}(\mathbf{A})$ .
(d) Twice, and both times to make a geometric sum start at $1$ : in (b), where $\left\| \mathbf{A}^{0} \right\| = \left\| \mathbf{I} \right\| = 1$ is the $k = 0$ term of $\sum_k a^{k}$ ; and in (d), where $1 = \left\| \mathbf{I} \right\|$ is the left-hand side of the estimate.
(e) It is at least $1/\left\| \mathbf{B}^{-1} \right\|$ : every $\mathbf{E}$ with $\left\| \mathbf{E} \right\| < 1/\left\| \mathbf{B}^{-1} \right\|$ leaves $\mathbf{B} + \mathbf{E}$ invertible.

B. Practice

Exercise (B1: Check, sum, compare)

Let $\mathbf{A} = \begin{pmatrix} 1/4 & 1/4 \\ 0 & 1/2 \end{pmatrix}$ .

(a) Verify the hypothesis of Theorem 16.5.1 for $\left\| \cdot \right\|_{\infty}$ .
(b) Compute $(\mathbf{I} - \mathbf{A})^{-1}$ exactly and compare $\left\| (\mathbf{I}-\mathbf{A})^{-1} \right\|_{\infty}$ with the bound of (b) and with the lower bound of (d).

Solution.

(a) The absolute row sums are $\tfrac12$ and $\tfrac12$ , so $\left\| \mathbf{A} \right\|_{\infty} = \tfrac12 < 1$ by Theorem 16.3.3 (b).
(b) $\mathbf{I} - \mathbf{A} = \begin{psmallmatrix} 3/4 & -1/4 \\ 0 & 1/2\end{psmallmatrix}$ , upper triangular with determinant $\tfrac38$ , so by Theorem 0.9.8 $(\mathbf{I}-\mathbf{A})^{-1} = \tfrac83\begin{pmatrix} 1/2 & 1/4 \\ 0 & 3/4\end{pmatrix} = \begin{pmatrix} 4/3 & 2/3 \\ 0 & 2 \end{pmatrix} .$ The absolute row sums are $2$ and $2$ , so $\left\| (\mathbf{I}-\mathbf{A})^{-1} \right\|_{\infty} = 2$ . The upper bound is $1/(1-\tfrac12) = 2$ , attained exactly; the lower bound is $1/(1+\tfrac12) = \tfrac23$ , comfortably satisfied. The upper bound is attained because both rows of $\mathbf{A}$ have the same absolute sum and no cancellation occurs anywhere in the geometric series.

Exercise (B2: A perturbed right-hand side)

Let $\mathbf{A} = \begin{pmatrix} 3 & 1 \\ 1 & 2\end{pmatrix}$ , $\mathbf{b} = (4, 3)$ and $\mathbf{f} = (1/10, 0)$ , with $\mathbf{E} = 0$ . Solve both systems, compute the relative error in the $\infty$ -norm, and compare with Theorem 16.5.3.

Solution. $\det \mathbf{A} = 5$ , so $\mathbf{A}^{-1} = \tfrac15\begin{psmallmatrix} 2 & -1 \\ -1 & 3\end{psmallmatrix}$ by Theorem 0.9.8, and $\mathbf{x} = \mathbf{A}^{-1}\mathbf{b} = \tfrac15(8 - 3, -4 + 9) = (1, 1)$ .

With $\mathbf{b} + \mathbf{f} = (\tfrac{41}{10}, 3)$ we get $\widetilde{\mathbf{x}} = \tfrac15(\tfrac{82}{10} - 3, -\tfrac{41}{10} + 9) = (\tfrac{52}{50}, \tfrac{49}{50})$ . Hence $\widetilde{\mathbf{x}} - \mathbf{x} = (\tfrac{2}{50}, -\tfrac{1}{50})$ and $\left\| \widetilde{\mathbf{x}} - \mathbf{x} \right\|_{\infty} = \tfrac1{25} = 0.04$ , a relative error of $0.04$ since $\left\| \mathbf{x} \right\|_{\infty} = 1$ .

For the bound: $\left\| \mathbf{A} \right\|_{\infty} = 4$ , $\left\| \mathbf{A}^{-1} \right\|_{\infty} = \tfrac45$ , so $\left\| \mathbf{A} \right\|_{\infty}\left\| \mathbf{A}^{-1} \right\|_{\infty} = \tfrac{16}{5}$ . Here $\mathbf{E} = 0$ , so $r = 0$ , and $\left\| \mathbf{f} \right\|_{\infty}/\left\| \mathbf{b} \right\|_{\infty} = \tfrac{1/10}{4} = \tfrac1{40}$ . The bound is $\tfrac{16}{5}\cdot\tfrac1{40} = \tfrac2{25} = 0.08$ . So $0.04 \le 0.08$ , loose by a factor of exactly $2$ .

Exercise (B3: Staying invertible)

Let $\mathbf{B} = \begin{pmatrix} 2 & 0 \\ 0 & 1/2 \end{pmatrix}$ . Using $\left\| \cdot \right\|_{\infty}$ , find a radius $\delta > 0$ such that every $\mathbf{E}$ with $\left\| \mathbf{E} \right\|_{\infty} < \delta$ leaves $\mathbf{B} + \mathbf{E}$ invertible, and bound $\left\| (\mathbf{B}+\mathbf{E})^{-1} \right\|_{\infty}$ for $\left\| \mathbf{E} \right\|_{\infty} \le \tfrac14$ . Is your $\delta$ the largest possible?

Solution. $\mathbf{B}^{-1} = \operatorname{diag}(\tfrac12, 2)$ , so $\left\| \mathbf{B}^{-1} \right\|_{\infty} = 2$ and Corollary 16.5.2 gives $\delta = 1/\left\| \mathbf{B}^{-1} \right\|_{\infty} = \tfrac12$ .

For $\left\| \mathbf{E} \right\|_{\infty} \le \tfrac14$ we get $r = 2\cdot\tfrac14 = \tfrac12$ , so part (a) of the corollary gives $\left\| (\mathbf{B}+\mathbf{E})^{-1} \right\|_{\infty} \le \frac{2}{1 - \tfrac12} = 4 .$

It is the largest possible here. Taking $\mathbf{E} = \operatorname{diag}(0, -\tfrac12)$ gives $\left\| \mathbf{E} \right\|_{\infty} = \tfrac12$ and $\mathbf{B} + \mathbf{E} = \operatorname{diag}(2, 0)$ , which is singular. So no radius larger than $\tfrac12$ works, and the estimate $1/\left\| \mathbf{B}^{-1} \right\|$ is attained by this $\mathbf{B}$ . (It is not attained by every $\mathbf{B}$ in every norm; Exercise (C2: Distance to the singular matrices) returns to this.)

C. Going deeper

Exercise (C1: The inverse to first order)

Let $\left\| \mathbf{A} \right\| < 1$ .

(a) Prove that $\left\| (\mathbf{I} - \mathbf{A})^{-1} - \mathbf{I} - \mathbf{A} \right\| \le \dfrac{\left\| \mathbf{A} \right\|^{2}}{1 - \left\| \mathbf{A} \right\|}$ .
(b) Deduce that for a fixed $\mathbf{M} \in M_n(\mathbb{C})$ and small real $t$ , $(\mathbf{I} - t\mathbf{M})^{-1} = \mathbf{I} + t\mathbf{M} + \mathbf{R}(t), \qquad \left\| \mathbf{R}(t) \right\|/\lvert t\rvert \to 0$ as $t \to 0$ .

Hint for (a): this is Theorem 16.5.1 (c) with a particular $K$ .

Solution.

(a) Take $K = 1$ in Theorem 16.5.1 (c): $\mathbf{S}_1 = \mathbf{I} + \mathbf{A}$ , so $\left\| (\mathbf{I}-\mathbf{A})^{-1} - \mathbf{I} - \mathbf{A} \right\| \le \frac{\left\| \mathbf{A} \right\|^{1+1}}{1 - \left\| \mathbf{A} \right\|} = \frac{\left\| \mathbf{A} \right\|^{2}}{1-\left\| \mathbf{A} \right\|} .$
(b) If $\mathbf{M} = 0$ the claim is trivial, so assume $\mathbf{M} \ne 0$ and let $\lvert t\rvert < 1/(2\left\| \mathbf{M} \right\|)$ . Then $\left\| t\mathbf{M} \right\| = \lvert t\rvert\left\| \mathbf{M} \right\| < \tfrac12$ , so (a) applies with $\mathbf{A} = t\mathbf{M}$ and gives, with $\mathbf{R}(t) = (\mathbf{I} - t\mathbf{M})^{-1} - \mathbf{I} - t\mathbf{M}$ , $\left\| \mathbf{R}(t) \right\| \le \frac{t^{2}\left\| \mathbf{M} \right\|^{2}}{1 - \lvert t\rvert\left\| \mathbf{M} \right\|} \le 2t^{2}\left\| \mathbf{M} \right\|^{2} ,$ using $1 - \lvert t\rvert\left\| \mathbf{M} \right\| > \tfrac12$ . Hence $\left\| \mathbf{R}(t) \right\|/\lvert t\rvert \le 2\lvert t\rvert\left\| \mathbf{M} \right\|^{2} \to 0$ as $t \to 0$ . So $t \mapsto (\mathbf{I} - t\mathbf{M})^{-1}$ is differentiable at $t = 0$ with derivative $\mathbf{M}$ , which is the case $\mathbf{A}(t) = \mathbf{I} - t\mathbf{M}$ of the general formula for differentiating an inverse, proved in §06.

Exercise (C2: Distance to the singular matrices)

Let $\mathbf{B} \in M_n(\mathbb{C})$ be invertible and let $\left\| \cdot \right\|$ be an induced matrix norm.

(a) Prove that every singular $\mathbf{S} \in M_n(\mathbb{C})$ satisfies $\left\| \mathbf{B} - \mathbf{S} \right\| \ge 1/\left\| \mathbf{B}^{-1} \right\|$ .
(b) For $\mathbf{B} = \operatorname{diag}(1, \varepsilon)$ with $0 < \varepsilon < 1$ and the $2$ -norm, exhibit a singular $\mathbf{S}$ attaining the bound.
(c) Hence say what $\left\| \mathbf{B}^{-1} \right\|_2$ measures.

Solution.

(a) Suppose $\left\| \mathbf{B} - \mathbf{S} \right\| < 1/\left\| \mathbf{B}^{-1} \right\|$ . Apply Corollary 16.5.2 with $\mathbf{E} = \mathbf{S} - \mathbf{B}$ : since $\left\| \mathbf{E} \right\| < 1/\left\| \mathbf{B}^{-1} \right\|$ , the matrix $\mathbf{B} + \mathbf{E} = \mathbf{S}$ is invertible, contradicting the assumption that $\mathbf{S}$ is singular. Hence $\left\| \mathbf{B} - \mathbf{S} \right\| \ge 1/\left\| \mathbf{B}^{-1} \right\|$ for every singular $\mathbf{S}$ .
(b) $\mathbf{B}^{-1} = \operatorname{diag}(1, 1/\varepsilon)$ , a normal matrix, so its singular values are the moduli of its eigenvalues and $\left\| \mathbf{B}^{-1} \right\|_2 = 1/\varepsilon$ by Theorem 16.3.3 (c). The bound is therefore $\varepsilon$ . Take $\mathbf{S} = \operatorname{diag}(1, 0)$ , which is singular; then $\mathbf{B} - \mathbf{S} = \operatorname{diag}(0, \varepsilon)$ and $\left\| \mathbf{B} - \mathbf{S} \right\|_2 = \varepsilon$ . So the bound is attained.
(c) The reciprocal $1/\left\| \mathbf{B}^{-1} \right\|_2$ is a lower bound for the distance from $\mathbf{B}$ to the singular matrices, attained in the example. So $\left\| \mathbf{B}^{-1} \right\|_2$ is large exactly when $\mathbf{B}$ is close to being singular, which is the geometric content behind the condition number of §08.

Exercise (C3: Without

\left\| \mathbf{I} \right\| = 1

)

Let $\left\| \cdot \right\|$ be any matrix norm on $M_n(\mathbb{C})$ in the sense of Definition 16.3.1, not necessarily induced, and let $\left\| \mathbf{A} \right\| < 1$ .

(a) Prove that $\mathbf{I} - \mathbf{A}$ is invertible and that $\left\| (\mathbf{I}-\mathbf{A})^{-1} \right\| \le \left\| \mathbf{I} \right\| + \frac{\left\| \mathbf{A} \right\|}{1 - \left\| \mathbf{A} \right\|} .$
(b) Verify that this bound is correct for the Frobenius norm on $M_2(\mathbb{C})$ with $\mathbf{A} = 0$ , where the bound of Theorem 16.5.1 (b) fails.
(c) Explain why the argument of (a) cannot be improved to $1/(1 - \left\| \mathbf{A} \right\|)$ for a general matrix norm.

Solution.

(a) By Theorem 16.4.1 (b), which holds for every matrix norm, $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\| < 1$ ; so Theorem 10.10.6 applies and gives both the invertibility of $\mathbf{I} - \mathbf{A}$ and $\mathbf{S}_K \to (\mathbf{I}-\mathbf{A})^{-1}$ . Submultiplicativity gives $\left\| \mathbf{A}^{k} \right\| \le \left\| \mathbf{A} \right\|^{k}$ for $k \ge 1$ , so separating the term $k = 0$ , $\left\| \mathbf{S}_K \right\| \le \left\| \mathbf{I} \right\| + \sum_{k=1}^{K}\left\| \mathbf{A} \right\|^{k} \le \left\| \mathbf{I} \right\| + \frac{\left\| \mathbf{A} \right\|}{1 - \left\| \mathbf{A} \right\|} .$ As in the proof of Theorem 16.5.1 (b), Corollary 16.2.4 and Lemma 16.1.1 let the bound pass to the limit.
(b) With $\mathbf{A} = 0$ , the right-hand side is $\left\| \mathbf{I}_2 \right\|_F + 0 = \sqrt2$ , and the left-hand side is $\left\| \mathbf{I}_2 \right\|_F = \sqrt2$ . The bound holds, with equality; the bound $1/(1-0) = 1$ of Theorem 16.5.1 (b) does not.
(c) The case $\mathbf{A} = 0$ already decides it: the left-hand side is $\left\| \mathbf{I} \right\|$ , so any valid bound must be at least $\left\| \mathbf{I} \right\|$ , and $1/(1 - \left\| \mathbf{A} \right\|) = 1$ there. A norm with $\left\| \mathbf{I} \right\| > 1$ therefore falsifies the sharper form at once, and by Theorem 16.3.2 (c) an induced norm never has $\left\| \mathbf{I} \right\| > 1$ . This is exactly the difference between a matrix norm and an induced one.