20.7 The Sylvester Equation Revisited

Chapter 12 settled when the equation $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} = \mathbf{C}$ can be solved: over $\mathbb{C}$ it has exactly one solution for every $\mathbf{C}$ if and only if $\mathbf{A}$ and $\mathbf{B}$ have no common eigenvalue (Theorem 12.10.2). It then set a question aside. “The quantitative version — how badly conditioned the equation is when the spectra are close but disjoint — is a separate matter, and belongs with perturbation theory in Chapter 20.” Chapter 8, which first wrote the equation as a linear system, said the same thing more briefly: “its quantitative form appears in Chapter 20.” This section pays both debts. It attaches to each pair $(\mathbf{A}, \mathbf{B})$ a number that says how large a solution can be, computes it exactly for normal pairs, shows how badly it can behave otherwise, and proves a bound in the spectral norm for Hermitian pairs whose spectra sit on opposite sides of a gap.

The reason to want these bounds now is that Sections 9 and 10 need them. In Section 9 the error in a computed invariant subspace turns out to satisfy a Sylvester equation, and in Section 10 so does the error in a square root or a polar factor. Each of those three errors is measured by one of the bounds proved here, applied once.

Throughout, the field is $\mathbb{C}$ , $\mathbf{A} \in M_m(\mathbb{C})$ and $\mathbf{B} \in M_n(\mathbb{C})$ , and $\mathbf{X}, \mathbf{C} \in M_{m \times n}(\mathbb{C})$ . We write $\mathcal{S} = \mathcal{S}_{\mathbf{A},\mathbf{B}}$ for the Sylvester operator $\mathbf{X} \mapsto \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B}$ of Definition 12.10.1, and $\mathbf{K} = \mathbf{I}_n \otimes \mathbf{A} - \mathbf{B}^{\top} \otimes \mathbf{I}_m$ for its matrix, so that $\operatorname{vec}(\mathcal{S}(\mathbf{X})) = \mathbf{K}\operatorname{vec}\mathbf{X}$ by Eq. 12.10.1. The eigenvalues of $\mathbf{A}$ are $\lambda_1, \dots, \lambda_m$ and those of $\mathbf{B}$ are $\mu_1, \dots, \mu_n$ , with multiplicity. Every bound names its norm: $\left\| \cdot \right\|_F$ is the Frobenius norm and $\left\| \cdot \right\|_2$ the spectral norm.

20.7.1. How large can the solution be?

Start with the smallest case, $m = n = 1$ . The equation is $(a - b)x = c$ , and when $a \ne b$ its solution is $x = c/(a - b)$ . So the size of the answer is governed by one number, the distance $\lvert a - b\rvert$ between the two “spectra”: the closer they are, the larger $x$ can be for a given $c$ .

The natural guess for larger matrices is that the distance between the two spectra, $\min_{i,j}\lvert\lambda_i - \mu_j\rvert$ , plays the same role, so that $\left\| \mathbf{X} \right\|_F \le \left\| \mathbf{C} \right\|_F / \min_{i,j}\lvert\lambda_i - \mu_j\rvert$ . We will see that this guess is right for normal pairs and can be wrong by any factor otherwise. The number that really controls the solution is the smallest amount by which $\mathcal{S}$ can stretch a matrix, and it deserves a name.

The separation of $\mathbf{A}$ and $\mathbf{B}$ is the least that the Sylvester operator can shrink a matrix of unit size.

Definition 20.7.1 (Separation)

Let $\mathbf{A} \in M_m(\mathbb{C})$ and $\mathbf{B} \in M_n(\mathbb{C})$ . The separation of $\mathbf{A}$ and $\mathbf{B}$ is $\begin{aligned} \operatorname{sep}_F(\mathbf{A}, \mathbf{B}) \mathrel{:=} \min\bigl\{ &\left\| \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} \right\|_F : \\ &\mathbf{X} \in M_{m \times n}(\mathbb{C}),\ \left\| \mathbf{X} \right\|_F = 1 \bigr\} . \end{aligned}$

In words: we run over every matrix $\mathbf{X}$ of the right shape whose Frobenius norm is exactly $1$ , apply the Sylvester operator, measure the result in the Frobenius norm, and take the smallest value. By homogeneity, $\left\| \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} \right\|_F \ge \operatorname{sep}_F(\mathbf{A}, \mathbf{B})\left\| \mathbf{X} \right\|_F$ for every $\mathbf{X}$ , and $\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ is the largest constant with this property. The order matters: $\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ belongs to $\mathbf{X} \mapsto \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B}$ , and $\operatorname{sep}_F(\mathbf{B}, \mathbf{A})$ to a different operator on a different space. The subscript $F$ records the norm, as in $\left\| \cdot \right\|_F$ .

Well-definedness. A minimum over an infinite set needs to exist, and the first part of Proposition 20.7.1 below shows that it does, without any appeal to compactness: it is the smallest singular value of $\mathbf{K}$ .

Examples.

$m = n = 1$ . Then $\mathbf{X} = (x)$ with $\lvert x\rvert = 1$ , and $\lvert ax - xb\rvert = \lvert a - b\rvert$ . So $\operatorname{sep}_F(a, b) = \lvert a - b\rvert$ , the one-dimensional picture above.
Equal matrices. For square $\mathbf{A}$ , $\operatorname{sep}_F(\mathbf{A}, \mathbf{A}) = 0$ : the matrix $\mathbf{X} = \mathbf{I}_m/\sqrt{m}$ has $\left\| \mathbf{X} \right\|_F = 1$ and $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{A} = \mathbf{O}$ . This degenerate case matters because it is the extreme of a shared eigenvalue, and the first property below says that any shared eigenvalue forces the separation to $0$ .
Diagonal matrices. If $\mathbf{A} = \operatorname{diag}(\lambda_1, \dots, \lambda_m)$ and $\mathbf{B} = \operatorname{diag}(\mu_1, \dots, \mu_n)$ , then $(\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B})_{ij} = (\lambda_i - \mu_j)x_{ij}$ , so $\mathcal{S}$ multiplies each entry by its own factor. The smallest stretch is the smallest factor in modulus, and $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \min_{i,j}\lvert\lambda_i - \mu_j\rvert$ . The proof of Theorem 20.7.2 below writes this out.

Nonexample by minimal change. Drop the normalization and take $\min\{\left\| \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} \right\|_F : \mathbf{X} \ne \mathbf{O}\}$ instead. The set of values is still nonempty and bounded below, but its infimum is $0$ for every pair, and when the spectra are disjoint it is never attained: replacing $\mathbf{X}$ by $t\mathbf{X}$ multiplies the value by $t$ , and $t$ can be as small as we like, while the value $0$ is taken at some $\mathbf{X} \ne \mathbf{O}$ exactly when the two spectra meet (Theorem 12.10.2), as they do in the second example above, where $\mathbf{A} = \mathbf{B}$ and $\mathbf{X} = \mathbf{I}_m$ . It is exactly the clause $\left\| \mathbf{X} \right\|_F = 1$ that fails, and it is what turns a meaningless infimum into a measurement of the operator.

Why the Frobenius norm. Vectorization lists the entries of $\mathbf{X}$ in one column, so $\left\| \operatorname{vec}\mathbf{X} \right\|_2 = \left\| \mathbf{X} \right\|_F$ : $\operatorname{vec}$ is an isometry from $(M_{m \times n}(\mathbb{C}), \left\| \cdot \right\|_F)$ to $(\mathbb{C}^{mn}, \left\| \cdot \right\|_2)$ . That turns $\operatorname{sep}_F$ into a question about the ordinary matrix $\mathbf{K}$ , which the singular value decomposition answers. With $\left\| \cdot \right\|_2$ on both sides the minimum is also a sensible quantity, but it has no such formula, and we will not need it: the spectral-norm results below go through a different argument.

Warning. The separation is not the distance between the spectra. It is at most that distance, by part (c) of the proposition below, but it can be far smaller. For $\mathbf{A} = \begin{pmatrix} 1 & t \\ 0 & 1 \end{pmatrix}$ and the $1 \times 1$ matrix $\mathbf{B} = \mathbf{O}_1$ , the spectra $\{1\}$ and $\{0\}$ are at distance $1$ for every $t$ , yet $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) < 1/t$ for $t > 0$ (Example (Separation Far Below the Gap)). Whenever $\mathbf{A}$ or $\mathbf{B}$ is not normal, compute the separation; do not read it off the eigenvalues.

