17.9 The Same Theory for Singular Values

Everything so far in this chapter has been about Hermitian matrices, and it had to be: a general square matrix need not have real eigenvalues to order, and a rectangular matrix has none at all. But every matrix has singular values, they are real and nonnegative, and Chapter 13 listed them decreasingly from the moment it defined them. This section carries the apparatus across — a min–max description, a perturbation bound, an interlacing theorem — and then spends the rest of its length paying debts that earlier chapters recorded and could not settle.

Throughout, $F = \mathbb{R}$ or $F = \mathbb{C}$ , $\mathbf{A} \in M_{m \times n}(F)$ , $p = \min(m, n)$ , and $\sigma_1(\mathbf{A}) \ge \dots \ge \sigma_p(\mathbf{A}) \ge 0$ are the singular values of $\mathbf{A}$ (Definition 13.9.1). Nothing here is assumed Hermitian and nothing is assumed square; where a matrix must be square, or invertible, the statement says so. Vector norms are Euclidean, and $\left\| \mathbf{A} \right\|_2$ is the spectral norm of Definition 16.3.2, which Theorem 16.3.3 (c) computes as $\sigma_1(\mathbf{A})$ .

One convention, stated once and used everywhere below. We set $\sigma_i(\mathbf{A}) \mathrel{:=} 0 \qquad \text{for } p < i \le n .$ This is not new: Theorem 13.9.2 (a) already makes it, and records what it buys. With it in force, if $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ is a singular value decomposition (Theorem 13.9.1) with columns $\mathbf{v}_1, \dots, \mathbf{v}_n$ of $\mathbf{V}$ , then

\mathbf{A}^{*}\mathbf{A}\,\mathbf{v}_i = \sigma_i(\mathbf{A})^2\,\mathbf{v}_i \qquad (1 \le i \le n),

(17.9.1)

so that $\mathbf{v}_1, \dots, \mathbf{v}_n$ is an orthonormal eigenbasis of $\mathbf{A}^{*}\mathbf{A}$ whose eigenvalues $\sigma_1^2 \ge \dots \ge \sigma_n^2 \ge 0$ are already sorted. In the notation of this chapter, $\lambda_i(\mathbf{A}^{*}\mathbf{A}) = \sigma_i(\mathbf{A})^2 \qquad (1 \le i \le n) .$ Every statement in this section is that identity, pushed through a theorem about Hermitian matrices.

17.9.1. The stretch ratio is a Rayleigh quotient

Chapter 13 introduced the singular values by an algebraic route — take $\mathbf{A}^{*}\mathbf{A}$ , diagonalize it, take square roots. Their geometric meaning is stretching: how much longer $\mathbf{A}\mathbf{x}$ is than $\mathbf{x}$ . The bridge between the two descriptions is one line of algebra, and it is the only computation this section needs before the theorems start.

For $\mathbf{x} \ne \mathbf{0}$ in $F^n$ , the matrix $\mathbf{A}^{*}\mathbf{A}$ is Hermitian, so its Rayleigh quotient (Definition 17.1.1) is defined, and

R_{\mathbf{A}^{*}\mathbf{A}}(\mathbf{x}) = \frac{\langle \mathbf{A}^{*}\mathbf{A}\mathbf{x}, \mathbf{x} \rangle}{\langle \mathbf{x}, \mathbf{x} \rangle} = \frac{\mathbf{x}^{*}\mathbf{A}^{*}\mathbf{A}\mathbf{x}}{\mathbf{x}^{*}\mathbf{x}} = \frac{(\mathbf{A}\mathbf{x})^{*}(\mathbf{A}\mathbf{x})}{\mathbf{x}^{*}\mathbf{x}} = \frac{\left\| \mathbf{A}\mathbf{x} \right\|^2}{\left\| \mathbf{x} \right\|^2} .

(17.9.2)

The Rayleigh quotient of $\mathbf{A}^{*}\mathbf{A}$ is the squared stretching factor of $\mathbf{A}$ .

So a statement about the Rayleigh quotient of $\mathbf{A}^{*}\mathbf{A}$ is a statement about the function $\mathbf{x} \mapsto \left\| \mathbf{A}\mathbf{x} \right\|/\left\| \mathbf{x} \right\|$ , and conversely. Nothing is lost in passing between them, because $t \mapsto \sqrt t$ is a strictly increasing bijection of $[0, \infty)$ onto itself: it carries maxima to maxima and minima to minima, over any set whatever.

Before the min–max theorem, it is worth writing down what the singular value decomposition says about this function in coordinates. The computation is three lines, and it is used four times below — for the witness subspaces in every proof of the section — so it gets a label.

Lemma 17.9.1 (Stretching in the Right Singular Basis)

Let $\mathbf{A} \in M_{m \times n}(F)$ have a singular value decomposition $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ (Theorem 13.9.1), with $\mathbf{v}_1, \dots, \mathbf{v}_n$ the columns of $\mathbf{V}$ , and write $\sigma_i = \sigma_i(\mathbf{A})$ with the convention above. Then for $\mathbf{x} = \sum_{i=1}^{n} c_i\mathbf{v}_i$ , $\left\| \mathbf{A}\mathbf{x} \right\|^2 = \sum_{i=1}^{n}\sigma_i^2\,\lvert c_i\rvert^2 , \qquad \left\| \mathbf{x} \right\|^2 = \sum_{i=1}^{n}\lvert c_i\rvert^2 .$ Consequently, for each $1 \le k \le n$ :

(a) on the tail subspace $T_k = \operatorname{span}(\mathbf{v}_k, \dots, \mathbf{v}_n)$ , of dimension $n - k + 1$ , $\max\Bigl\{\tfrac{\left\| \mathbf{A}\mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} : \mathbf{0} \ne \mathbf{x} \in T_k\Bigr\} = \sigma_k ,$ attained at $\mathbf{x} = \mathbf{v}_k$ ;
(b) on the head subspace $H_k = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ , of dimension $k$ , $\min\Bigl\{\tfrac{\left\| \mathbf{A}\mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} : \mathbf{0} \ne \mathbf{x} \in H_k\Bigr\} = \sigma_k ,$ attained at $\mathbf{x} = \mathbf{v}_k$ .

Idea. In the right singular basis $\mathbf{A}$ does nothing but scale: it sends $\mathbf{v}_i$ to $\sigma_i\mathbf{u}_i$ , and the $\mathbf{u}_i$ are orthonormal. So measuring $\mathbf{A}\mathbf{x}$ is Pythagoras applied to the scaled coordinates, and every claim about how much $\mathbf{A}$ can stretch a subspace becomes a claim about a weighted sum of $\lvert c_i\rvert^2$ .

Proof. By Eq. 17.9.1 the list $(\mathbf{v}_1, \dots, \mathbf{v}_n)$ is an orthonormal basis of $F^n$ consisting of eigenvectors of $\mathbf{A}^{*}\mathbf{A}$ , with $\mathbf{A}^{*}\mathbf{A}\mathbf{v}_i = \sigma_i^2\mathbf{v}_i$ . Hence, for $\mathbf{x} = \sum_i c_i\mathbf{v}_i$ , using Eq. 17.9.2 in the form $\left\| \mathbf{A}\mathbf{x} \right\|^2 = \mathbf{x}^{*}\mathbf{A}^{*}\mathbf{A}\mathbf{x}$ and expanding with orthonormality, $\left\| \mathbf{A}\mathbf{x} \right\|^2 = \Bigl(\sum_i c_i\mathbf{v}_i\Bigr)^{*}\Bigl(\sum_j c_j\sigma_j^2\mathbf{v}_j\Bigr) = \sum_{i=1}^{n}\sigma_i^2\lvert c_i\rvert^2 ,$ the cross terms vanishing because $\mathbf{v}_i^{*}\mathbf{v}_j = \delta_{ij}$ . The second identity is the same expansion with $\mathbf{A}$ removed.

(a) For $\mathbf{0} \ne \mathbf{x} \in T_k$ we have $c_i = 0$ for $i < k$ , so $\left\| \mathbf{A}\mathbf{x} \right\|^2 = \sum_{i \ge k}\sigma_i^2\lvert c_i\rvert^2 \le \sigma_k^2\sum_{i\ge k}\lvert c_i\rvert^2 = \sigma_k^2\left\| \mathbf{x} \right\|^2$ , since $\sigma_i \le \sigma_k$ for $i \ge k$ and the singular values are nonnegative. Taking square roots gives $\left\| \mathbf{A}\mathbf{x} \right\|/\left\| \mathbf{x} \right\| \le \sigma_k$ , and $\mathbf{x} = \mathbf{v}_k$ gives $\left\| \mathbf{A}\mathbf{v}_k \right\| = \sigma_k = \sigma_k\left\| \mathbf{v}_k \right\|$ , so the bound is attained.
(b) For $\mathbf{0} \ne \mathbf{x} \in H_k$ we have $c_i = 0$ for $i > k$ , so $\left\| \mathbf{A}\mathbf{x} \right\|^2 = \sum_{i \le k}\sigma_i^2\lvert c_i\rvert^2 \ge \sigma_k^2\left\| \mathbf{x} \right\|^2$ , since now $\sigma_i \ge \sigma_k$ for $i \le k$ ; and $\mathbf{x} = \mathbf{v}_k$ attains equality. This proves the lemma.

In words: the tail subspace is a place where $\mathbf{A}$ stretches no more than $\sigma_k$ , and the head subspace is a place where it stretches no less. The min–max theorem says that these two subspaces are optimal.