Everything we need about the separation is collected in one proposition.

Proposition 20.7.1 (Properties of the Separation)

Let $\mathbf{A} \in M_m(\mathbb{C})$ , $\mathbf{B} \in M_n(\mathbb{C})$ , and $\mathbf{K} = \mathbf{I}_n \otimes \mathbf{A} - \mathbf{B}^{\top} \otimes \mathbf{I}_m$ .

(a) The minimum defining $\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ exists, and $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \sigma_{mn}(\mathbf{K})$ , the smallest singular value of $\mathbf{K}$ .
(b) $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) > 0$ if and only if $\operatorname{spec}(\mathbf{A}) \cap \operatorname{spec}(\mathbf{B}) = \varnothing$ .
(c) $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) \le \min_{i,j}\lvert\lambda_i - \mu_j\rvert$ .
(d) If $\operatorname{spec}(\mathbf{A}) \cap \operatorname{spec}(\mathbf{B}) = \varnothing$ , then for every $\mathbf{C}$ the unique solution of $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} = \mathbf{C}$ satisfies $\left\| \mathbf{X} \right\|_F \le \frac{\left\| \mathbf{C} \right\|_F}{\operatorname{sep}_F(\mathbf{A}, \mathbf{B})} ,$ and equality holds for some $\mathbf{C} \ne \mathbf{O}$ .
(e) For unitary $\mathbf{U} \in \operatorname{U}(m)$ and $\mathbf{V} \in \operatorname{U}(n)$ , $\operatorname{sep}_F(\mathbf{U}^{*}\mathbf{A}\mathbf{U}, \mathbf{V}^{*}\mathbf{B}\mathbf{V}) = \operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ .
(f) If $n = 1$ and $\mathbf{B} = (\mu)$ , then $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \sigma_m(\mathbf{A} - \mu\mathbf{I}_m)$ , the smallest singular value of $\mathbf{A} - \mu\mathbf{I}_m$ .

Idea. Part (a) is the isometry $\operatorname{vec}$ plus the fact that the smallest stretch of a square matrix is its smallest singular value. Part (b) is Sylvester’s theorem, read through (a). Part (c) needs one good test matrix: an eigenvector of $\mathbf{A}$ times a left eigenvector of $\mathbf{B}$ is multiplied by $\lambda - \mu$ under $\mathcal{S}$ , exactly as in the $1 \times 1$ case. Part (d) is the definition read backwards. Part (e) holds because unitary factors change neither the set of unit matrices nor the Frobenius norm. Part (f) is the case $n = 1$ of (a), where $\mathbf{K}$ is nothing but $\mathbf{A} - \mu\mathbf{I}_m$ .

Proof.

(a) Let $\mathbf{X} \in M_{m \times n}(\mathbb{C})$ and $\mathbf{x} = \operatorname{vec}\mathbf{X}$ . The entries of $\mathbf{x}$ are those of $\mathbf{X}$ , so $\left\| \mathbf{x} \right\|_2 = \left\| \mathbf{X} \right\|_F$ , and likewise $\left\| \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} \right\|_F = \left\| \mathbf{K}\mathbf{x} \right\|_2$ by Eq. 12.10.1. Since $\operatorname{vec}$ is a bijection from $M_{m \times n}(\mathbb{C})$ onto $\mathbb{C}^{mn}$ (Definition 8.4.2), the set whose minimum defines $\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ equals $\{\left\| \mathbf{K}\mathbf{x} \right\|_2 : \left\| \mathbf{x} \right\|_2 = 1\}$ . By Lemma 17.9.1 (b) with $k$ equal to the size $mn$ of $\mathbf{K}$ , the head subspace is all of $\mathbb{C}^{mn}$ , and the minimum of $\left\| \mathbf{K}\mathbf{x} \right\|/\left\| \mathbf{x} \right\|$ over $\mathbf{x} \ne \mathbf{0}$ exists and equals $\sigma_{mn}(\mathbf{K})$ . Restricting to unit vectors changes nothing, since the quotient is unchanged when $\mathbf{x}$ is scaled.
(b) By Theorem 13.9.1, the number of nonzero singular values of $\mathbf{K}$ is $\operatorname{rank}\mathbf{K}$ . Since $\sigma_{mn}(\mathbf{K})$ is the smallest, it is nonzero exactly when all $mn$ of them are, that is, when $\operatorname{rank}\mathbf{K} = mn$ , which says that $\mathbf{K}$ is invertible (Theorem 7.5.3 (d)). By Eq. 12.10.1, $\mathbf{K}$ is invertible exactly when $\mathcal{S}$ is, and by Theorem 12.10.2 ((a) $\Leftrightarrow$ (b)) that happens exactly when $\operatorname{spec}(\mathbf{A}) \cap \operatorname{spec}(\mathbf{B}) = \varnothing$ . Combining with (a) proves (b).
(c) Fix $i, j$ . Choose an eigenvector $\mathbf{x}$ of $\mathbf{A}$ for $\lambda_i$ , and, by Proposition 9.10.5 (b), a left eigenvector $\mathbf{y}$ of $\mathbf{B}$ for $\mu_j$ , so that $\mathbf{y}^{\top}\mathbf{B} = \mu_j\mathbf{y}^{\top}$ (Definition 9.10.1). Scale both to length $1$ , and put $\mathbf{X} = \mathbf{x}\mathbf{y}^{\top}$ . Its $(p, q)$ entry is $x_py_q$ , so $\left\| \mathbf{X} \right\|_F^2 = \sum_{p,q}\lvert x_p\rvert^2\lvert y_q\rvert^2 = \left\| \mathbf{x} \right\|^2\left\| \mathbf{y} \right\|^2 = 1 .$ By associativity, $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} = (\mathbf{A}\mathbf{x})\mathbf{y}^{\top} - \mathbf{x}(\mathbf{y}^{\top}\mathbf{B}) = (\lambda_i - \mu_j)\mathbf{X}$ . Hence $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) \le \left\| (\lambda_i - \mu_j)\mathbf{X} \right\|_F = \lvert\lambda_i - \mu_j\rvert$ . This holds for every pair $(i, j)$ , so it holds for the minimum.
(d) By Theorem 12.10.2 the solution $\mathbf{X}$ exists and is unique. If $\mathbf{X} = \mathbf{O}$ there is nothing to prove. Otherwise $\mathbf{X}/\left\| \mathbf{X} \right\|_F$ has Frobenius norm $1$ , so by Definition 20.7.1 $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) \le \frac{\left\| \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} \right\|_F}{\left\| \mathbf{X} \right\|_F} = \frac{\left\| \mathbf{C} \right\|_F}{\left\| \mathbf{X} \right\|_F} ,$ and $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) > 0$ by (b), so we may rearrange. For equality, take $\mathbf{X}_0$ with $\left\| \mathbf{X}_0 \right\|_F = 1$ attaining the minimum, which exists by (a), and put $\mathbf{C} = \mathbf{A}\mathbf{X}_0 - \mathbf{X}_0\mathbf{B}$ . Then $\mathbf{C} \ne \mathbf{O}$ , because $\left\| \mathbf{C} \right\|_F = \operatorname{sep}_F(\mathbf{A}, \mathbf{B}) > 0$ , and the unique solution is $\mathbf{X}_0$ , for which the two sides are both $1$ .
(e) Put $\mathbf{A}' = \mathbf{U}^{*}\mathbf{A}\mathbf{U}$ and $\mathbf{B}' = \mathbf{V}^{*}\mathbf{B}\mathbf{V}$ . For every $\mathbf{X}$ , $\mathbf{A}'(\mathbf{U}^{*}\mathbf{X}\mathbf{V}) - (\mathbf{U}^{*}\mathbf{X}\mathbf{V})\mathbf{B}' = \mathbf{U}^{*}(\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B})\mathbf{V} ,$ because $\mathbf{U}\mathbf{U}^{*} = \mathbf{I}_m$ and $\mathbf{V}\mathbf{V}^{*} = \mathbf{I}_n$ . By Lemma 11.7.5, $\left\| \mathbf{U}^{*}\mathbf{X}\mathbf{V} \right\|_F = \left\| \mathbf{X} \right\|_F$ and the right side has Frobenius norm $\left\| \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} \right\|_F$ . The map $\mathbf{X} \mapsto \mathbf{U}^{*}\mathbf{X}\mathbf{V}$ is a bijection of $M_{m \times n}(\mathbb{C})$ , with inverse $\mathbf{Y} \mapsto \mathbf{U}\mathbf{Y}\mathbf{V}^{*}$ , so it carries the matrices of Frobenius norm $1$ onto themselves. Hence the two minima are taken over the same set of values, and they are equal.
(f) With $n = 1$ and $\mathbf{B} = (\mu)$ , the Kronecker matrix is $\mathbf{K} = \mathbf{I}_1 \otimes \mathbf{A} - (\mu) \otimes \mathbf{I}_m = \mathbf{A} - \mu\mathbf{I}_m$ , of size $mn = m$ . So (a) gives $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \sigma_m(\mathbf{A} - \mu\mathbf{I}_m)$ .

Part (d) is the quantitative form that Chapter 8 and Chapter 12 promised, and it says more than an inequality. The number $1/\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ is exactly the largest factor by which solving the equation can magnify the data, measured in the Frobenius norm. Since $\mathcal{S}$ is linear, it is also the factor for errors: if $\mathbf{C}$ is replaced by $\mathbf{C} + \Delta\mathbf{C}$ , the solution moves by $\mathcal{S}^{-1}(\Delta\mathbf{C})$ , whose norm is at most $\left\| \Delta\mathbf{C} \right\|_F/\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ , and some $\Delta\mathbf{C}$ achieves this. A small separation is the precise meaning of “badly conditioned”. Part (c) says that close spectra always make the separation small. The rest of the section asks whether the converse holds, that is, whether well-separated spectra make it large.

Quick check. Part (f) of Proposition 20.7.1 was read off the Kronecker matrix. Prove it instead straight from Definition 20.7.1, without vectorizing: for $\mathbf{B} = (\mu)$ , unwind what the matrices $\mathbf{X}$ of Frobenius norm $1$ are.

Solution. Here $n = 1$ , so $\mathbf{X} = \mathbf{x}$ is a column in $\mathbb{C}^m$ with $\left\| \mathbf{x} \right\|_F = \left\| \mathbf{x} \right\|$ , and $\mathbf{A}\mathbf{x} - \mathbf{x}\mu = (\mathbf{A} - \mu\mathbf{I}_m)\mathbf{x}$ . So $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \min_{\left\| \mathbf{x} \right\| = 1}\left\| (\mathbf{A} - \mu\mathbf{I}_m)\mathbf{x} \right\|$ , which is $\sigma_m(\mathbf{A} - \mu\mathbf{I}_m)$ by Lemma 17.9.1 (b) with $k = m$ .

20.7.2. Normal pairs: the separation is the gap

For normal matrices the naive guess is right, and the proof is the diagonal example written out.

Theorem 20.7.2 (Separation of Normal Matrices)

Let $\mathbf{A} \in M_m(\mathbb{C})$ and $\mathbf{B} \in M_n(\mathbb{C})$ be normal, with eigenvalues $\lambda_1, \dots, \lambda_m$ and $\mu_1, \dots, \mu_n$ . Then $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \min_{i,j}\lvert\lambda_i - \mu_j\rvert .$ Consequently, if $\delta = \min_{i,j}\lvert\lambda_i - \mu_j\rvert > 0$ , the unique solution of $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} = \mathbf{C}$ satisfies $\left\| \mathbf{X} \right\|_F \le \left\| \mathbf{C} \right\|_F/\delta$ .

Idea. Unitary diagonalization costs nothing in the Frobenius norm, by Proposition 20.7.1 (e). Once both matrices are diagonal, the operator scales the $(i, j)$ entry by $\lambda_i - \mu_j$ , so the total shrinkage is a weighted average of the $\lvert\lambda_i - \mu_j\rvert^2$ , and a weighted average is at least the smallest weight.

Proof. By Corollary 12.4.3 there are unitary $\mathbf{U} \in \operatorname{U}(m)$ and $\mathbf{V} \in \operatorname{U}(n)$ with $\mathbf{U}^{*}\mathbf{A}\mathbf{U} = \boldsymbol{\Lambda} \mathrel{:=} \operatorname{diag}(\lambda_1, \dots, \lambda_m)$ and $\mathbf{V}^{*}\mathbf{B}\mathbf{V} = \mathbf{M} \mathrel{:=} \operatorname{diag}(\mu_1, \dots, \mu_n)$ . By Proposition 20.7.1 (e), $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \operatorname{sep}_F(\boldsymbol{\Lambda}, \mathbf{M})$ .

Let $\mathbf{X} = (x_{ij})$ have $\left\| \mathbf{X} \right\|_F = 1$ , and put $\delta = \min_{i,j}\lvert\lambda_i - \mu_j\rvert$ . The $(i, j)$ entry of $\boldsymbol{\Lambda}\mathbf{X} - \mathbf{X}\mathbf{M}$ is $\lambda_ix_{ij} - x_{ij}\mu_j = (\lambda_i - \mu_j)x_{ij}$ , since multiplying by a diagonal matrix on the left scales rows and on the right scales columns. Hence $\begin{aligned} \left\| \boldsymbol{\Lambda}\mathbf{X} - \mathbf{X}\mathbf{M} \right\|_F^2 &= \sum_{i,j}\lvert\lambda_i - \mu_j\rvert^2\lvert x_{ij}\rvert^2 \\ &\ge \delta^2\sum_{i,j}\lvert x_{ij}\rvert^2 = \delta^2 . \end{aligned}$ Therefore $\operatorname{sep}_F(\boldsymbol{\Lambda}, \mathbf{M}) \ge \delta$ . The reverse inequality is Proposition 20.7.1 (c). This proves the equality, and the bound on $\mathbf{X}$ is then Proposition 20.7.1 (d).

The theorem answers the question of the opening completely in the normal case: there, how badly conditioned the equation is depends on the spectra and on nothing else. In particular it applies to Hermitian pairs, which is the case Section 9 needs.

Example (A Normal Pair)

Let $\mathbf{A} = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}, \qquad \mathbf{B} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} .$ Compute $\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ in two ways: from Theorem 20.7.2, and from the singular values of $\mathbf{K}$ .

Solution. The matrix $\mathbf{A}$ is real symmetric, hence normal, with $p_{\mathbf{A}}(x) = (x - 2)^2 - 1 = (x - 1)(x - 3)$ , so its eigenvalues are $1, 3$ . The matrix $\mathbf{B}$ is real with $\mathbf{B}^{\top}\mathbf{B} = \mathbf{I}_2 = \mathbf{B}\mathbf{B}^{\top}$ , hence normal, and $p_{\mathbf{B}}(x) = x^2 + 1$ , so its eigenvalues are $\pm i$ . The four distances are $\lvert 1 \mp i\rvert = \sqrt2, \qquad \lvert 3 \mp i\rvert = \sqrt{10} ,$ so Theorem 20.7.2 gives $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \sqrt2$ .