17.9.2. Each singular value as an optimization

Theorem 17.9.2 (Min–Max for Singular Values)

Let $\mathbf{A} \in M_{m \times n}(F)$ and let $1 \le k \le n$ , with $\sigma_k(\mathbf{A}) = 0$ read by convention when $k > p$ . Then $\begin{aligned} \sigma_k(\mathbf{A}) &= \min_{\substack{W \le F^n \\ \dim W = n-k+1}}\ \max_{\mathbf{0} \ne \mathbf{x} \in W}\ \frac{\left\| \mathbf{A}\mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \\ &= \max_{\substack{W \le F^n \\ \dim W = k}}\ \min_{\mathbf{0} \ne \mathbf{x} \in W}\ \frac{\left\| \mathbf{A}\mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} . \end{aligned}$ The outer minimum is attained at $W = \operatorname{span}(\mathbf{v}_k, \dots, \mathbf{v}_n)$ and the outer maximum at $W = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ , for the right singular vectors of any singular value decomposition of $\mathbf{A}$ (Theorem 13.9.1).

Idea. There is nothing to discover: Eq. 17.9.2 turns the objective function into the Rayleigh quotient of the Hermitian matrix $\mathbf{A}^{*}\mathbf{A}$ , Theorem 17.2.3 applies to that matrix, and the square root — increasing, hence order-preserving — moves through the minima and maxima without changing which subspace attains them.

Proof. Put $\mathbf{B} = \mathbf{A}^{*}\mathbf{A} \in M_n(F)$ , which is Hermitian, and fix $1 \le k \le n$ . By Eq. 17.9.1, $\lambda_k(\mathbf{B}) = \sigma_k(\mathbf{A})^2$ . By Theorem 17.2.3 applied to $\mathbf{B}$ , $\sigma_k(\mathbf{A})^2 = \lambda_k(\mathbf{B}) = \min_{\dim W = n-k+1}\ \max_{\mathbf{0} \ne \mathbf{x} \in W} R_{\mathbf{B}}(\mathbf{x}) ,$ and by Eq. 17.9.2, $R_{\mathbf{B}}(\mathbf{x}) = \bigl(\left\| \mathbf{A}\mathbf{x} \right\|/\left\| \mathbf{x} \right\|\bigr)^2$ for every $\mathbf{x} \ne \mathbf{0}$ .

Fix a subspace $W$ . The function $\mathbf{x} \mapsto \left\| \mathbf{A}\mathbf{x} \right\|/\left\| \mathbf{x} \right\|$ takes only nonnegative values, and $t \mapsto t^2$ is strictly increasing on $[0, \infty)$ ; so a vector of $W$ maximizes $R_{\mathbf{B}}$ over $W$ exactly when it maximizes $\left\| \mathbf{A}\mathbf{x} \right\|/\left\| \mathbf{x} \right\|$ , and $\max_{\mathbf{0} \ne \mathbf{x} \in W} R_{\mathbf{B}}(\mathbf{x}) = \Bigl(\max_{\mathbf{0} \ne \mathbf{x} \in W}\frac{\left\| \mathbf{A}\mathbf{x} \right\|}{\left\| \mathbf{x} \right\|}\Bigr)^{2} .$ (Both maxima exist: by homogeneity the quotient may be taken over the unit sphere of $W$ , which is compact by fact (A3) of Chapter 16’s introduction, and the function is continuous, so the extreme value theorem — fact (A4) of Chapter 16’s introduction — applies. This is the same appeal Theorem 17.2.3 makes.) Taking square roots, and using once more that $t \mapsto \sqrt t$ is increasing, so that it commutes with a minimum over the family of subspaces, $\sigma_k(\mathbf{A}) = \sqrt{\lambda_k(\mathbf{B})} = \min_{\dim W = n-k+1}\ \max_{\mathbf{0} \ne \mathbf{x} \in W}\frac{\left\| \mathbf{A}\mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} .$ The max–min form follows from the second equality of Theorem 17.2.3 by the same two steps.

For the attainment claims, Lemma 17.9.1 (a) says that the tail subspace $T_k$ , of dimension $n-k+1$ , has inner maximum exactly $\sigma_k(\mathbf{A})$ , which is therefore the outer minimum; and part (b) says the head subspace $H_k$ , of dimension $k$ , has inner minimum exactly $\sigma_k(\mathbf{A})$ . This proves the theorem.

Two things are worth noticing. First, the subspaces $W$ live in $F^n$ , the domain, whatever $m$ is; the theorem compares two matrices with the same number of columns without caring how many rows they have. Second, the extremal subspaces are named, and they are spans of right singular vectors: the theorem is not only an identity but a recipe.

There is a second route to the same theorem, and it is worth recording because it converts a statement about a rectangular matrix into a statement about a Hermitian one, which is what the later chapters will want.

Proposition 17.9.3 (The Hermitian Dilation)

Let $\mathbf{A} \in M_{m \times n}(F)$ and put $\mathcal{H}(\mathbf{A}) \mathrel{:=} \begin{pmatrix} \mathbf{O} & \mathbf{A} \\ \mathbf{A}^{*} & \mathbf{O}\end{pmatrix} \in M_{m+n}(F) .$ Then $\mathcal{H}(\mathbf{A})$ is Hermitian, and its eigenvalues, with multiplicity, are $\sigma_1(\mathbf{A}), \dots, \sigma_p(\mathbf{A}), \ -\sigma_1(\mathbf{A}), \dots, -\sigma_p(\mathbf{A}), \ \underbrace{0, \dots, 0}_{m + n - 2p} .$

Idea. Guess the eigenvectors from the SVD. The pair $(\mathbf{u}_i, \mathbf{v}_i)$ , stacked, is sent by $\mathcal{H}(\mathbf{A})$ to $(\mathbf{A}\mathbf{v}_i, \mathbf{A}^{*}\mathbf{u}_i) = \sigma_i(\mathbf{u}_i, \mathbf{v}_i)$ ; flipping the sign of the second half flips the sign of the eigenvalue. That accounts for $2p$ orthonormal eigenvectors, and what is left over is a kernel whose dimension is a count.

Proof. Writing out the conjugate transpose block by block, $\mathcal{H}(\mathbf{A})^{*} = \begin{psmallmatrix} \mathbf{O} & (\mathbf{A}^{*})^{*} \\ \mathbf{A}^{*} & \mathbf{O}\end{psmallmatrix} = \mathcal{H}(\mathbf{A})$ , so $\mathcal{H}(\mathbf{A})$ is Hermitian.

Fix a singular value decomposition $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ (Theorem 13.9.1), with columns $\mathbf{u}_1, \dots, \mathbf{u}_m$ of $\mathbf{U}$ and $\mathbf{v}_1, \dots, \mathbf{v}_n$ of $\mathbf{V}$ . Since $\mathbf{V}^{*}\mathbf{v}_i = \mathbf{e}_i$ and $\boldsymbol{\Sigma}\mathbf{e}_i = \sigma_i\mathbf{e}_i$ for $i \le p$ while $\boldsymbol{\Sigma}\mathbf{e}_j = \mathbf{0}$ for $p < j \le n$ , and symmetrically for $\mathbf{A}^{*} = \mathbf{V}\boldsymbol{\Sigma}^{*}\mathbf{U}^{*}$ , $\mathbf{A}\mathbf{v}_i = \sigma_i\mathbf{u}_i, \quad \mathbf{A}^{*}\mathbf{u}_i = \sigma_i\mathbf{v}_i \ \ (i \le p), \qquad \mathbf{A}\mathbf{v}_j = \mathbf{0}, \quad \mathbf{A}^{*}\mathbf{u}_j = \mathbf{0} \ \ (j > p) .$ For $i \le p$ put $\mathbf{w}_i^{\pm} = \tfrac{1}{\sqrt2}\begin{pmatrix} \mathbf{u}_i \\ \pm\mathbf{v}_i\end{pmatrix} \in F^{m+n} .$ Then $\mathcal{H}(\mathbf{A})\mathbf{w}_i^{\pm} = \tfrac{1}{\sqrt2}\bigl(\pm\mathbf{A}\mathbf{v}_i,\ \mathbf{A}^{*}\mathbf{u}_i\bigr) = \tfrac{1}{\sqrt2}\bigl(\pm\sigma_i\mathbf{u}_i,\ \sigma_i\mathbf{v}_i\bigr) = \pm\sigma_i\,\mathbf{w}_i^{\pm}$ . Likewise $\mathcal{H}(\mathbf{A})(\mathbf{u}_j, \mathbf{0}) = (\mathbf{0}, \mathbf{A}^{*}\mathbf{u}_j) = \mathbf{0}$ for $j > p$ , and $\mathcal{H}(\mathbf{A})(\mathbf{0}, \mathbf{v}_j) = (\mathbf{A}\mathbf{v}_j, \mathbf{0}) = \mathbf{0}$ for $j > p$ .

These $2p + (m - p) + (n - p) = m + n$ vectors are orthonormal: the $\mathbf{w}_i^{\pm}$ are unit vectors because $\mathbf{u}_i$ and $\mathbf{v}_i$ are, and any two distinct vectors in the list pair to $0$ , since $(\mathbf{w}_i^{+})^{*}\mathbf{w}_i^{-} = \tfrac12(1 - 1) = 0$ and all other pairs have orthogonal $\mathbf{u}$ -parts or orthogonal $\mathbf{v}$ -parts. So they form an orthonormal eigenbasis of $F^{m+n}$ with the stated eigenvalues, which are therefore the eigenvalue list of $\mathcal{H}(\mathbf{A})$ with multiplicity. This proves the proposition.

Applying Theorem 17.2.3 to $\mathcal{H}(\mathbf{A})$ instead of $\mathbf{A}^{*}\mathbf{A}$ gives Theorem 17.9.2 again, with subspaces of $F^{m+n}$ in place of $F^{n}$ . We took the shorter road; the dilation is recorded because it turns any theorem about Hermitian eigenvalues into one about singular values, which Section 10’s exercises and Chapter 20 both exploit.

17.9.3. Perturbation, with no hypothesis at all

For Hermitian matrices, Corollary 17.3.6 says that $\lvert\lambda_i(\mathbf{A} + \mathbf{E}) - \lambda_i(\mathbf{A})\rvert \le \left\| \mathbf{E} \right\|_2$ — provided $\mathbf{A}$ and $\mathbf{E}$ are Hermitian. That proviso is not decoration: Chapter 16’s Example (A Jordan block’s eigenvalues move like $\varepsilon^{1/k}$ ) shows the conclusion failing spectacularly without it. The corresponding statement for singular values needs no proviso whatsoever.

Theorem 17.9.4 (Weyl’s Inequalities for Singular Values)

Let $\mathbf{A}, \mathbf{B} \in M_{m \times n}(F)$ and let $i, j \ge 1$ with $i + j - 1 \le n$ . Then $\sigma_{i+j-1}(\mathbf{A} + \mathbf{B}) \le \sigma_i(\mathbf{A}) + \sigma_j(\mathbf{B}) .$

Idea. Put $k = i + j - 1$ . The min–max form of Theorem 17.9.2 bounds $\sigma_k(\mathbf{A}+\mathbf{B})$ from above as soon as we produce one subspace of dimension $n - k + 1$ on which $\mathbf{A} + \mathbf{B}$ stretches by at most $\sigma_i(\mathbf{A}) + \sigma_j(\mathbf{B})$ . Each summand supplies a subspace where it is individually small — the tail subspaces of Lemma 17.9.1 — and the dimensions are chosen so that the two subspaces must overlap in something of the required size. On the overlap the triangle inequality finishes it.

Proof. Put $k = i + j - 1 \le n$ . Let $T = \operatorname{span}(\mathbf{v}_i, \dots, \mathbf{v}_n)$ for the right singular vectors of $\mathbf{A}$ and $T' = \operatorname{span}(\mathbf{v}_j', \dots, \mathbf{v}_n')$ for those of $\mathbf{B}$ , so that $\dim T = n - i + 1$ , $\dim T' = n - j + 1$ , and by Lemma 17.9.1 (a), $\left\| \mathbf{A}\mathbf{x} \right\| \le \sigma_i(\mathbf{A})\left\| \mathbf{x} \right\| \ \ (\mathbf{x} \in T), \qquad \left\| \mathbf{B}\mathbf{x} \right\| \le \sigma_j(\mathbf{B})\left\| \mathbf{x} \right\| \ \ (\mathbf{x} \in T') .$ By the dimension formula (Theorem 1.7.3) and $\dim(T + T') \le n$ , $\begin{aligned} \dim(T \cap T') &\ge (n - i + 1) + (n - j + 1) - n \\ &= n - (i + j - 1) + 1 = n - k + 1 , \end{aligned}$ which is at least $1$ because $k \le n$ . Choose a subspace $W \subseteq T \cap T'$ with $\dim W = n - k + 1$ exactly; this is possible because every subspace has a subspace of each smaller dimension, obtained by truncating a basis. For $\mathbf{0} \ne \mathbf{x} \in W$ , the triangle inequality (Corollary 11.1.6) gives $\left\| (\mathbf{A} + \mathbf{B})\mathbf{x} \right\| \le \left\| \mathbf{A}\mathbf{x} \right\| + \left\| \mathbf{B}\mathbf{x} \right\| \le \bigl(\sigma_i(\mathbf{A}) + \sigma_j(\mathbf{B})\bigr)\left\| \mathbf{x} \right\| .$ Hence the inner maximum over $W$ is at most $\sigma_i(\mathbf{A}) + \sigma_j(\mathbf{B})$ , and since $\sigma_k(\mathbf{A}+\mathbf{B})$ is the minimum of that inner maximum over all subspaces of dimension $n - k + 1$ (Theorem 17.9.2), we get $\sigma_k(\mathbf{A}+\mathbf{B}) \le \sigma_i(\mathbf{A}) + \sigma_j(\mathbf{B})$ . This proves the theorem.

Corollary 17.9.5 (Singular Values Are Perfectly Conditioned)

Let $\mathbf{A}, \mathbf{E} \in M_{m \times n}(F)$ . Then $\lvert\sigma_i(\mathbf{A} + \mathbf{E}) - \sigma_i(\mathbf{A})\rvert \le \left\| \mathbf{E} \right\|_2 \qquad\text{for every } 1 \le i \le n .$ No hypothesis is placed on $\mathbf{A}$ or on $\mathbf{E}$ .

Idea. Put $j = 1$ in the Weyl inequality for singular values: one index passes through unchanged, and the other matrix contributes only its largest singular value, which is $\left\| \mathbf{E} \right\|_2$ . That bounds $\sigma_i(\mathbf{A} + \mathbf{E})$ from above; writing $\mathbf{A} = (\mathbf{A} + \mathbf{E}) + (-\mathbf{E})$ and doing it again bounds it from below.

Proof. Take $j = 1$ in Theorem 17.9.4, so that $i + j - 1 = i \le n$ : $\sigma_i(\mathbf{A} + \mathbf{E}) \le \sigma_i(\mathbf{A}) + \sigma_1(\mathbf{E}) = \sigma_i(\mathbf{A}) + \left\| \mathbf{E} \right\|_2 ,$ using Theorem 16.3.3 (c) for the last equality. Now apply the same inequality with $\mathbf{A} + \mathbf{E}$ in place of $\mathbf{A}$ and $-\mathbf{E}$ in place of $\mathbf{E}$ , noting $\left\| -\mathbf{E} \right\|_2 = \left\| \mathbf{E} \right\|_2$ by homogeneity (Theorem 16.3.2 (b)): $\sigma_i(\mathbf{A}) = \sigma_i\bigl((\mathbf{A} + \mathbf{E}) + (-\mathbf{E})\bigr) \le \sigma_i(\mathbf{A} + \mathbf{E}) + \left\| \mathbf{E} \right\|_2 .$ The two inequalities together are the claim.

This is a Lipschitz bound with constant $1$ , exactly as Corollary 17.3.6 is for Hermitian eigenvalues, and with no dependence on $n$ , on the conditioning of $\mathbf{A}$ , or on the gaps between the singular values. What is new is the absence of hypotheses. It is worth seeing the contrast on the very matrix Chapter 16 used to show that eigenvalues have no such bound.

Example (The Jordan block again, measured by its singular values)

Let $k \ge 2$ , let $0 < \varepsilon < 1$ , and let $\mathbf{A} = \mathbf{J}_k(0), \qquad \mathbf{A}_{\varepsilon} = \mathbf{J}_k(0) + \varepsilon\mathbf{E}_{k1}$ be the matrices of Example (A Jordan block’s eigenvalues move like $\varepsilon^{1/k}$ ). Compute the singular values of both, and compare how far they move with how far the eigenvalues move.

Solution. The columns of $\mathbf{A}_{\varepsilon}$ are $\varepsilon\mathbf{e}_k$ in position $1$ , and $\mathbf{e}_{j-1}$ in position $j$ for $2 \le j \le k$ . These $k$ columns are pairwise orthogonal, with norms $\varepsilon, 1, \dots, 1$ , so $\mathbf{A}_{\varepsilon}^{*}\mathbf{A}_{\varepsilon} = \operatorname{diag}(\varepsilon^2, 1, \dots, 1) ,$ whose eigenvalues in decreasing order are $1$ with multiplicity $k-1$ and then $\varepsilon^2$ , since $\varepsilon < 1$ . By Definition 13.9.1 the singular values of $\mathbf{A}_{\varepsilon}$ are $\sigma_1 = \dots = \sigma_{k-1} = 1, \qquad \sigma_k = \varepsilon .$ Setting $\varepsilon = 0$ in the same computation, the singular values of $\mathbf{A} = \mathbf{J}_k(0)$ are $1, \dots, 1, 0$ .

So every singular value moves by at most $\varepsilon$ , and exactly one of them — the last — moves by exactly $\varepsilon$ . The perturbation has $\left\| \varepsilon\mathbf{E}_{k1} \right\|_2 = \varepsilon$ , computed in Example (A Jordan block’s eigenvalues move like $\varepsilon^{1/k}$ ), so Corollary 17.9.5 is attained here and not merely satisfied.

Meanwhile Example (A Jordan block’s eigenvalues move like $\varepsilon^{1/k}$ ) computed that the eigenvalues of the same two matrices are $0$ (with multiplicity $k$ ) and the $k$ -th roots of $\varepsilon$ , all of modulus $\varepsilon^{1/k}$ . For $k = 10$ and $\varepsilon = 10^{-10}$ : the singular values move by $10^{-10}$ , and the eigenvalues move by $10^{-1}$ , a factor of a billion more. The same matrix, the same perturbation, two spectra — one of them stable and one of them not.

This is not a paradox. The singular values of $\mathbf{A}$ are the square roots of the eigenvalues of the Hermitian matrix $\mathbf{A}^{*}\mathbf{A}$ , and Hermitian eigenvalues are stable; the eigenvalues of $\mathbf{A}$ itself are roots of a polynomial, and a repeated root is fragile. The instability lives in the passage from $\mathbf{A}$ to its eigenvalues, not in $\mathbf{A}$ — which is why a question that can be phrased in singular values should be.

Warning. Weyl’s inequality does not say $\sigma_k(\mathbf{A} + \mathbf{B}) \le \sigma_k(\mathbf{A}) + \sigma_k(\mathbf{B})$ . The index bookkeeping $i + j - 1$ is the content, not a technicality. Take $\mathbf{A} = \operatorname{diag}(1, 0), \qquad \mathbf{B} = \operatorname{diag}(0, 1) .$ Then $\sigma(\mathbf{A}) = \sigma(\mathbf{B}) = (1, 0)$ , while $\mathbf{A} + \mathbf{B} = \mathbf{I}_2$ has $\sigma(\mathbf{I}_2) = (1, 1)$ . So $\sigma_2(\mathbf{A} + \mathbf{B}) = 1$ while $\sigma_2(\mathbf{A}) + \sigma_2(\mathbf{B}) = 0$ . What Theorem 17.9.4 does give here, with $i = j = 1$ , is $\sigma_1(\mathbf{A} + \mathbf{B}) \le \sigma_1(\mathbf{A}) + \sigma_1(\mathbf{B}) = 2$ , which holds. Only $i = 1$ or $j = 1$ lets an index pass through unchanged, which is why Corollary 17.9.5 is the case $j = 1$ .

17.9.4. The best approximation of low rank

Chapter 13 §11 proved that the truncated singular value decomposition $\mathbf{A}_k$ of Definition 13.11.1 is the closest matrix of rank at most $k$ to $\mathbf{A}$ in the Frobenius norm (Theorem 13.11.3), and then wrote, in the remark that closes its main proof:

The same matrix $\mathbf{A}_k$ is also optimal in the spectral norm $\left\| \cdot \right\|_2$ , where the minimum value is $\sigma_{k+1}$ rather than $\bigl(\sum_{i>k}\sigma_i^2\bigr)^{1/2}$ . We cannot state that here, because the spectral norm is defined only in Chapter 16.

Chapter 16 supplied the norm and then, in its closing ledger, handed the theorem to this chapter: “the theorem itself waits for Chapter 17, which proves it from the min–max description of the singular values.” That description now exists. Here is the theorem.

Theorem 17.9.6 (Eckart–Young Theorem, Spectral Case)

Let $\mathbf{A} \in M_{m \times n}(F)$ and let $0 \le k < n$ . Then for every $\mathbf{B} \in M_{m \times n}(F)$ with $\operatorname{rank}\mathbf{B} \le k$ , $\left\| \mathbf{A} - \mathbf{B} \right\|_2 \ \ge\ \sigma_{k+1}(\mathbf{A}) ,$ and equality holds for the truncation $\mathbf{B} = \mathbf{A}_k$ of Definition 13.11.1. In words: $\mathbf{A}_k$ minimizes $\left\| \mathbf{A} - \mathbf{B} \right\|_2$ over all matrices of rank at most $k$ , and the minimum value is $\sigma_{k+1}(\mathbf{A})$ .

Idea. A matrix $\mathbf{B}$ of rank at most $k$ has a large null space — dimension at least $n - k$ — and on that null space $\mathbf{A} - \mathbf{B}$ acts exactly as $\mathbf{A}$ does. The head subspace $H_{k+1} = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{k+1})$ is a place where $\mathbf{A}$ stretches by at least $\sigma_{k+1}$ , and it has dimension $k+1$ . Two subspaces of $F^n$ of dimensions $n - k$ and $k+1$ cannot avoid each other, by Lemma 17.2.1, and a vector in both settles the matter in one line.

Proof. The lower bound. Let $\operatorname{rank}\mathbf{B} \le k$ . By Rank–Nullity for matrices (Theorem 3.5.7), $\dim\operatorname{nul}(\mathbf{B}) = n - \operatorname{rank}\mathbf{B} \ge n - k$ . Let $H = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{k+1})$ , where $\mathbf{v}_1, \dots, \mathbf{v}_n$ are the right singular vectors of a fixed singular value decomposition of $\mathbf{A}$ (Theorem 13.9.1); then $\dim H = k + 1$ . Since $\dim\operatorname{nul}(\mathbf{B}) + \dim H \ \ge\ (n - k) + (k + 1) = n + 1 > n ,$ Lemma 17.2.1 gives a vector $\mathbf{x} \ne \mathbf{0}$ with $\mathbf{x} \in \operatorname{nul}(\mathbf{B}) \cap H$ . For that $\mathbf{x}$ , $\mathbf{B}\mathbf{x} = \mathbf{0}$ , so $(\mathbf{A} - \mathbf{B})\mathbf{x} = \mathbf{A}\mathbf{x}$ , and by Lemma 17.9.1 (b) applied with $k + 1$ in place of $k$ , $\left\| (\mathbf{A} - \mathbf{B})\mathbf{x} \right\| = \left\| \mathbf{A}\mathbf{x} \right\| \ \ge\ \sigma_{k+1}(\mathbf{A})\,\left\| \mathbf{x} \right\| .$ Since $\mathbf{x} \ne \mathbf{0}$ , dividing by $\left\| \mathbf{x} \right\|$ and using Theorem 16.3.2 (a), which says $\left\| \mathbf{A} - \mathbf{B} \right\|_2$ is the largest such ratio, gives $\left\| \mathbf{A} - \mathbf{B} \right\|_2 \ge \sigma_{k+1}(\mathbf{A})$ .