For the second computation, $\mathbf{B}^{\top} = \begin{psmallmatrix} 0 & 1 \\ -1 & 0 \end{psmallmatrix}$ , and by Definition 8.4.1, in $2 \times 2$ blocks, $\mathbf{K} = \mathbf{I}_2 \otimes \mathbf{A} - \mathbf{B}^{\top} \otimes \mathbf{I}_2 = \begin{pmatrix} \mathbf{A} & -\mathbf{I}_2 \\ \mathbf{I}_2 & \mathbf{A} \end{pmatrix} .$ Since $\mathbf{K}$ is real, $\mathbf{K}^{*} = \mathbf{K}^{\top}$ , so the singular values of $\mathbf{K}$ are the nonnegative square roots of the eigenvalues of $\mathbf{K}^{\top}\mathbf{K}$ (Definition 13.9.1). Since $\mathbf{A}$ is real symmetric, block multiplication (Theorem 8.1.1) gives $\begin{aligned} \mathbf{K}^{\top}\mathbf{K} &= \begin{pmatrix} \mathbf{A} & \mathbf{I}_2 \\ -\mathbf{I}_2 & \mathbf{A} \end{pmatrix}\begin{pmatrix} \mathbf{A} & -\mathbf{I}_2 \\ \mathbf{I}_2 & \mathbf{A} \end{pmatrix} \\ &= \begin{pmatrix} \mathbf{A}^2 + \mathbf{I}_2 & \mathbf{O} \\ \mathbf{O} & \mathbf{A}^2 + \mathbf{I}_2 \end{pmatrix} . \end{aligned}$ The eigenvalues of $\mathbf{A}^2 + \mathbf{I}_2$ are $1^2 + 1 = 2$ and $3^2 + 1 = 10$ (Theorem 9.10.1), so the singular values of $\mathbf{K}$ are $\sqrt{10}, \sqrt{10}, \sqrt2, \sqrt2$ . The smallest is $\sqrt2$ , in agreement with Proposition 20.7.1 (a).

20.7.3. Nonnormal pairs: the separation can collapse

For a nonnormal pair the inequality of Proposition 20.7.1 (c) can be strict, and by as large a factor as we please. The smallest example uses a $1 \times 1$ matrix $\mathbf{B}$ , so that Proposition 20.7.1 (f) computes the separation.

Example (Separation Far Below the Gap)

For a real number $t \ge 0$ , let $\mathbf{A} = \begin{pmatrix} 1 & t \\ 0 & 1 \end{pmatrix}, \qquad \mathbf{B} = \mathbf{O}_1 .$ Compute $\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ and compare it with the distance between the spectra. Then, for $t = 99/10$ , solve $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} = \mathbf{C}$ with $\mathbf{C} = \mathbf{e}_2$ and compare the size of the solution with the guess $\left\| \mathbf{C} \right\|_F/\min\lvert\lambda_i - \mu_j\rvert$ .

Solution. The spectra are $\operatorname{spec}(\mathbf{A}) = \{1\}$ (triangular, Theorem 9.7.4) and $\operatorname{spec}(\mathbf{B}) = \{0\}$ , at distance $1$ for every $t$ . By Proposition 20.7.1 (f) with $\mu = 0$ , $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \sigma_2(\mathbf{A})$ , the square root of the smaller eigenvalue of $\mathbf{A}^{\top}\mathbf{A} = \begin{pmatrix} 1 & t \\ t & 1 + t^2 \end{pmatrix} .$ Its characteristic polynomial is $(z - 1)(z - 1 - t^2) - t^2 = z^2 - (2 + t^2)z + 1$ . Both roots are positive and their product is $1$ , so the smaller is the reciprocal of the larger, $\sigma_2(\mathbf{A}) = 1/\sigma_1(\mathbf{A})$ . Solving the quadratic, $\sigma_2(\mathbf{A})^2 = \frac{2 + t^2 - t\sqrt{t^2 + 4}}{2} = \Bigl(\frac{\sqrt{t^2 + 4} - t}{2}\Bigr)^2 ,$ as expanding the square confirms. Hence $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \frac{\sqrt{t^2 + 4} - t}{2} = \frac{2}{\sqrt{t^2 + 4} + t} ,$ where the second form multiplies top and bottom by $\sqrt{t^2 + 4} + t$ . The second form is less than $2/(2t) = 1/t$ for $t > 0$ , because $\sqrt{t^2 + 4} > t$ . The spectra stay at distance $1$ , and the separation tends to $0$ as $t \to \infty$ .

For $t = 99/10$ we have $t^2 + 4 = 10201/100$ , whose square root is $101/10$ , so $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \frac{1}{2}\Bigl(\frac{101}{10} - \frac{99}{10}\Bigr) = \frac{1}{10} .$ The equation is $\mathbf{A}\mathbf{x} = \mathbf{e}_2$ for the column $\mathbf{x} = \mathbf{X}$ , so $\mathbf{x} = \mathbf{A}^{-1}\mathbf{e}_2 = (-t, 1)$ , since $\mathbf{A}^{-1} = \begin{psmallmatrix} 1 & -t \\ 0 & 1 \end{psmallmatrix}$ . Its length is $\sqrt{t^2 + 1} = \sqrt{9901}/10 \approx 9.95$ . The guess from the eigenvalues was $\left\| \mathbf{C} \right\|_F/1 = 1$ , wrong by a factor of almost $10$ . The true bound $\left\| \mathbf{C} \right\|_F/\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = 10$ from Proposition 20.7.1 (d) is almost attained, and it is attained when $\mathbf{C}$ is a unit left singular vector of $\mathbf{A}$ for $\sigma_2$ .

The example has a second reading. The eigenvalue $1$ of $\mathbf{A}$ is far from $0$ , yet a perturbation of $\mathbf{A}$ of size $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = 1/10$ in the spectral norm makes $0$ an eigenvalue, because that is how far $\mathbf{A}$ is from the singular matrices (Corollary 17.9.7). Exercise C1 below shows that, for every pair, no perturbation of spectral norm less than $\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ can create a common eigenvalue, and that when $\mathbf{B}$ is $1 \times 1$ one of exactly that size can. For a nonnormal pair, the distance between the spectra measures the wrong thing, and the separation measures the right one.

20.7.4. A one-sided bound in the spectral norm

Section 9 will measure the angle between two invariant subspaces, and the largest such angle is a spectral norm, not a Frobenius norm. For Hermitian pairs, Theorem 20.7.2 already gives $\left\| \mathbf{X} \right\|_F \le \left\| \mathbf{C} \right\|_F/\delta$ . The spectral-norm analogue with the same constant is false in general: Exercise C2 below exhibits real diagonal $\mathbf{A}$ and $\mathbf{B}$ whose spectra interlace at distance $1$ , yet $\left\| \mathbf{X} \right\|_2 > \left\| \mathbf{C} \right\|_2$ . What rescues the spectral norm is a stronger hypothesis on where the spectra lie: all of $\operatorname{spec}(\mathbf{A})$ on one side of a gap and all of $\operatorname{spec}(\mathbf{B})$ on the other.

Theorem 20.7.3 (One-Sided Sylvester Bound)

Let $\mathbf{A} \in M_m(\mathbb{C})$ and $\mathbf{B} \in M_n(\mathbb{C})$ be Hermitian, and let $\alpha > \beta$ be real numbers with $\mathbf{A} \succeq \alpha\mathbf{I}_m, \qquad \mathbf{B} \preceq \beta\mathbf{I}_n .$ Then for every $\mathbf{C} \in M_{m \times n}(\mathbb{C})$ the equation $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} = \mathbf{C}$ has exactly one solution, and it satisfies $\left\| \mathbf{X} \right\|_2 \le \frac{\left\| \mathbf{C} \right\|_2}{\alpha - \beta}, \qquad \left\| \mathbf{X} \right\|_F \le \frac{\left\| \mathbf{C} \right\|_F}{\alpha - \beta} .$

Idea. The singular-pair trick. A single pair of vectors sees the whole spectral norm of $\mathbf{X}$ : by the singular value decomposition there are unit vectors $\mathbf{u}, \mathbf{v}$ with $\mathbf{X}\mathbf{v} = s\mathbf{u}$ and $\mathbf{X}^{*}\mathbf{u} = s\mathbf{v}$ , where $s = \left\| \mathbf{X} \right\|_2$ . Sandwich the equation between them. The left side becomes $\mathbf{u}^{*}\mathbf{A}\mathbf{X}\mathbf{v} - \mathbf{u}^{*}\mathbf{X}\mathbf{B}\mathbf{v} = s(\mathbf{u}^{*}\mathbf{A}\mathbf{u} - \mathbf{v}^{*}\mathbf{B}\mathbf{v})$ , a real number at least $s(\alpha - \beta)$ because of the two one-sided hypotheses. The right side becomes $\mathbf{u}^{*}\mathbf{C}\mathbf{v}$ , which is at most $\left\| \mathbf{C} \right\|_2$ in modulus. The one-sided hypotheses are used exactly once, to make both quadratic forms pull in the same direction.

Proof. Existence and uniqueness. Let $\lambda \in \operatorname{spec}(\mathbf{A})$ with unit eigenvector $\mathbf{x}$ . Then $\lambda = \langle \mathbf{A}\mathbf{x}, \mathbf{x} \rangle \ge \alpha$ , because $\langle (\mathbf{A} - \alpha\mathbf{I}_m)\mathbf{x}, \mathbf{x} \rangle \ge 0$ by Definition 13.1.1 and Definition 13.5.1. Likewise every $\mu \in \operatorname{spec}(\mathbf{B})$ satisfies $\mu \le \beta < \alpha$ . So $\operatorname{spec}(\mathbf{A}) \cap \operatorname{spec}(\mathbf{B}) = \varnothing$ , and Theorem 12.10.2 gives exactly one solution $\mathbf{X}$ .

The spectral norm. Put $s = \left\| \mathbf{X} \right\|_2$ , which equals $\sigma_1(\mathbf{X})$ by Theorem 16.3.3 (c). If $s = 0$ there is nothing to prove. Otherwise $\mathbf{X}$ has rank at least $1$ , and Theorem 13.9.1 with Eq. 13.9.3 (for $i = 1$ ) gives unit vectors $\mathbf{u} \in \mathbb{C}^m$ and $\mathbf{v} \in \mathbb{C}^n$ with

\mathbf{X}\mathbf{v} = s\mathbf{u}, \qquad \mathbf{X}^{*}\mathbf{u} = s\mathbf{v} .

(20.7.1)

Taking adjoints in the second, $\mathbf{u}^{*}\mathbf{X} = s\mathbf{v}^{*}$ . Multiply $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} = \mathbf{C}$ by $\mathbf{u}^{*}$ on the left and $\mathbf{v}$ on the right: $\begin{aligned} \mathbf{u}^{*}\mathbf{C}\mathbf{v} &= \mathbf{u}^{*}\mathbf{A}(\mathbf{X}\mathbf{v}) - (\mathbf{u}^{*}\mathbf{X})\mathbf{B}\mathbf{v} \\ &= s\,\mathbf{u}^{*}\mathbf{A}\mathbf{u} - s\,\mathbf{v}^{*}\mathbf{B}\mathbf{v} . \end{aligned}$ Since $\mathbf{A} - \alpha\mathbf{I}_m \succeq \mathbf{O}$ and $\mathbf{u}$ is a unit vector, $\mathbf{u}^{*}\mathbf{A}\mathbf{u} - \alpha = \langle (\mathbf{A} - \alpha\mathbf{I}_m)\mathbf{u}, \mathbf{u} \rangle \ge 0$ . Since $\beta\mathbf{I}_n - \mathbf{B} \succeq \mathbf{O}$ , likewise $\mathbf{v}^{*}\mathbf{B}\mathbf{v} \le \beta$ . Hence $\mathbf{u}^{*}\mathbf{C}\mathbf{v}$ is real and $\mathbf{u}^{*}\mathbf{C}\mathbf{v} \ge s(\alpha - \beta) .$ On the other hand, by the Cauchy–Schwarz inequality (Theorem 11.1.5) and Theorem 16.3.2 (a), $\lvert\mathbf{u}^{*}\mathbf{C}\mathbf{v}\rvert \le \left\| \mathbf{u} \right\|\,\left\| \mathbf{C}\mathbf{v} \right\| \le \left\| \mathbf{C} \right\|_2 .$ Combining, $s(\alpha - \beta) \le \left\| \mathbf{C} \right\|_2$ , and dividing by $\alpha - \beta > 0$ gives the first bound.

The Frobenius norm. Hermitian matrices are normal. Every $\lambda_i \ge \alpha$ and every $\mu_j \le \beta$ , as shown above, so $\lambda_i - \mu_j \ge \alpha - \beta$ for all $i, j$ . By Theorem 20.7.2, $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \min_{i,j}(\lambda_i - \mu_j) \ge \alpha - \beta$ , and Proposition 20.7.1 (d) gives $\left\| \mathbf{X} \right\|_F \le \left\| \mathbf{C} \right\|_F/\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) \le \left\| \mathbf{C} \right\|_F/(\alpha - \beta)$ . This proves the theorem.

The trick deserves its name because it is portable. Whenever a matrix $\mathbf{X}$ satisfies a linear equation and one wants $\left\| \mathbf{X} \right\|_2$ , take a top singular pair of $\mathbf{X}$ itself and test the equation against it. The spectral norm is then attained on the test, and the rest is a pair of scalar inequalities. Notice what was not used: the size of the gap between individual eigenvalues. Only the two half-lines $[\alpha, \infty)$ and $(-\infty, \beta]$ matter, which is why the bound survives when $\mathbf{A}$ and $\mathbf{B}$ have many eigenvalues each.

Remark. The one-sided hypothesis does real work in the spectral-norm bound, as Exercise C2 shows. When the spectra of two Hermitian matrices are merely at distance $\delta$ , in any interlaced pattern, the spectral-norm bound does hold with a larger constant: $\left\| \mathbf{X} \right\|_2 \le (\pi/2)\left\| \mathbf{C} \right\|_2/\delta$ , and $\pi/2$ cannot be improved. We do not prove this, and nothing in the book depends on it.

The form of the theorem used most often has a plus sign and two positive definite matrices. It is a direct translation.

Corollary 20.7.4 (Sylvester Bound for Positive Matrices)

Let $\mathbf{S} \in M_m(\mathbb{C})$ and $\mathbf{T} \in M_n(\mathbb{C})$ be Hermitian with $\mathbf{S} \succeq \alpha\mathbf{I}_m$ and $\mathbf{T} \succeq \beta\mathbf{I}_n$ , where $\alpha + \beta > 0$ . Then for every $\mathbf{C} \in M_{m \times n}(\mathbb{C})$ the equation $\mathbf{S}\mathbf{X} + \mathbf{X}\mathbf{T} = \mathbf{C}$ has exactly one solution, and it satisfies $\left\| \mathbf{X} \right\|_2 \le \frac{\left\| \mathbf{C} \right\|_2}{\alpha + \beta}, \qquad \left\| \mathbf{X} \right\|_F \le \frac{\left\| \mathbf{C} \right\|_F}{\alpha + \beta} .$

Proof. The equation reads $\mathbf{S}\mathbf{X} - \mathbf{X}(-\mathbf{T}) = \mathbf{C}$ . The matrix $-\mathbf{T}$ is Hermitian, and $-\beta\mathbf{I}_n - (-\mathbf{T}) = \mathbf{T} - \beta\mathbf{I}_n \succeq \mathbf{O}$ , so $-\mathbf{T} \preceq -\beta\mathbf{I}_n$ . Since $\alpha > -\beta$ , Theorem 20.7.3 applies to the pair $(\mathbf{S}, -\mathbf{T})$ with the numbers $\alpha$ and $-\beta$ , and $\alpha - (-\beta) = \alpha + \beta$ .

The hypothesis is weaker than it looks: $\alpha$ or $\beta$ may be negative, provided their sum is positive. The typical case is $\mathbf{S}, \mathbf{T} \succ \mathbf{O}$ with $\alpha = \lambda_m(\mathbf{S})$ and $\beta = \lambda_n(\mathbf{T})$ , the smallest eigenvalues, which are the best constants because $\mathbf{S} \succeq \lambda_m(\mathbf{S})\mathbf{I}_m$ (Lemma 13.5.2). Section 10 applies the corollary twice in this form, once with $\mathbf{S}$ and $\mathbf{T}$ the square roots of two positive definite matrices and once with them the positive factors of two polar decompositions.

Example (The Bound Can Be Attained)

Let $\mathbf{S} = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ , $\mathbf{T} = (1)$ , and $\mathbf{C} = \begin{pmatrix} 4 \\ -4 \end{pmatrix}$ . Solve $\mathbf{S}\mathbf{X} + \mathbf{X}\mathbf{T} = \mathbf{C}$ and compare with Corollary 20.7.4.