Equality at the truncation. If $k \ge p$ , then $\mathbf{A}_k = \mathbf{A}$ by Definition 13.11.1 and $\sigma_{k+1}(\mathbf{A}) = 0$ by our convention, so equality holds trivially; assume $k < p$ . By Definition 13.11.1, $\mathbf{A}_k = \sum_{i\le k}\sigma_i\mathbf{u}_i\mathbf{v}_i^{*}$ has rank $\min(k, \operatorname{rank}\mathbf{A}) \le k$ , and $\mathbf{A} - \mathbf{A}_k = \sum_{i > k}\sigma_i\mathbf{u}_i\mathbf{v}_i^{*} = \mathbf{U}\boldsymbol{\Sigma}^{(k)}\mathbf{V}^{*} ,$ where $\boldsymbol{\Sigma}^{(k)}$ is $\boldsymbol{\Sigma}$ with its first $k$ diagonal entries replaced by $0$ . Since $\mathbf{U}$ is unitary, $(\mathbf{A} - \mathbf{A}_k)^{*}(\mathbf{A} - \mathbf{A}_k) = \mathbf{V}\,(\boldsymbol{\Sigma}^{(k)})^{*}\boldsymbol{\Sigma}^{(k)}\,\mathbf{V}^{*}$ , which is similar to the diagonal matrix $(\boldsymbol{\Sigma}^{(k)})^{*}\boldsymbol{\Sigma}^{(k)}$ ; its eigenvalues are therefore $\sigma_{k+1}^2, \dots, \sigma_p^2$ together with zeros. By Definition 13.9.1 the singular values of $\mathbf{A} - \mathbf{A}_k$ are $\sigma_{k+1} \ge \sigma_{k+2} \ge \dots$ followed by zeros, the largest being $\sigma_{k+1}$ . Hence $\left\| \mathbf{A} - \mathbf{A}_k \right\|_2 = \sigma_{k+1}(\mathbf{A})$ by Theorem 16.3.3 (c). This proves the theorem.