Solution. The eigenvalues of $\mathbf{S}$ are $1$ and $3$ (as for $\mathbf{A}$ in Example (A Normal Pair)), so $\mathbf{S} \succeq 1\cdot\mathbf{I}_2$ by Lemma 13.5.2, and $\mathbf{T} \succeq 1$ . The corollary applies with $\alpha = \beta = 1$ and predicts $\left\| \mathbf{X} \right\|_2 \le \left\| \mathbf{C} \right\|_2/2$ .

Here $\mathbf{X} = \mathbf{x}$ is a column and the equation is $(\mathbf{S} + \mathbf{I}_2)\mathbf{x} = \mathbf{C}$ , with $\mathbf{S} + \mathbf{I}_2 = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}, \qquad (\mathbf{S} + \mathbf{I}_2)^{-1} = \frac{1}{8}\begin{pmatrix} 3 & -1 \\ -1 & 3 \end{pmatrix} .$ So $\mathbf{x} = \tfrac18(12 + 4, -4 - 12) = (2, -2)$ . For a column, the spectral and Frobenius norms are both the Euclidean length, so $\left\| \mathbf{X} \right\|_2 = 2\sqrt2$ , while $\left\| \mathbf{C} \right\|_2/2 = 4\sqrt2/2 = 2\sqrt2$ . The bound is an equality.

The reason is visible: $\mathbf{C}$ is an eigenvector of $\mathbf{S}$ for its smallest eigenvalue $1$ , so $(\mathbf{S} + \mathbf{I}_2)\mathbf{C} = 2\mathbf{C}$ , and the solution is $\mathbf{x} = \mathbf{C}/2$ , of norm exactly $\left\| \mathbf{C} \right\|_2/(\alpha + \beta)$ . The data sits where both one-sided hypotheses are tight.

20.7.5. Exercises

A. Check your understanding

Exercise (A1)

(a) Define $\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ for $\mathbf{A} \in M_m(\mathbb{C})$ and $\mathbf{B} \in M_n(\mathbb{C})$ , and state how it is computed from the Kronecker matrix $\mathbf{K}$ .
(b) True or false: $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \min_{i,j}\lvert\lambda_i - \mu_j\rvert$ for all square $\mathbf{A}, \mathbf{B}$ . Justify your answer.
(c) True or false: $\operatorname{sep}_F(\mathbf{A} + c\mathbf{I}_m, \mathbf{B} + c\mathbf{I}_n) = \operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ for every $c \in \mathbb{C}$ . Justify your answer.
(d) State the bound on the solution of $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} = \mathbf{C}$ in terms of the separation, including its hypothesis.
(e) In the proof of Theorem 20.7.3, which vectors are the equation multiplied by, and where are the hypotheses $\mathbf{A} \succeq \alpha\mathbf{I}_m$ and $\mathbf{B} \preceq \beta\mathbf{I}_n$ used?

Solution.

(a) $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \min\{\left\| \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} \right\|_F : \left\| \mathbf{X} \right\|_F = 1\}$ , the minimum over $\mathbf{X} \in M_{m \times n}(\mathbb{C})$ (Definition 20.7.1). It equals $\sigma_{mn}(\mathbf{K})$ , the smallest singular value of $\mathbf{K} = \mathbf{I}_n \otimes \mathbf{A} - \mathbf{B}^{\top} \otimes \mathbf{I}_m$ (Proposition 20.7.1 (a)).
(b) False. It is true for normal pairs (Theorem 20.7.2), but Example (Separation Far Below the Gap) has spectra at distance $1$ and separation $1/10$ when $t = 99/10$ . What is always true is the inequality $\le$ of Proposition 20.7.1 (c).
(c) True. For every $\mathbf{X}$ , $(\mathbf{A} + c\mathbf{I}_m)\mathbf{X} - \mathbf{X}(\mathbf{B} + c\mathbf{I}_n) = \mathbf{A}\mathbf{X} + c\mathbf{X} - \mathbf{X}\mathbf{B} - c\mathbf{X} = \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B}$ , so the two minima are taken over the same set of values.
(d) If $\operatorname{spec}(\mathbf{A}) \cap \operatorname{spec}(\mathbf{B}) = \varnothing$ , the unique solution satisfies $\left\| \mathbf{X} \right\|_F \le \left\| \mathbf{C} \right\|_F/\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ , and equality holds for some $\mathbf{C} \ne \mathbf{O}$ (Proposition 20.7.1 (d)).
(e) By $\mathbf{u}^{*}$ on the left and $\mathbf{v}$ on the right, where $\mathbf{u}, \mathbf{v}$ are unit vectors with $\mathbf{X}\mathbf{v} = s\mathbf{u}$ and $\mathbf{X}^{*}\mathbf{u} = s\mathbf{v}$ , $s = \left\| \mathbf{X} \right\|_2$ . The hypotheses give $\mathbf{u}^{*}\mathbf{A}\mathbf{u} \ge \alpha$ and $\mathbf{v}^{*}\mathbf{B}\mathbf{v} \le \beta$ , which make $\mathbf{u}^{*}\mathbf{C}\mathbf{v} = s(\mathbf{u}^{*}\mathbf{A}\mathbf{u} - \mathbf{v}^{*}\mathbf{B}\mathbf{v})$ at least $s(\alpha - \beta)$ .

B. Practice

Exercise (B1: A positive Sylvester equation)

Let $\mathbf{S} = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}, \quad \mathbf{T} = \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}, \quad \mathbf{C} = \begin{pmatrix} 3 & 4 \\ -3 & -4 \end{pmatrix} .$

(a) Find the largest $\alpha$ and $\beta$ with $\mathbf{S} \succeq \alpha\mathbf{I}_2$ and $\mathbf{T} \succeq \beta\mathbf{I}_2$ , and state the bound that Corollary 20.7.4 gives for $\left\| \mathbf{X} \right\|_2$ .
(b) Solve $\mathbf{S}\mathbf{X} + \mathbf{X}\mathbf{T} = \mathbf{C}$ , column by column.
(c) Compute $\left\| \mathbf{X} \right\|_2$ and $\left\| \mathbf{C} \right\|_2$ , and check the bound. Hence decide whether the bound is attained here.

Solution.

(a) $p_{\mathbf{S}}(x) = (x - 3)^2 - 1 = (x - 2)(x - 4)$ , so $\lambda_2(\mathbf{S}) = 2$ , and $\lambda_2(\mathbf{T}) = 1$ . By Lemma 13.5.2, $\langle \mathbf{S}\mathbf{x}, \mathbf{x} \rangle \ge 2$ for unit $\mathbf{x}$ , with equality at an eigenvector, so $\alpha = 2$ is the largest constant with $\mathbf{S} \succeq \alpha\mathbf{I}_2$ ; likewise $\beta = 1$ . The corollary gives $\left\| \mathbf{X} \right\|_2 \le \left\| \mathbf{C} \right\|_2/3$ .
(b) Since $\mathbf{T}$ is diagonal, column $j$ of $\mathbf{X}\mathbf{T}$ is $t_{jj}$ times column $j$ of $\mathbf{X}$ . So column $j$ of the equation is $(\mathbf{S} + t_{jj}\mathbf{I}_2)\mathbf{x}_j = \mathbf{c}_j$ . For $j = 1$ : $\begin{psmallmatrix} 4 & 1 \\ 1 & 4 \end{psmallmatrix}\mathbf{x}_1 = (3, -3)$ , and $\mathbf{x}_1 = (1, -1)$ works, since $4 - 1 = 3$ and $1 - 4 = -3$ . For $j = 2$ : $\begin{psmallmatrix} 5 & 1 \\ 1 & 5 \end{psmallmatrix}\mathbf{x}_2 = (4, -4)$ , and $\mathbf{x}_2 = (1, -1)$ works. The solution is unique by Corollary 20.7.4, so $\mathbf{X} = \begin{pmatrix} 1 & 1 \\ -1 & -1 \end{pmatrix} .$
(c) Both matrices have rank one: $\mathbf{X} = \mathbf{a}\mathbf{b}^{\top}$ with $\mathbf{a} = (1, -1)$ , $\mathbf{b} = (1, 1)$ , and $\mathbf{C} = \mathbf{a}\mathbf{c}^{\top}$ with $\mathbf{c} = (3, 4)$ . For a rank-one matrix $\mathbf{a}\mathbf{b}^{\top}$ , the spectral norm equals the Frobenius norm (Proposition 16.3.4), which is $\left\| \mathbf{a} \right\|\,\left\| \mathbf{b} \right\|$ by the computation in Proposition 20.7.1 (c). So $\left\| \mathbf{X} \right\|_2 = \sqrt2\cdot\sqrt2 = 2$ and $\left\| \mathbf{C} \right\|_2 = \sqrt2\cdot 5 = 5\sqrt2$ . The bound reads $2 \le 5\sqrt2/3 \approx 2.357$ , which holds. It is not attained. Each column of $\mathbf{C}$ lies along the eigenvector $(1, -1)$ of $\mathbf{S}$ for $\alpha = 2$ , but the second column is paired with $t_{22} = 2$ rather than $\beta = 1$ , so the second column of $\mathbf{X}$ is $\mathbf{c}_2/4$ , not $\mathbf{c}_2/3$ .