So the minimizer is the same matrix in both norms, and only the minimum value changes: $\sigma_{k+1}$ for the spectral norm, $\bigl(\sum_{i>k}\sigma_i^2\bigr)^{1/2}$ for the Frobenius norm. That the same $\mathbf{A}_k$ works for both is not a coincidence — it is optimal in every unitarily invariant norm at once, which is Chapter 21’s theorem and needs machinery neither this section nor Chapter 13 has.

Example (One matrix, two norms)

Let $\mathbf{A} = \begin{pmatrix} 3 & 1 & 0 \\ 1 & 3 & 0 \\ 0 & 0 & 1 \end{pmatrix} \in M_3(\mathbb{R}) .$ Find the best approximations of rank $1$ and rank $2$ , and compute the error in both the spectral and the Frobenius norm.

Solution. $\mathbf{A}$ is symmetric and block diagonal. The $2 \times 2$ block $\begin{psmallmatrix} 3 & 1 \\ 1 & 3\end{psmallmatrix}$ has trace $6$ and determinant $8$ , hence eigenvalues $4$ and $2$ , with orthonormal eigenvectors $\tfrac{1}{\sqrt2}(1,1)$ and $\tfrac{1}{\sqrt2}(1,-1)$ ; the third eigenvalue is $1$ , with eigenvector $\mathbf{e}_3$ . All three eigenvalues are positive, so $\mathbf{A} \succ \mathbf{O}$ and its singular values are those eigenvalues (Theorem 13.1.5; $\mathbf{A}^{*}\mathbf{A} = \mathbf{A}^2$ has eigenvalues their squares): $\sigma_1 = 4, \quad \sigma_2 = 2, \quad \sigma_3 = 1,$ with $\mathbf{u}_i = \mathbf{v}_i$ the unit eigenvectors $\tfrac{1}{\sqrt2}(1,1,0)$ , $\tfrac{1}{\sqrt2}(1,-1,0)$ , $\mathbf{e}_3$ .