Exercise (B2: Separations of four pairs)

For each pair, compute $\operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ and decide whether it equals $\min_{i,j}\lvert\lambda_i - \mu_j\rvert$ . Justify your answer.

(a) $\mathbf{A} = \operatorname{diag}(1, 3)$ , $\mathbf{B} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ .
(b) $\mathbf{A} = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ , $\mathbf{B} = (-1)$ .
(c) $\mathbf{A} = \begin{pmatrix} 0 & -2 \\ 2 & 0 \end{pmatrix}$ , $\mathbf{B} = \operatorname{diag}(1, -1)$ .
(d) $\mathbf{A} = \begin{pmatrix} 1 & 4 \\ 0 & 1 \end{pmatrix}$ , $\mathbf{B} = \mathbf{O}_1$ .

Solution.

(a) $\mathbf{B}$ is real symmetric with eigenvalues $\pm1$ , and $1 \in \operatorname{spec}(\mathbf{A}) \cap \operatorname{spec}(\mathbf{B})$ . So $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = 0$ by Proposition 20.7.1 (b), which equals the minimum distance $\lvert 1 - 1\rvert = 0$ .
(b) Both matrices are real symmetric, hence normal. The eigenvalues of $\mathbf{A}$ are $1, 3$ and that of $\mathbf{B}$ is $-1$ , so Theorem 20.7.2 gives $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \min(2, 4) = 2$ . It equals the minimum distance.
(c) $\mathbf{A}^{\top}\mathbf{A} = 4\mathbf{I}_2 = \mathbf{A}\mathbf{A}^{\top}$ , so $\mathbf{A}$ is normal, with $p_{\mathbf{A}}(x) = x^2 + 4$ and eigenvalues $\pm2i$ . $\mathbf{B}$ is diagonal. The distances $\lvert\pm2i \mp 1\rvert$ all equal $\sqrt5$ , so $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \sqrt5$ by Theorem 20.7.2, equal to the minimum distance.
(d) This is Example (Separation Far Below the Gap) with $t = 4$ : $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = (\sqrt{20} - 4)/2 = \sqrt5 - 2 \approx 0.236$ , while the spectra $\{1\}$ and $\{0\}$ are at distance $1$ . They are not equal. The theorem does not apply because $\mathbf{A}$ is not normal: $\mathbf{A}^{\top}\mathbf{A} = \begin{psmallmatrix} 1 & 4 \\ 4 & 17 \end{psmallmatrix} \ne \begin{psmallmatrix} 17 & 4 \\ 4 & 1 \end{psmallmatrix} = \mathbf{A}\mathbf{A}^{\top}$ .

Exercise (B3: A symmetric Sylvester equation)

Let $\mathbf{A} \in M_n(\mathbb{C})$ be Hermitian with $\mathbf{A} \succeq 2\mathbf{I}_n$ , and let $\mathbf{C} \in M_n(\mathbb{C})$ .

(a) Prove that $\mathbf{A}\mathbf{X} + \mathbf{X}\mathbf{A} = \mathbf{C}$ has exactly one solution, and that it satisfies $\left\| \mathbf{X} \right\|_2 \le \left\| \mathbf{C} \right\|_2/4$ .
(b) Prove that if $\mathbf{C}$ is Hermitian, then so is $\mathbf{X}$ .

Solution.

(a) Apply Corollary 20.7.4 with $\mathbf{S} = \mathbf{T} = \mathbf{A}$ and $\alpha = \beta = 2$ . Since $\alpha + \beta = 4 > 0$ , the equation has exactly one solution, and $\left\| \mathbf{X} \right\|_2 \le \left\| \mathbf{C} \right\|_2/4$ .
(b) Take the adjoint of $\mathbf{A}\mathbf{X} + \mathbf{X}\mathbf{A} = \mathbf{C}$ . Since $\mathbf{A}^{*} = \mathbf{A}$ and $\mathbf{C}^{*} = \mathbf{C}$ , we get $\mathbf{X}^{*}\mathbf{A} + \mathbf{A}\mathbf{X}^{*} = \mathbf{C}$ , so $\mathbf{X}^{*}$ is also a solution. By the uniqueness in (a), $\mathbf{X}^{*} = \mathbf{X}$ .

C. Going deeper

Exercise (C1: The separation is stable, and it measures a distance)

Let $\mathbf{A} \in M_m(\mathbb{C})$ , $\mathbf{B} \in M_n(\mathbb{C})$ , $\mathbf{E} \in M_m(\mathbb{C})$ , and $\mathbf{F} \in M_n(\mathbb{C})$ .

(a) Prove that $\left\| \mathbf{E}\mathbf{X} \right\|_F \le \left\| \mathbf{E} \right\|_2\left\| \mathbf{X} \right\|_F$ and $\left\| \mathbf{X}\mathbf{F} \right\|_F \le \left\| \mathbf{F} \right\|_2\left\| \mathbf{X} \right\|_F$ for every $\mathbf{X} \in M_{m \times n}(\mathbb{C})$ .
(b) Prove that $\lvert\operatorname{sep}_F(\mathbf{A} + \mathbf{E}, \mathbf{B} + \mathbf{F}) - \operatorname{sep}_F(\mathbf{A}, \mathbf{B})\rvert \le \left\| \mathbf{E} \right\|_2 + \left\| \mathbf{F} \right\|_2$ .
(c) Now let $n = 1$ and $\mathbf{B} = (\mu)$ . Prove that there is $\mathbf{E}$ with $\left\| \mathbf{E} \right\|_2 = \operatorname{sep}_F(\mathbf{A}, \mathbf{B})$ such that $\mu$ is an eigenvalue of $\mathbf{A} + \mathbf{E}$ .
(d) Hence, for $t = 99/10$ in Example (Separation Far Below the Gap), exhibit the size of a perturbation of $\mathbf{A}$ that makes $0$ an eigenvalue, and explain why the eigenvalue gap $1$ is a poor guide to how close the pair is to having a common eigenvalue.

Hint for (c): use a singular value decomposition of $\mathbf{A} - \mu\mathbf{I}_m$ .

Solution.