Truncating, $\mathbf{A}_1 = 4\mathbf{v}_1\mathbf{v}_1^{\top} = \begin{pmatrix} 2 & 2 & 0 \\ 2 & 2 & 0 \\ 0 & 0 & 0\end{pmatrix}, \qquad \mathbf{A}_2 = \begin{pmatrix} 3 & 1 & 0 \\ 1 & 3 & 0 \\ 0 & 0 & 0\end{pmatrix},$ the second because $4\mathbf{v}_1\mathbf{v}_1^{\top} + 2\mathbf{v}_2\mathbf{v}_2^{\top}$ restores the $2\times2$ block exactly. The error matrices are $\mathbf{A} - \mathbf{A}_1 = \begin{pmatrix} 1 & -1 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}, \qquad \mathbf{A} - \mathbf{A}_2 = \operatorname{diag}(0,0,1) .$ For $k = 1$ : $\left\| \mathbf{A} - \mathbf{A}_1 \right\|_2 = \sigma_2 = 2$ and $\left\| \mathbf{A} - \mathbf{A}_1 \right\|_F = \sqrt{\sigma_2^2 + \sigma_3^2} = \sqrt5 \approx 2.236$ . Check the first directly: $\mathbf{A} - \mathbf{A}_1$ is symmetric with the $2\times2$ block $\begin{psmallmatrix} 1 & -1 \\ -1 & 1\end{psmallmatrix}$ , of eigenvalues $2$ and $0$ , and the entry $1$ , so its largest eigenvalue in modulus is $2$ . Check the second directly: the sum of the squares of the five nonzero entries is $4 \cdot 1 + 1 = 5$ .

For $k = 2$ : both norms of $\operatorname{diag}(0,0,1)$ equal $1 = \sigma_3$ , and the two formulas agree because only one singular value is discarded.

Quick check. A matrix has singular values $6, 3, 2, 1$ . What is the smallest spectral-norm error of a rank- $2$ approximation, and how does it compare with the Frobenius-norm error found in Exercise (B1: Errors from the singular values alone)?

Solution. By Theorem 17.9.6 with $k = 2$ , the minimum is $\sigma_3 = 2$ . By Theorem 13.11.3 the Frobenius minimum is $\sqrt{\sigma_3^2 + \sigma_4^2} = \sqrt5 \approx 2.236$ . The Frobenius error is the larger of the two, as it must be: it counts every discarded singular value, while the spectral error counts only the largest one.

17.9.5. How far an invertible matrix is from being singular

Take $k = n - 1$ in Theorem 17.9.6, with $\mathbf{A}$ square. A matrix of rank at most $n-1$ is precisely a singular matrix, so the theorem computes the distance from $\mathbf{A}$ to the set of singular matrices. That is the geometric content of Chapter 16’s condition number, and it is the best payoff in this chapter.

Corollary 17.9.7 (The Distance to Singularity)

Let $\mathbf{A} \in M_n(F)$ be invertible. Then $\min\bigl\{\left\| \mathbf{A} - \mathbf{B} \right\|_2 : \mathbf{B} \in M_n(F) \text{ singular}\bigr\} = \sigma_n(\mathbf{A}) = \frac{1}{\left\| \mathbf{A}^{-1} \right\|_2} ,$ the minimum being attained at $\mathbf{B} = \mathbf{A}_{n-1}$ . Consequently the relative distance from $\mathbf{A}$ to the nearest singular matrix is $\frac{\min\{\left\| \mathbf{A} - \mathbf{B} \right\|_2 : \mathbf{B} \text{ singular}\}}{\left\| \mathbf{A} \right\|_2} = \frac{\sigma_n(\mathbf{A})}{\sigma_1(\mathbf{A})} = \frac{1}{\kappa_2(\mathbf{A})} ,$ the reciprocal of the spectral condition number of Definition 16.8.1.

Idea. A singular matrix has rank at most $n - 1$ , so this is the spectral Eckart–Young theorem with $k = n - 1$ , and the answer is the next singular value, $\sigma_n$ . The formula $1/\left\| \mathbf{A}^{-1} \right\|_2$ is the same number read through the inverse, whose largest singular value is $1/\sigma_n$ .

Proof. A matrix $\mathbf{B} \in M_n(F)$ is singular if and only if $\operatorname{rank}\mathbf{B} \le n - 1$ (Theorem 7.5.3 (d)). So the set over which the minimum is taken is exactly the set appearing in Theorem 17.9.6 with $k = n - 1$ , and that theorem gives the value $\sigma_{(n-1)+1}(\mathbf{A}) = \sigma_n(\mathbf{A})$ , attained at $\mathbf{A}_{n-1}$ . The matrix $\mathbf{A}_{n-1}$ is singular because its rank is $\min(n-1, \operatorname{rank}\mathbf{A}) = n - 1 < n$ .

For the second expression: since $\operatorname{rank}\mathbf{A} = n$ , exactly $n$ singular values of $\mathbf{A}$ are nonzero (Theorem 13.9.1), so $\sigma_n(\mathbf{A}) > 0$ . By Definition 16.8.1 and Proposition 16.8.2 (d), $\left\| \mathbf{A} \right\|_2\left\| \mathbf{A}^{-1} \right\|_2 = \kappa_2(\mathbf{A}) = \sigma_1(\mathbf{A})/\sigma_n(\mathbf{A})$ , and $\left\| \mathbf{A} \right\|_2 = \sigma_1(\mathbf{A})$ by Theorem 16.3.3 (c); dividing, $\left\| \mathbf{A}^{-1} \right\|_2 = 1/\sigma_n(\mathbf{A})$ . Dividing the minimum $\sigma_n(\mathbf{A})$ by $\left\| \mathbf{A} \right\|_2 = \sigma_1(\mathbf{A})$ gives $\sigma_n/\sigma_1 = 1/\kappa_2(\mathbf{A})$ , the last display. This proves the corollary.

What this settles. Chapter 16 defined $\kappa(\mathbf{A}) = \left\| \mathbf{A} \right\|\left\| \mathbf{A}^{-1} \right\|$ as the worst factor by which $\mathbf{A}$ magnifies a relative error, proved that the factor is attained, and described it geometrically through Lemma 16.8.1 as the ratio of the largest to the smallest stretch $\left\| \mathbf{A}\mathbf{x} \right\|$ over unit vectors $\mathbf{x}$ . That is a statement about what $\mathbf{A}$ does. Corollary 17.9.7 is a statement about where $\mathbf{A}$ is: it says that $1/\kappa_2(\mathbf{A})$ measures the distance from $\mathbf{A}$ to the boundary of the invertible matrices, relative to the size of $\mathbf{A}$ . A matrix with $\kappa_2 = 10^6$ is not merely a matrix that magnifies errors by a million; it is a matrix that a relative perturbation of one part in a million can make singular. “Ill-conditioned” and “nearly singular” are the same property, and this is the theorem that identifies them.

Two earlier exercises reached for this. Exercise (C1: How far is a matrix from being singular?) found the same distance in the Frobenius norm — also $\sigma_n$ , since only one singular value is discarded when $k = n-1$ . Exercise (C2: The condition number is the reciprocal distance to singularity) obtained the spectral statement by hand, with a Neumann-series lower bound and the truncation as witness. Nothing above rests on either. What is new is that the distance to singularity is now the case $k = n-1$ of one theorem covering every rank, proved by a dimension count and stated as an attained minimum.

Example (The nearest singular matrix, exactly and approximately)

(a) For the matrix $\mathbf{A}$ of Example (One matrix, two norms), find the nearest singular matrix and the relative distance to it.
(b) Do the same, to three significant figures, for $\mathbf{C} = \begin{psmallmatrix} 1 & 1 \\ 1 & 1.01\end{psmallmatrix}$ , the ill-conditioned matrix of Example (A system where the bound is attained).

Solution.

(a) The singular values are $4, 2, 1$ , so by Corollary 17.9.7 the nearest singular matrix is at distance $\sigma_3 = 1$ , and it is $\mathbf{A}_2 = \begin{pmatrix} 3 & 1 & 0 \\ 1 & 3 & 0 \\ 0 & 0 & 0\end{pmatrix},$ computed in Example (One matrix, two norms); it is singular because its last row is zero. Here $\kappa_2(\mathbf{A}) = 4/1 = 4$ , so the relative distance is $\tfrac14$ : a perturbation of a quarter of the size of $\mathbf{A}$ is needed, and $\mathbf{A}$ is very well conditioned.
(b) $\mathbf{C}$ is symmetric with $\operatorname{tr}\mathbf{C} = \tfrac{201}{100}$ and $\det\mathbf{C} = \tfrac{1}{100}$ , so its eigenvalues are $\frac{201 \pm \sqrt{201^2 - 400}}{200} = \frac{201 \pm \sqrt{40001}}{200} ,$ both positive, hence equal to the singular values: $\sigma_1 \approx 2.00501$ and $\sigma_2 \approx 0.0049875$ . So $\kappa_2(\mathbf{C}) \approx 402.0$ and the nearest singular matrix is at distance $\sigma_2 \approx 0.00499$ , a relative distance of $1/\kappa_2(\mathbf{C}) \approx 0.00249$ , about a quarter of one percent. The nearest singular matrix itself is $\mathbf{C}_1 = \sigma_1\mathbf{v}_1\mathbf{v}_1^{\top}$ , which to five decimals is $\mathbf{C}_1 \approx \begin{pmatrix} 0.99749 & 1.00249 \\ 1.00249 & 1.00752 \end{pmatrix} ;$ it is singular, and each entry differs from the corresponding entry of $\mathbf{C}$ by about $0.0025$ . Changing $\mathbf{C}$ in its third decimal place destroys its invertibility. That is what $\kappa_2 \approx 402$ means.

Warning. The distance to singularity is not measured by the determinant. Chapter 16 §08 warned that no threshold on $\lvert\det\mathbf{A}\rvert$ detects ill-conditioning, and Corollary 17.9.7 says exactly why: the quantity that decides nearness to singularity is $\sigma_n$ , and $\lvert\det\mathbf{A}\rvert = \sigma_1\sigma_2\cdots\sigma_n$ is a product in which a tiny $\sigma_n$ can be hidden by large partners, or a healthy $\sigma_n$ buried by many small ones. For $\mathbf{A} = 10^{-6}\mathbf{I}_{10}$ all singular values are $10^{-6}$ , so $\lvert\det\mathbf{A}\rvert = 10^{-60}$ while the relative distance to singularity is $1/\kappa_2 = 1$ , the largest it can ever be. For $\mathbf{A} = \operatorname{diag}(10^{6}, 10^{-6})$ , $\lvert\det\mathbf{A}\rvert = 1$ while the relative distance is $10^{-12}$ . Only the smallest singular value knows.

17.9.6. Deleting a row

The last transfer is Cauchy interlacing. For a Hermitian matrix the operation was deleting a row and the matching column; for a general matrix there is no matching, and deleting a single row is enough.

Theorem 17.9.8 (Interlacing Under Deletion of a Row or a Column)

Let $\mathbf{A} \in M_{m \times n}(F)$ with $m \ge 2$ , and let $\mathbf{B} \in M_{(m-1)\times n}(F)$ be obtained from $\mathbf{A}$ by deleting one row. Then $\sigma_i(\mathbf{B}) \le \sigma_i(\mathbf{A}) \quad (1 \le i \le n), \qquad \sigma_{i+1}(\mathbf{A}) \le \sigma_i(\mathbf{B}) \quad (1 \le i \le n-1) ,$ singular values beyond the $p$ -th being read as $0$ . If instead $n \ge 2$ and $\mathbf{B} \in M_{m\times(n-1)}(F)$ is obtained from $\mathbf{A}$ by deleting one column, the same two chains hold, both over $1 \le i \le n-1$ ; written out, $\sigma_1(\mathbf{A}) \ge \sigma_1(\mathbf{B}) \ge \sigma_2(\mathbf{A}) \ge \dots \ge \sigma_{n-1}(\mathbf{B}) \ge \sigma_n(\mathbf{A})$ .

Idea. Deleting a row removes one term from the sum $\left\| \mathbf{A}\mathbf{x} \right\|^2 = \sum_{\text{rows}} \lvert\text{row} \cdot \mathbf{x}\rvert^2$ . So $\left\| \mathbf{B}\mathbf{x} \right\| \le \left\| \mathbf{A}\mathbf{x} \right\|$ for every $\mathbf{x}$ , which gives the first chain from the min–max formula at once, because both matrices are compared over the same subspaces of $F^n$ . For the second chain, the two norms agree on the hyperplane where the deleted row vanishes; intersecting a good subspace for $\mathbf{B}$ with that hyperplane costs one dimension, and one dimension is exactly one index.

Proof. Say row $r$ of $\mathbf{A}$ is deleted, and write $\mathbf{r}^{*} \in M_{1\times n}(F)$ for that row. Summing squares of entries coordinate by coordinate,

\left\| \mathbf{A}\mathbf{x} \right\|^2 = \left\| \mathbf{B}\mathbf{x} \right\|^2 + \lvert\mathbf{r}^{*}\mathbf{x}\rvert^2 \qquad (\mathbf{x} \in F^n) ,

(17.9.3)

since the entries of $\mathbf{A}\mathbf{x}$ are those of $\mathbf{B}\mathbf{x}$ together with $\mathbf{r}^{*}\mathbf{x}$ .

First chain. By Eq. 17.9.3, $\left\| \mathbf{B}\mathbf{x} \right\|/\left\| \mathbf{x} \right\| \le \left\| \mathbf{A}\mathbf{x} \right\|/\left\| \mathbf{x} \right\|$ for every $\mathbf{x} \ne \mathbf{0}$ . Both $\mathbf{A}$ and $\mathbf{B}$ have $n$ columns, so Theorem 17.9.2 describes $\sigma_i(\mathbf{A})$ and $\sigma_i(\mathbf{B})$ as a minimum over the same family of subspaces of $F^n$ , of a maximum of these two objective functions. A pointwise smaller function has a smaller maximum on each subspace and hence a smaller minimum over the family, so $\sigma_i(\mathbf{B}) \le \sigma_i(\mathbf{A})$ for every $i \le n$ .

Second chain. Fix $1 \le i \le n - 1$ . Let $\mathbf{w}_1, \dots, \mathbf{w}_n$ be the right singular vectors of a singular value decomposition of $\mathbf{B}$ (Theorem 13.9.1), and put $T = \operatorname{span}(\mathbf{w}_i, \dots, \mathbf{w}_n)$ , of dimension $n - i + 1$ ; by Lemma 17.9.1 (a) applied to $\mathbf{B}$ , $\left\| \mathbf{B}\mathbf{x} \right\| \le \sigma_i(\mathbf{B})\left\| \mathbf{x} \right\| \qquad (\mathbf{x} \in T) .$ Let $H = \{\mathbf{x} \in F^n : \mathbf{r}^{*}\mathbf{x} = 0\} = \operatorname{nul}(\mathbf{r}^{*})$ . Since $\mathbf{r}^{*}$ has at most one nonzero row, $\operatorname{rank}\mathbf{r}^{*} \le 1$ , so $\dim H \ge n - 1$ by Rank–Nullity for matrices (Theorem 3.5.7). By the dimension formula (Theorem 1.7.3), $\dim(T \cap H) \ \ge\ (n - i + 1) + (n - 1) - n = n - i \ \ge\ 1 .$ Choose $W \subseteq T \cap H$ with $\dim W = n - i = n - (i+1) + 1$ . For $\mathbf{0} \ne \mathbf{x} \in W$ we have $\mathbf{r}^{*}\mathbf{x} = 0$ , so Eq. 17.9.3 gives $\left\| \mathbf{A}\mathbf{x} \right\| = \left\| \mathbf{B}\mathbf{x} \right\| \le \sigma_i(\mathbf{B})\left\| \mathbf{x} \right\|$ . Hence the inner maximum over $W$ is at most $\sigma_i(\mathbf{B})$ , and $\sigma_{i+1}(\mathbf{A})$ , being the minimum of that inner maximum over all subspaces of dimension $n - (i+1) + 1$ (Theorem 17.9.2), is at most $\sigma_i(\mathbf{B})$ .

Columns. Deleting column $c$ of $\mathbf{A}$ is deleting row $c$ of $\mathbf{A}^{*}$ . Taking conjugate transposes in $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ gives $\mathbf{A}^{*} = \mathbf{V}\boldsymbol{\Sigma}^{*}\mathbf{U}^{*}$ , in which $\boldsymbol{\Sigma}^{*}$ has the same diagonal $\sigma_1, \dots, \sigma_p$ ; so by Theorem 13.9.2, $\sigma_i(\mathbf{A}^{*}) = \sigma_i(\mathbf{A})$ for every $i \le p$ , and the same holds for $\mathbf{B}$ and $\mathbf{B}^{*}$ . Both $\mathbf{A}^{*}$ and $\mathbf{B}^{*}$ have $m$ columns, so the row statement applied to them gives $\sigma_i(\mathbf{B}) \le \sigma_i(\mathbf{A})$ for $i \le m$ and $\sigma_{i+1}(\mathbf{A}) \le \sigma_i(\mathbf{B})$ for $i \le m - 1$ . The remaining indices are free: if $i > m$ then $i$ exceeds $\min(m, n-1)$ , so $\sigma_i(\mathbf{B}) = 0$ and the first inequality is trivial; and if $i \ge m$ then $i + 1 > p$ , so $\sigma_{i+1}(\mathbf{A}) = 0$ and the second is trivial. Hence both chains hold on the stated ranges. This proves the theorem.

Example (Interlacing on a 3 × 2 matrix)

Let $\mathbf{A} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1\end{pmatrix}$ , the matrix of Example (The best rank-one approximation of a 3 × 2 matrix). Verify Theorem 17.9.8 for each of the three rows that could be deleted.

Solution. Example (The best rank-one approximation of a 3 × 2 matrix) computed $\mathbf{A}^{\top}\mathbf{A} = \begin{psmallmatrix} 2 & 1 \\ 1 & 2\end{psmallmatrix}$ , with eigenvalues $3$ and $1$ , so $\sigma_1(\mathbf{A}) = \sqrt3 \approx 1.732$ and $\sigma_2(\mathbf{A}) = 1$ .