(a) Let $\mathbf{x}_1, \dots, \mathbf{x}_n$ be the columns of $\mathbf{X}$ . The columns of $\mathbf{E}\mathbf{X}$ are $\mathbf{E}\mathbf{x}_q$ , so by Theorem 16.3.2 (a) $\left\| \mathbf{E}\mathbf{X} \right\|_F^2 = \sum_{q}\left\| \mathbf{E}\mathbf{x}_q \right\|^2 \le \left\| \mathbf{E} \right\|_2^2\sum_q\left\| \mathbf{x}_q \right\|^2 = \left\| \mathbf{E} \right\|_2^2\left\| \mathbf{X} \right\|_F^2 .$ For the second, $\left\| \mathbf{X}\mathbf{F} \right\|_F = \left\| (\mathbf{X}\mathbf{F})^{*} \right\|_F = \left\| \mathbf{F}^{*}\mathbf{X}^{*} \right\|_F$ , since conjugate transposition does not change the moduli of the entries. By the first part this is at most $\left\| \mathbf{F}^{*} \right\|_2\left\| \mathbf{X}^{*} \right\|_F = \left\| \mathbf{F}^{*} \right\|_2\left\| \mathbf{X} \right\|_F$ . Finally $\left\| \mathbf{F}^{*} \right\|_2 = \left\| \mathbf{F} \right\|_2$ : if $\mathbf{F} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ is a singular value decomposition, then $\mathbf{F}^{*} = \mathbf{V}\boldsymbol{\Sigma}^{\top}\mathbf{U}^{*}$ is one for $\mathbf{F}^{*}$ , with the same diagonal, so $\sigma_1(\mathbf{F}^{*}) = \sigma_1(\mathbf{F})$ by Theorem 13.9.2 and Theorem 16.3.3 (c).
(b) Let $\left\| \mathbf{X} \right\|_F = 1$ . By the triangle inequality (Corollary 11.1.6, the Frobenius norm being induced by an inner product) and (a), $\begin{aligned} \left\| (\mathbf{A} + \mathbf{E})\mathbf{X} - \mathbf{X}(\mathbf{B} + \mathbf{F}) \right\|_F &\ge \left\| \mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} \right\|_F - \left\| \mathbf{E}\mathbf{X} \right\|_F - \left\| \mathbf{X}\mathbf{F} \right\|_F \\ &\ge \operatorname{sep}_F(\mathbf{A}, \mathbf{B}) - \left\| \mathbf{E} \right\|_2 - \left\| \mathbf{F} \right\|_2 . \end{aligned}$ Taking the minimum over $\mathbf{X}$ gives $\operatorname{sep}_F(\mathbf{A} + \mathbf{E}, \mathbf{B} + \mathbf{F}) \ge \operatorname{sep}_F(\mathbf{A}, \mathbf{B}) - \left\| \mathbf{E} \right\|_2 - \left\| \mathbf{F} \right\|_2$ . Applying this to the pair $(\mathbf{A} + \mathbf{E}, \mathbf{B} + \mathbf{F})$ with the perturbations $-\mathbf{E}, -\mathbf{F}$ gives the reverse inequality, and together they are the claim.
(c) By Proposition 20.7.1 (f), $s \mathrel{:=} \operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = \sigma_m(\mathbf{A} - \mu\mathbf{I}_m)$ . Let $\mathbf{A} - \mu\mathbf{I}_m = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ be a singular value decomposition (Theorem 13.9.1), with last columns $\mathbf{u}_m$ of $\mathbf{U}$ and $\mathbf{v}_m$ of $\mathbf{V}$ . Then $(\mathbf{A} - \mu\mathbf{I}_m)\mathbf{v}_m = s\mathbf{u}_m$ , comparing column $m$ of $(\mathbf{A} - \mu\mathbf{I}_m)\mathbf{V} = \mathbf{U}\boldsymbol{\Sigma}$ . Put $\mathbf{E} = -s\,\mathbf{u}_m\mathbf{v}_m^{*}$ . Then $(\mathbf{A} + \mathbf{E} - \mu\mathbf{I}_m)\mathbf{v}_m = s\mathbf{u}_m - s\mathbf{u}_m(\mathbf{v}_m^{*}\mathbf{v}_m) = \mathbf{0}$ with $\mathbf{v}_m \ne \mathbf{0}$ , so $\mu$ is an eigenvalue of $\mathbf{A} + \mathbf{E}$ . Also $\left\| \mathbf{E}\mathbf{x} \right\| = s\lvert\mathbf{v}_m^{*}\mathbf{x}\rvert \le s\left\| \mathbf{x} \right\|$ by Cauchy–Schwarz, with equality at $\mathbf{x} = \mathbf{v}_m$ , so $\left\| \mathbf{E} \right\|_2 = s$ .
(d) With $\mu = 0$ and $\operatorname{sep}_F(\mathbf{A}, \mathbf{O}_1) = 1/10$ , part (c) gives a perturbation of spectral norm $1/10$ after which $0$ is an eigenvalue of $\mathbf{A} + \mathbf{E}$ , so $\mathbf{A} + \mathbf{E}$ and $\mathbf{B}$ share an eigenvalue. The eigenvalues $1$ and $0$ are at distance $1$ , but a perturbation ten times smaller than that distance destroys the solvability of the equation. By (b) with $\mathbf{F} = \mathbf{O}$ , no perturbation of spectral norm less than $1/10$ can do it, since it leaves the separation positive. So the separation, not the eigenvalue gap, is the distance to a shared eigenvalue here.

Exercise (C2: Interlaced spectra break the spectral-norm bound)

Let $\mathbf{A} = \operatorname{diag}(0, 2)$ , $\mathbf{B} = \operatorname{diag}(1, 3)$ , and $\mathbf{C} = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ .

(a) Show that every eigenvalue of $\mathbf{A}$ is at distance at least $1$ from every eigenvalue of $\mathbf{B}$ , and explain why Theorem 20.7.3 does not apply with $\alpha - \beta = 1$ .
(b) Solve $\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B} = \mathbf{C}$ .
(c) Show that $\left\| \mathbf{X} \right\|_2 > \left\| \mathbf{C} \right\|_2$ .
(d) Verify directly that $\left\| \mathbf{X} \right\|_F \le \left\| \mathbf{C} \right\|_F$ , as Theorem 20.7.2 requires.

Hint for (c): compute $\mathbf{C}^{\top}\mathbf{C}$ , and test $\mathbf{X}$ on the vector $(1, 1)$ .

Solution.

(a) The eigenvalues are $0, 2$ and $1, 3$ , and the four differences $\lambda_i - \mu_j$ are $-1, -3, 1, -1$ , all of modulus at least $1$ . The theorem needs $\mathbf{A} \succeq \alpha\mathbf{I}$ and $\mathbf{B} \preceq \beta\mathbf{I}$ with $\alpha > \beta$ , that is, every eigenvalue of $\mathbf{A}$ above every eigenvalue of $\mathbf{B}$ , or, applying it to $(-\mathbf{A}, -\mathbf{B})$ , every one below. Neither holds, since $0 < 1 < 2 < 3$ interlace. Applied honestly, the best one-sided constants are $\alpha = 0$ and $\beta = 3$ , and $\alpha > \beta$ fails.
(b) As in the diagonal example after Definition 20.7.1, $(\mathbf{A}\mathbf{X} - \mathbf{X}\mathbf{B})_{ij} = (a_{ii} - b_{jj})x_{ij}$ , so $x_{ij} = c_{ij}/(a_{ii} - b_{jj})$ : $\mathbf{X} = \begin{pmatrix} 1/(0 - 1) & 1/(0 - 3) \\ 1/(2 - 1) & -1/(2 - 3) \end{pmatrix} = \begin{pmatrix} -1 & -1/3 \\ 1 & 1 \end{pmatrix} .$
(c) $\mathbf{C}^{\top}\mathbf{C} = 2\mathbf{I}_2$ , so both singular values of $\mathbf{C}$ are $\sqrt2$ and $\left\| \mathbf{C} \right\|_2 = \sqrt2$ (Theorem 16.3.3 (c)). For $\mathbf{x} = (1, 1)/\sqrt2$ , a unit vector, $\mathbf{X}\mathbf{x} = (-4/3, 2)/\sqrt2$ , so $\left\| \mathbf{X}\mathbf{x} \right\|^2 = \frac{1}{2}\Bigl(\frac{16}{9} + 4\Bigr) = \frac{26}{9} > 2 .$ Hence $\left\| \mathbf{X} \right\|_2 \ge \sqrt{26}/3 > \sqrt2 = \left\| \mathbf{C} \right\|_2$ .
(d) $\left\| \mathbf{X} \right\|_F^2 = 1 + \tfrac19 + 1 + 1 = \tfrac{28}{9}$ and $\left\| \mathbf{C} \right\|_F^2 = 4$ , so $\left\| \mathbf{X} \right\|_F \le \left\| \mathbf{C} \right\|_F$ , in agreement with Theorem 20.7.2, which gives $\operatorname{sep}_F(\mathbf{A}, \mathbf{B}) = 1$ . So the Frobenius bound with constant $1/\delta$ survives interlacing, while the spectral-norm bound with the same constant does not.