Deleting row 1 or row 2. The remaining matrix is $\begin{psmallmatrix} 0 & 1 \\ 1 & 1\end{psmallmatrix}$ or $\begin{psmallmatrix} 1 & 0 \\ 1 & 1\end{psmallmatrix}$ . In both cases $\mathbf{B}^{\top}\mathbf{B} = \begin{psmallmatrix} 1 & 1 \\ 1 & 2\end{psmallmatrix}$ , with trace $3$ and determinant $1$ , hence eigenvalues $(3 \pm \sqrt5)/2$ . Their square roots are $(1 + \sqrt5)/2 \approx 1.618$ and $(\sqrt5 - 1)/2 \approx 0.618$ — the two are reciprocal, since $(3+\sqrt5)/2 \cdot (3-\sqrt5)/2 = 1$ . The interlacing reads $1.732 \ \ge\ 1.618 \ \ge\ 1 \ \ge\ 0.618 ,$ that is $\sigma_1(\mathbf{A}) \ge \sigma_1(\mathbf{B}) \ge \sigma_2(\mathbf{A}) \ge \sigma_2(\mathbf{B})$ , as the theorem requires.

Deleting row 3. The remaining matrix is $\mathbf{I}_2$ , with $\sigma_1 = \sigma_2 = 1$ , and the chain reads $1.732 \ge 1 \ge 1 \ge 1$ . Here the second inequality of the first chain and the inequality of the second chain are both equalities: deleting the row that carried all the interaction between the two columns leaves a perfectly conditioned matrix.

Everything in this section came from one move: a singular value is the square root of an eigenvalue of a Hermitian matrix, so the min–max theory transfers wholesale. What the transfer bought is worth listing. The spectral half of the Eckart–Young theorem, which Chapter 13 could state only in the Frobenius norm, is now proved. The condition number of Chapter 16 has a geometric meaning: $1/\kappa_2(\mathbf{A})$ is how far, relatively, $\mathbf{A}$ sits from the nearest singular matrix. And singular values turned out to be perfectly conditioned with no hypothesis at all, which the Jordan block showed eigenvalues are not. The Hermitian dilation $\mathcal{H}(\mathbf{A})$ is the other bridge from singular values to Hermitian eigenvalues; Section 10’s exercises use it, and Chapter 20 leans on it for perturbation bounds.

17.9.7. Exercises

A. Check your understanding

Exercise (A1)

(a) State the min–max description of $\sigma_k(\mathbf{A})$ , naming the dimension of the subspaces in each of the two forms.
(b) Explain in one sentence why the identity $\left\| \mathbf{A}\mathbf{x} \right\|^2/\left\| \mathbf{x} \right\|^2 = R_{\mathbf{A}^{*}\mathbf{A}}(\mathbf{x})$ is what makes the whole section possible.
(c) State the bound of Corollary 17.9.5 and say precisely which hypotheses it needs, comparing with Corollary 17.3.6.
(d) What is $\min\{\left\| \mathbf{A} - \mathbf{B} \right\|_2 : \operatorname{rank}\mathbf{B} \le k\}$ , and what is the corresponding Frobenius-norm minimum? Which of the two is larger, and why?
(e) Decide whether the statement is correct, and justify: “a square matrix with a very small determinant is close to a singular matrix”.

Solution.

(a) See Theorem 17.9.2: $\sigma_k(\mathbf{A})$ is the minimum, over subspaces $W \le F^n$ of dimension $n - k + 1$ , of $\max\{\left\| \mathbf{A}\mathbf{x} \right\|/\left\| \mathbf{x} \right\| : \mathbf{0} \ne \mathbf{x} \in W\}$ ; equivalently the maximum, over subspaces of dimension $k$ , of the corresponding minimum.
(b) It converts a statement about the rectangular matrix $\mathbf{A}$ , which has no eigenvalues, into a statement about the Hermitian matrix $\mathbf{A}^{*}\mathbf{A}$ , which has the whole of Sections 1 to 8 available; and the conversion loses nothing, because the square root is increasing.
(c) $\lvert\sigma_i(\mathbf{A} + \mathbf{E}) - \sigma_i(\mathbf{A})\rvert \le \left\| \mathbf{E} \right\|_2$ , for arbitrary $\mathbf{A}, \mathbf{E} \in M_{m\times n}(F)$ — no symmetry, no smallness, no squareness. Corollary 17.3.6 is the same bound for eigenvalues, but it requires both $\mathbf{A}$ and $\mathbf{E}$ to be Hermitian, and Example (A Jordan block’s eigenvalues move like $\varepsilon^{1/k}$ ) shows the bound is false without that.
(d) $\sigma_{k+1}(\mathbf{A})$ in the spectral norm (Theorem 17.9.6) and $\bigl(\sum_{i>k}\sigma_i^2\bigr)^{1/2}$ in the Frobenius norm (Theorem 13.11.3). The Frobenius value is the larger, since $\sum_{i>k}\sigma_i^2 \ge \sigma_{k+1}^2$ ; it charges for every discarded singular value, the spectral norm only for the biggest.
(e) Incorrect. Nearness to singularity is measured by $\sigma_n$ , not by $\det$ (Corollary 17.9.7). The matrix $10^{-6}\mathbf{I}_{10}$ has determinant $10^{-60}$ and relative distance $1$ to the singular matrices, the largest possible value. The determinant is the product of all the singular values and cannot report the smallest one.

B. Practice

Exercise (B1: Two norms, one list of singular values)

A matrix $\mathbf{A} \in M_{5\times4}(\mathbb{R})$ has singular values $8, 4, 4, 1$ .

(a) Compute $\min\{\left\| \mathbf{A} - \mathbf{B} \right\|_2 : \operatorname{rank}\mathbf{B} \le k\}$ for $k = 0, 1, 2, 3$ .
(b) Compute the corresponding Frobenius minima and say for which $k$ the two agree.
(c) Compute $\kappa_2(\mathbf{A})$ and the relative distance from $\mathbf{A}$ to the set of matrices of rank at most $3$ .

Solution.

(a) By Theorem 17.9.6 the minimum is $\sigma_{k+1}$ , so the four values are $8, 4, 4, 1$ for $k = 0, 1, 2, 3$ .
(b) By Theorem 13.11.3 the minimum is $\bigl(\sum_{i>k}\sigma_i^2\bigr)^{1/2}$ : $\sqrt{64+16+16+1} = \sqrt{97}, \quad \sqrt{33}, \quad \sqrt{17}, \quad 1$ for $k = 0, 1, 2, 3$ , approximately $9.849,\ 5.745,\ 4.123,\ 1$ . They agree only at $k = 3$ , where exactly one singular value is discarded.
(c) $\mathbf{A}$ has rank $4$ and full column rank, so Definition 16.8.1 gives $\kappa_2(\mathbf{A}) = \sigma_1/\sigma_4 = 8$ . The distance to the matrices of rank at most $3$ is $\sigma_4 = 1$ and $\left\| \mathbf{A} \right\|_2 = 8$ , so the relative distance is $\tfrac18 = 1/\kappa_2(\mathbf{A})$ — the rectangular analogue of Corollary 17.9.7, and for the same reason.

Exercise (B2: The nearest singular matrix)

Let $\mathbf{A} = \begin{pmatrix} 2 & 1 \\ 1 & 1\end{pmatrix}$ , whose condition number $\kappa_2(\mathbf{A}) = \tfrac{7 + 3\sqrt5}{2} \approx 6.854$ was computed in Example (Three condition numbers of one matrix).

(a) Find the singular values of $\mathbf{A}$ and the distance from $\mathbf{A}$ to the nearest singular matrix.
(b) Write down a singular matrix at exactly that distance, and check that it is singular.
(c) Compute the relative distance and compare it with $1/\kappa_2(\mathbf{A})$ .

Solution.

(a) $\mathbf{A}$ is symmetric with $\operatorname{tr}\mathbf{A} = 3$ and $\det\mathbf{A} = 1$ , so its eigenvalues are $(3 \pm \sqrt5)/2$ , both positive; hence these are also its singular values, $\sigma_1 = \tfrac{3+\sqrt5}{2} \approx 2.618, \qquad \sigma_2 = \tfrac{3-\sqrt5}{2} \approx 0.382 .$ By Corollary 17.9.7 the distance to the nearest singular matrix is $\sigma_2 = (3-\sqrt5)/2$ .
(b) The witness is $\mathbf{A}_1 = \sigma_1\mathbf{v}_1\mathbf{v}_1^{\top}$ , where $\mathbf{v}_1$ is a unit eigenvector for $\sigma_1$ . From $(2 - \sigma_1)x_1 + x_2 = 0$ we may take $\mathbf{v}_1$ parallel to $(2, \sqrt5 - 1)$ , whose squared length is $4 + (6 - 2\sqrt5) = 10 - 2\sqrt5$ . Hence $\mathbf{A}_1 = \frac{3+\sqrt5}{2}\cdot\frac{1}{10 - 2\sqrt5}\begin{pmatrix} 4 & 2(\sqrt5-1) \\ 2(\sqrt5-1) & 6 - 2\sqrt5\end{pmatrix} = \begin{pmatrix} 1 + \tfrac{2\sqrt5}{5} & \tfrac12 + \tfrac{3\sqrt5}{10} \\[2pt] \tfrac12 + \tfrac{3\sqrt5}{10} & \tfrac12 + \tfrac{\sqrt5}{10}\end{pmatrix} ,$ approximately $\begin{psmallmatrix} 1.894 & 1.171 \\ 1.171 & 0.724\end{psmallmatrix}$ . It is singular: it is a scalar multiple of $\mathbf{v}_1\mathbf{v}_1^{\top}$ , which has rank $1$ , so its determinant is $0$ . (Directly: $1.894 \times 0.724 - 1.171^2 = 0$ to three decimals.)
(c) $\left\| \mathbf{A} \right\|_2 = \sigma_1$ , so the relative distance is $\frac{\sigma_2}{\sigma_1} = \frac{3 - \sqrt5}{3 + \sqrt5} = \frac{(3-\sqrt5)^2}{4} = \frac{7 - 3\sqrt5}{2} \approx 0.1459 ,$ using $(3-\sqrt5)(3+\sqrt5) = 4$ . And $1/\kappa_2(\mathbf{A}) = 2/(7 + 3\sqrt5) = (7 - 3\sqrt5)/2$ , since $(7+3\sqrt5)(7-3\sqrt5) = 49 - 45 = 4$ . The two agree, as Corollary 17.9.7 says.

Exercise (B3: Interlacing by hand)

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

(a) Compute the singular values of $\mathbf{A}$ .
(b) Compute the singular values of each of the three matrices obtained by deleting one row, and check Theorem 17.9.8 in each case.

Solution.

(a) $\mathbf{A}^{\top}\mathbf{A} = \begin{psmallmatrix} 4 & 0 \\ 0 & 5\end{psmallmatrix}$ , so the eigenvalues are $5$ and $4$ and $\sigma_1(\mathbf{A}) = \sqrt5 \approx 2.236$ , $\sigma_2(\mathbf{A}) = 2$ .
(b) Deleting row $1$ leaves $\begin{psmallmatrix} 0 & 1 \\ 0 & 2\end{psmallmatrix}$ , with $\mathbf{B}^{\top}\mathbf{B} = \operatorname{diag}(0, 5)$ , so $\sigma_1 = \sqrt5$ , $\sigma_2 = 0$ ; the chain reads $\sqrt5 \ge \sqrt5 \ge 2 \ge 0$ .

Deleting row $2$ leaves $\begin{psmallmatrix} 2 & 0 \\ 0 & 2\end{psmallmatrix}$ , with singular values $2, 2$ ; the chain reads $\sqrt5 \ge 2 \ge 2 \ge 2$ .

Deleting row $3$ leaves $\begin{psmallmatrix} 2 & 0 \\ 0 & 1\end{psmallmatrix}$ , with singular values $2, 1$ ; the chain reads $\sqrt5 \ge 2 \ge 2 \ge 1$ .

All three satisfy $\sigma_1(\mathbf{A}) \ge \sigma_1(\mathbf{B}) \ge \sigma_2(\mathbf{A}) \ge \sigma_2(\mathbf{B})$ , as Theorem 17.9.8 requires.

C. Going deeper

Exercise (C1: Rank cannot drop suddenly)

Let $\mathbf{A} \in M_{m\times n}(F)$ have rank $r \ge 1$ .

(a) Prove that every $\mathbf{B} \in M_{m\times n}(F)$ with $\left\| \mathbf{A} - \mathbf{B} \right\|_2 < \sigma_r(\mathbf{A})$ has $\operatorname{rank}\mathbf{B} \ge r$ .
(b) Deduce that for every $\mathbf{A}$ there is an $\varepsilon > 0$ such that every $\mathbf{B}$ within $\varepsilon$ of $\mathbf{A}$ in the spectral norm has $\operatorname{rank}\mathbf{B} \ge \operatorname{rank}\mathbf{A}$ .
(c) Show that the reverse inequality can fail however small $\varepsilon$ is: give matrices $\mathbf{A}$ and $\mathbf{B}$ with $\left\| \mathbf{A} - \mathbf{B} \right\|_2$ as small as we like and $\operatorname{rank}\mathbf{B} > \operatorname{rank}\mathbf{A}$ .

Hint: for (a), argue by contradiction with Theorem 17.9.6.

Solution.

(a) Suppose $\operatorname{rank}\mathbf{B} \le r - 1$ . By Theorem 17.9.6 with $k = r - 1$ , $\left\| \mathbf{A} - \mathbf{B} \right\|_2 \ \ge\ \sigma_{r}(\mathbf{A}) ,$ contradicting the hypothesis. Hence $\operatorname{rank}\mathbf{B} \ge r$ .
(b) If $\mathbf{A} = \mathbf{O}$ any $\varepsilon > 0$ works, since then $r = 0$ and every $\mathbf{B}$ has rank at least $0$ . Otherwise take $\varepsilon = \sigma_r(\mathbf{A})$ , which is $> 0$ because $\mathbf{A}$ has exactly $r = \operatorname{rank}\mathbf{A}$ nonzero singular values (Theorem 13.9.3). Then (a) applies.
(c) Take $\mathbf{A} = \operatorname{diag}(1, 0)$ , of rank $1$ , and $\mathbf{B} = \operatorname{diag}(1, \delta)$ with $\delta > 0$ . Then $\mathbf{A} - \mathbf{B} = \operatorname{diag}(0, -\delta)$ , so $\left\| \mathbf{A} - \mathbf{B} \right\|_2 = \delta$ , as small as we like, while $\operatorname{rank}\mathbf{B} = 2 > 1 = \operatorname{rank}\mathbf{A}$ . Rank can jump up under an arbitrarily small perturbation, and never jumps down under a small one: that asymmetry is exactly (a), and it is why numerical rank is defined by a threshold on the singular values rather than by exact vanishing.

Exercise (C2: The dilation, and a second proof of the perturbation bound)

Let $\mathbf{A}, \mathbf{E} \in M_{m\times n}(F)$ and let $\mathcal{H}(\cdot)$ be the Hermitian dilation of Proposition 17.9.3.

(a) Prove that $\mathcal{H}(\mathbf{A} + \mathbf{E}) = \mathcal{H}(\mathbf{A}) + \mathcal{H}(\mathbf{E})$ and that $\mathcal{H}(\mathbf{E})$ is Hermitian.
(b) Prove that $\left\| \mathcal{H}(\mathbf{E}) \right\|_2 = \left\| \mathbf{E} \right\|_2$ .
(c) Hence give a second proof of Corollary 17.9.5 for $1 \le i \le p$ , using Corollary 17.3.6, and say in one sentence why this route explains the absence of hypotheses on $\mathbf{E}$ .

Hint: for (b), use Proposition 17.9.3 and Theorem 16.3.3 (c).

Solution.

(a) Both claims are immediate from the block form: $\mathcal{H}$ is built entrywise from $\mathbf{A}$ and $\mathbf{A}^{*}$ , and both $\mathbf{A} \mapsto \mathbf{A}$ and $\mathbf{A} \mapsto \mathbf{A}^{*}$ are additive, so $\mathcal{H}(\mathbf{A} + \mathbf{E}) = \begin{pmatrix} \mathbf{O} & \mathbf{A} + \mathbf{E} \\ \mathbf{A}^{*} + \mathbf{E}^{*} & \mathbf{O}\end{pmatrix} = \mathcal{H}(\mathbf{A}) + \mathcal{H}(\mathbf{E}) .$ That $\mathcal{H}(\mathbf{E})$ is Hermitian was proved in Proposition 17.9.3, which places no hypothesis on its argument.
(b) Write $\mathbf{M} = \mathcal{H}(\mathbf{E})$ , which is Hermitian by (a). Then $\mathbf{M}^{*}\mathbf{M} = \mathbf{M}^2$ , whose eigenvalues are the squares of those of $\mathbf{M}$ (apply Corollary 12.4.3 to $\mathbf{M}$ and square the diagonal). By Proposition 17.9.3 the eigenvalues of $\mathbf{M}$ are $\pm\sigma_i(\mathbf{E})$ for $i \le p$ together with zeros, so the eigenvalues of $\mathbf{M}^{*}\mathbf{M}$ are the numbers $\sigma_i(\mathbf{E})^2$ , each twice, together with zeros. The largest is $\sigma_1(\mathbf{E})^2$ , so $\sigma_1(\mathbf{M}) = \sigma_1(\mathbf{E})$ by Definition 13.9.1, and Theorem 16.3.3 (c) turns this into $\left\| \mathcal{H}(\mathbf{E}) \right\|_2 = \left\| \mathbf{E} \right\|_2$ .
(c) Let $1 \le i \le p$ . By Proposition 17.9.3 the largest $p$ eigenvalues of $\mathcal{H}(\mathbf{A})$ are $\sigma_1(\mathbf{A}) \ge \dots \ge \sigma_p(\mathbf{A})$ , all of the remaining ones being $\le 0$ ; so $\lambda_i(\mathcal{H}(\mathbf{A})) = \sigma_i(\mathbf{A})$ , and likewise $\lambda_i(\mathcal{H}(\mathbf{A} + \mathbf{E})) = \sigma_i(\mathbf{A} + \mathbf{E})$ . By (a), $\mathcal{H}(\mathbf{A}+\mathbf{E}) = \mathcal{H}(\mathbf{A}) + \mathcal{H}(\mathbf{E})$ with $\mathcal{H}(\mathbf{A})$ and $\mathcal{H}(\mathbf{E})$ both Hermitian, so Corollary 17.3.6 applies and gives $\lvert\sigma_i(\mathbf{A} + \mathbf{E}) - \sigma_i(\mathbf{A})\rvert = \lvert\lambda_i(\mathcal{H}(\mathbf{A}+\mathbf{E})) - \lambda_i(\mathcal{H}(\mathbf{A}))\rvert \le \left\| \mathcal{H}(\mathbf{E}) \right\|_2 = \left\| \mathbf{E} \right\|_2 .$ The route explains the missing hypotheses: Corollary 17.3.6 demands that the perturbation be Hermitian, and $\mathcal{H}(\mathbf{E})$ is Hermitian for every $\mathbf{E}$ whatsoever. Passing to the dilation manufactures the hypothesis instead of assuming it.