17.7 Arbitrary Index Sets

The Courant–Fischer theorem describes one eigenvalue at a time, and Ky Fan’s theorem describes the sum of the top $k$ . Between those two lies every other sum, for instance $\lambda_2 + \lambda_4$ , and §06 ended by warning that the sharpest statements about eigenvalues tend to be statements about sums. This section describes the sum over an arbitrary index set as a max–min, which is Wielandt’s theorem. It then uses that description to compare two Hermitian matrices across any index set at once, which is Lidskii’s inequality. The price of the generality is that single subspaces are replaced by nested chains of them, and the proof takes some care.

Throughout, $F = \mathbb{R}$ or $F = \mathbb{C}$ , every matrix whose eigenvalues are indexed is Hermitian, and the indexing is decreasing, $\lambda_1(\mathbf{A}) \ge \dots \ge \lambda_n(\mathbf{A})$ , with multiplicity. An index set of size $k$ is a list of integers $1 \le i_1 < i_2 < \dots < i_k \le n$ .

17.7.1. What adding up the min–max gives

Here is the question that drives the section. Let $\mathbf{A}$ and $\mathbf{B}$ be Hermitian and fix an index set. How large can $\sum_{j=1}^{k}\lambda_{i_j}(\mathbf{A}) - \sum_{j=1}^{k}\lambda_{i_j}(\mathbf{B})$ be, in terms of $\mathbf{A} - \mathbf{B}$ ? One answer is immediate. By Corollary 17.3.4, applied to $\mathbf{B}$ and the Hermitian matrix $\mathbf{A} - \mathbf{B}$ , each single difference satisfies $\lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B}) \le \lambda_1(\mathbf{A} - \mathbf{B})$ . Adding $k$ of these gives the bound $k\,\lambda_1(\mathbf{A} - \mathbf{B})$ .

That bound is poor, and a rank-one example shows by how much. Let $\mathbf{A} = \mathbf{B} + \mathbf{u}\mathbf{u}^{*}$ with $\left\| \mathbf{u} \right\| = 1$ . By Theorem 17.5.1 every shift $\lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B})$ is $\ge 0$ , and by Corollary 17.5.3 the shifts add up to exactly $\left\| \mathbf{u} \right\|^2 = 1$ . So every partial sum of shifts is at most $1$ , whatever the index set. The eigenvalues of $\mathbf{u}\mathbf{u}^{*}$ are $1, 0, \dots, 0$ , so $1 = \lambda_1 + \dots + \lambda_k$ of $\mathbf{A} - \mathbf{B}$ for every $k$ . The summed Weyl bound says $k$ , which is wrong by a factor of $k$ .

The bound we would like is therefore $\sum_{j=1}^{k}\lambda_{i_j}(\mathbf{A}) - \sum_{j=1}^{k}\lambda_{i_j}(\mathbf{B}) \ \le\ \sum_{j=1}^{k}\lambda_j(\mathbf{A} - \mathbf{B}) ,$ and the obstruction is visible in the proof of Weyl’s inequality. That proof finds, for each index, one good vector. Summing $k$ such bounds uses $k$ unrelated vectors, and the only control over $\sum_j\langle (\mathbf{A}-\mathbf{B})\mathbf{x}_j, \mathbf{x}_j \rangle$ for unrelated unit vectors is $k\,\lambda_1(\mathbf{A}-\mathbf{B})$ . If the $\mathbf{x}_j$ were orthonormal, Theorem 17.6.2 would bound the same sum by $\lambda_1 + \dots + \lambda_k$ of $\mathbf{A} - \mathbf{B}$ . So we need a single orthonormal list $\mathbf{x}_1, \dots, \mathbf{x}_k$ that is simultaneously good for $\mathbf{A}$ and good for $\mathbf{B}$ : $\sum_{j}\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle \ \ge\ \sum_j\lambda_{i_j}(\mathbf{A}) , \qquad \sum_{j}\langle \mathbf{B}\mathbf{x}_j, \mathbf{x}_j \rangle \ \le\ \sum_j\lambda_{i_j}(\mathbf{B}) .$ The first requirement is easy to meet: it will hold whenever each $\mathbf{x}_j$ lies in the span $W_j$ of the top $i_j$ eigenvectors of $\mathbf{A}$ . Those spans are nested, $W_1 \subset W_2 \subset \dots \subset W_k$ , and from $\mathbf{B}$ ’s point of view they are an arbitrary nested chain of subspaces. The second requirement is then a question about $\mathbf{B}$ alone: inside any nested chain of subspaces of these dimensions, is there an orthonormal list whose sum for $\mathbf{B}$ is small? Wielandt’s theorem answers yes, and the chain needs a name.

17.7.2. Flags and adapted lists

Chapter 9 §07 called a chain $U_1 \subset U_2 \subset \dots \subset U_n = V$ with $\dim U_k = k$ a flag, and a basis whose first $k$ members span $U_k$ a basis adapted to it. We need chains that skip dimensions, and lists that meet each member of the chain once.

A flag of type $(i_1, \dots, i_k)$ is a nested chain of subspaces with prescribed dimensions; an adapted list takes its $j$ -th vector from the $j$ -th subspace and is orthonormal.

Definition 17.7.1 (Flags of a given type, and adapted lists)

Let $F = \mathbb{R}$ or $\mathbb{C}$ , and let $1 \le i_1 < \dots < i_k \le n$ be an index set. A flag of type $(i_1, \dots, i_k)$ in $F^n$ is a list $\mathcal{W} = (W_1, \dots, W_k)$ of subspaces of $F^n$ with $W_1 \subseteq W_2 \subseteq \dots \subseteq W_k \qquad\text{and}\qquad \dim W_j = i_j \ \text{ for every } j .$ A list $(\mathbf{x}_1, \dots, \mathbf{x}_k)$ of vectors of $F^n$ is adapted to $\mathcal{W}$ if it is orthonormal and $\mathbf{x}_j \in W_j$ for every $j$ .

In words. The subspaces are nested, and the $j$ -th one has dimension equal to the $j$ -th index $i_j$ , not to $j$ ; since the indices strictly increase, so do the dimensions, and each inclusion is proper. An adapted list has exactly one vector per subspace; the $j$ -th vector may be taken anywhere in $W_j$ , including in the smaller $W_1, \dots, W_{j-1}$ , but the whole list must be orthonormal.

Every flag has an adapted list. Choose a basis of $W_1$ , extend it to a basis of $W_2$ (Theorem 1.6.5), then to $W_3$ , and so on up to $W_k$ . This gives a basis $\mathbf{v}_1, \dots, \mathbf{v}_{i_k}$ of $W_k$ whose first $i_j$ members span $W_j$ . Applying Theorem 11.2.2 yields an orthonormal list $\mathbf{e}_1, \dots, \mathbf{e}_{i_k}$ with $\operatorname{span}(\mathbf{e}_1, \dots, \mathbf{e}_{i_j}) = W_j$ for each $j$ , and $(\mathbf{e}_{i_1}, \dots, \mathbf{e}_{i_k})$ is adapted to $\mathcal{W}$ .

Four cases to keep in mind.

One index. For $k = 1$ a flag is a single subspace $W_1$ of dimension $i_1$ , and an adapted list is a single unit vector in it.
An initial segment. For the index set $(1, 2, \dots, k)$ , $W_j$ has dimension $j$ . An adapted list is then an orthonormal basis of $W_k$ whose first $j$ vectors span $W_j$ , since $j$ orthonormal vectors in the $j$ -dimensional $W_j$ span it. With $k = n$ this is Chapter 9’s complete flag.
The eigenflag. Let $(\mathbf{u}_1, \dots, \mathbf{u}_n)$ be an orthonormal basis of $F^n$ with $\mathbf{A}\mathbf{u}_p = \lambda_p(\mathbf{A})\mathbf{u}_p$ , and put $W_j = \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{i_j})$ . This is a flag of type $(i_1, \dots, i_k)$ , and $(\mathbf{u}_{i_1}, \dots, \mathbf{u}_{i_k})$ is adapted to it, since $\mathbf{u}_{i_j}$ is among the vectors spanning $W_j$ .
The degenerate case $k = n$ . Then $i_j = j$ is forced, $W_n = F^n$ , and an adapted list is an orthonormal basis of $F^n$ whose first $j$ vectors span $W_j$ .

A minimal change breaks adaptedness. For the eigenflag of type $(1, 3)$ in $F^3$ , namely $\operatorname{span}(\mathbf{u}_1) \subset F^3$ , the list $(\mathbf{u}_1, \mathbf{u}_3)$ is adapted. Swap the two vectors to get $(\mathbf{u}_3, \mathbf{u}_1)$ . It is still orthonormal and its members still lie in $W_2 = F^3$ , but the clause $\mathbf{x}_1 \in W_1$ fails: $\mathbf{u}_3 \notin \operatorname{span}(\mathbf{u}_1)$ .

Why this definition? Orthonormality is what makes $\sum_j \langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle$ the trace of a compression, which is what Theorem 17.6.2 controls. The nesting will let us orthonormalize a list by Gram–Schmidt without moving any vector out of its own subspace, since Gram–Schmidt keeps the $j$ -th vector in the span of the first $j$ .

Quick check. In $\mathbb{R}^3$ , take the flag $W_1 = \operatorname{span}(\mathbf{e}_1) \subset W_2 = \operatorname{span}(\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3)$ , of type $(1, 3)$ . Which of these lists are adapted to it: (a) $(\mathbf{e}_1, \mathbf{e}_3)$ ; (b) $(\mathbf{e}_3, \mathbf{e}_1)$ ; (c) $(\mathbf{e}_1, \mathbf{e}_1 + \mathbf{e}_2)$ ; (d) $(-\mathbf{e}_1, \tfrac{1}{\sqrt2}(\mathbf{e}_2 - \mathbf{e}_3))$ ?

Solution.

(a) Yes: orthonormal, $\mathbf{e}_1 \in W_1$ and $\mathbf{e}_3 \in W_2$ . (b) No: $\mathbf{x}_1 = \mathbf{e}_3$ is not in $W_1$ . (c) No: the list is not orthonormal, since $\langle \mathbf{e}_1, \mathbf{e}_1 + \mathbf{e}_2 \rangle = 1$ and $\left\| \mathbf{e}_1 + \mathbf{e}_2 \right\| = \sqrt2$ . (d) Yes: $-\mathbf{e}_1 \in W_1$ , the second vector has length $1$ and is orthogonal to $\mathbf{e}_1$ , and every vector lies in $W_2 = \mathbb{R}^3$ .

17.7.3. Wielandt’s minimax principle

The eigenflag guarantees every adapted list a large sum, and no flag of the same type can guarantee more. That is the statement; the second half is the hard one.

Theorem 17.7.1 (Wielandt’s Minimax Principle)

Let $\mathbf{A} \in M_n(F)$ be Hermitian, with $F = \mathbb{R}$ or $\mathbb{C}$ , and let $1 \le i_1 < \dots < i_k \le n$ .

(a) For every flag $\mathcal{W}$ of type $(i_1, \dots, i_k)$ there is a list $(\mathbf{x}_1, \dots, \mathbf{x}_k)$ adapted to $\mathcal{W}$ with $\sum_{j=1}^{k}\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle \ \le\ \sum_{j=1}^{k}\lambda_{i_j}(\mathbf{A}) .$
(b) Let $(\mathbf{u}_1, \dots, \mathbf{u}_n)$ be an orthonormal basis with $\mathbf{A}\mathbf{u}_p = \lambda_p(\mathbf{A})\mathbf{u}_p$ for every $p$ , and let $\mathcal{W}^{\mathbf{A}}$ be the flag $W_j = \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{i_j})$ . Then every list $(\mathbf{x}_1, \dots, \mathbf{x}_k)$ adapted to $\mathcal{W}^{\mathbf{A}}$ satisfies $\sum_{j=1}^{k}\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle \ \ge\ \sum_{j=1}^{k}\lambda_{i_j}(\mathbf{A}) ,$ with equality for $\mathbf{x}_j = \mathbf{u}_{i_j}$ .
(c) Consequently $\sum_{j=1}^{k}\lambda_{i_j}(\mathbf{A}) = \max_{\mathcal{W}}\ \min_{(\mathbf{x}_1, \dots, \mathbf{x}_k)}\ \sum_{j=1}^{k}\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle ,$ where $\mathcal{W}$ runs over all flags of type $(i_1, \dots, i_k)$ in $F^n$ , and for each $\mathcal{W}$ the list runs over all lists adapted to $\mathcal{W}$ . The inner minimum exists for every $\mathcal{W}$ , and the outer maximum is attained at $\mathcal{W}^{\mathbf{A}}$ .

Idea. Two inequalities of different characters, as in Theorem 17.2.3. In both, the sum $\sum_j\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle$ is the trace of the compression $\mathbf{B}$ of $\mathbf{A}$ to the span of the list, so it is $\sum_j\lambda_j(\mathbf{B})$ . Both parts therefore come down to comparing $\lambda_j(\mathbf{B})$ with $\lambda_{i_j}(\mathbf{A})$ , one $j$ at a time, by Courant–Fischer applied to the small matrix $\mathbf{B}$ .

For (b), the first $j$ vectors of the list lie in $\operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{i_j})$ , where $R_{\mathbf{A}} \ge \lambda_{i_j}(\mathbf{A})$ , so $\lambda_j(\mathbf{B}) \ge \lambda_{i_j}(\mathbf{A})$ .

For (a), we need a list whose span $X$ meets each bottom span $L_{i_j} = \operatorname{span}(\mathbf{u}_{i_j}, \dots, \mathbf{u}_n)$ in dimension at least $k - j + 1$ , since $R_{\mathbf{A}} \le \lambda_{i_j}(\mathbf{A})$ there. For a single $j$ , Lemma 17.2.1 gives such a meeting. For all $j$ at once, with one $X$ , it does not: the vectors chosen for different $j$ can collide, and the example after the proof shows that they do. The remedy is to count in coordinates. Record, for each vector, the first eigenvector coordinate at which it is non-zero; vectors with different first coordinates are independent; and a greedy choice of these first coordinates achieves every count at once.

Step roadmap. A preliminary claim turns bounds on $R_{\mathbf{A}}$ over subspaces into bounds on the eigenvalues of a compression. Step 1 proves (b). Step 2 introduces leading indices and makes the greedy selection. Step 3 orthonormalizes the selected vectors and proves (a). Step 4 proves that the inner minimum exists, which is the only place analysis enters, and deduces (c).

Proof. Let $(\mathbf{u}_1, \dots, \mathbf{u}_n)$ be an orthonormal basis of $F^n$ with $\mathbf{A}\mathbf{u}_p = \lambda_p(\mathbf{A})\mathbf{u}_p$ for every $p$ ; such a basis exists by Corollary 12.4.3 over $\mathbb{C}$ or Corollary 12.5.2 over $\mathbb{R}$ . For part (b) take the basis named there; for part (a) any such basis will do. Abbreviate $\lambda_p = \lambda_p(\mathbf{A})$ . For $1 \le p \le n$ put $L_p = \operatorname{span}(\mathbf{u}_p, \mathbf{u}_{p+1}, \dots, \mathbf{u}_n), \qquad L_{n+1} = \{\mathbf{0}\} .$ By Lemma 17.3.1, $R_{\mathbf{A}}(\mathbf{x}) \le \lambda_p$ for every non-zero $\mathbf{x} \in L_p$ , and $R_{\mathbf{A}}(\mathbf{x}) \ge \lambda_p$ for every non-zero $\mathbf{x} \in \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_p)$ .

Claim. Claim 1 (compression bounds). Let $(\mathbf{y}_1, \dots, \mathbf{y}_k)$ be orthonormal, let $Y$ be its span, let $\mathbf{Q} \in M_{n \times k}(F)$ have columns $\mathbf{y}_1, \dots, \mathbf{y}_k$ , and let $\mathbf{B} = \mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ be the compression of Definition 17.6.1. Let $1 \le m \le k$ and $c \in \mathbb{R}$ .

(i) If $S \subseteq Y$ is a subspace with $\dim S = m$ and $R_{\mathbf{A}}(\mathbf{x}) \ge c$ for every non-zero $\mathbf{x} \in S$ , then $\lambda_m(\mathbf{B}) \ge c$ .
(ii) If $S \subseteq Y$ is a subspace with $\dim S = k - m + 1$ and $R_{\mathbf{A}}(\mathbf{x}) \le c$ for every non-zero $\mathbf{x} \in S$ , then $\lambda_m(\mathbf{B}) \le c$ .

Moreover $\sum_{j=1}^{k}\langle \mathbf{A}\mathbf{y}_j, \mathbf{y}_j \rangle = \operatorname{tr}\mathbf{B} = \sum_{j=1}^{k}\lambda_j(\mathbf{B})$ .

Proof. The matrix $\mathbf{B}$ is Hermitian, and the map $\mathbf{c} \mapsto \mathbf{Q}\mathbf{c}$ is a linear bijection $F^k \to Y$ with $R_{\mathbf{B}}(\mathbf{c}) = R_{\mathbf{A}}(\mathbf{Q}\mathbf{c})$ for $\mathbf{c} \ne \mathbf{0}$ , as computed in the proof of Lemma 17.2.2. Let $S' = \{\mathbf{c} \in F^k : \mathbf{Q}\mathbf{c} \in S\}$ ; it is a subspace, and $\mathbf{c} \mapsto \mathbf{Q}\mathbf{c}$ maps it bijectively onto $S$ , so $\dim S' = \dim S$ .

(i) By the max–min line of Theorem 17.2.3 for $\mathbf{B} \in M_k(F)$ , $\lambda_m(\mathbf{B})$ is the largest of the numbers $\min_{\mathbf{0}\ne\mathbf{c}\in T}R_{\mathbf{B}}(\mathbf{c})$ over subspaces $T \subseteq F^k$ of dimension $m$ . Taking $T = S'$ , $\lambda_m(\mathbf{B}) \ \ge\ \min_{\mathbf{0}\ne\mathbf{c}\in S'}R_{\mathbf{B}}(\mathbf{c}) = \min_{\mathbf{0}\ne\mathbf{x}\in S}R_{\mathbf{A}}(\mathbf{x}) \ \ge\ c .$
(ii) By the min–max line of Theorem 17.2.3 for $\mathbf{B}$ , with $T = S'$ of dimension $k - m + 1$ , $\lambda_m(\mathbf{B}) \ \le\ \max_{\mathbf{0}\ne\mathbf{c}\in S'}R_{\mathbf{B}}(\mathbf{c}) = \max_{\mathbf{0}\ne\mathbf{x}\in S}R_{\mathbf{A}}(\mathbf{x}) \ \le\ c .$

Finally, the diagonal entries of $\mathbf{B}$ are $\langle \mathbf{A}\mathbf{y}_j, \mathbf{y}_j \rangle$ by Definition 17.6.1, and the trace of the Hermitian $\mathbf{B}$ is the sum of its eigenvalues by Corollary 12.1.4.

Step 1. The eigenflag guarantees the sum: part (b). Let $(\mathbf{x}_1, \dots, \mathbf{x}_k)$ be adapted to $\mathcal{W}^{\mathbf{A}}$ , so $\mathbf{x}_j \in W_j = \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{i_j})$ . Fix $j$ and put $S = \operatorname{span}(\mathbf{x}_1, \dots, \mathbf{x}_j)$ . The list is orthonormal, hence independent, so $\dim S = j$ . Each $\mathbf{x}_m$ with $m \le j$ lies in $W_m \subseteq W_j$ , so $S \subseteq W_j$ , where $R_{\mathbf{A}} \ge \lambda_{i_j}$ . By Claim 1 (i) with $m = j$ , $\lambda_j(\mathbf{B}) \ge \lambda_{i_j}$ , where $\mathbf{B}$ is the compression to the span of the list. Summing over $j$ and using the last line of Claim 1, $\sum_{j=1}^{k}\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle = \sum_{j=1}^{k}\lambda_j(\mathbf{B}) \ \ge\ \sum_{j=1}^{k}\lambda_{i_j} .$ For $\mathbf{x}_j = \mathbf{u}_{i_j}$ each term is $\langle \mathbf{A}\mathbf{u}_{i_j}, \mathbf{u}_{i_j} \rangle = \lambda_{i_j}$ , so equality holds. This proves (b).

Step 2. Leading indices, and a selection. Let $\mathcal{W} = (W_1, \dots, W_k)$ be an arbitrary flag of type $(i_1, \dots, i_k)$ . For $\mathbf{x} \in F^n$ write $c_p(\mathbf{x}) = \langle \mathbf{x}, \mathbf{u}_p \rangle$ , so that $\mathbf{x} = \sum_p c_p(\mathbf{x})\mathbf{u}_p$ by Theorem 11.2.1 (a). Then $\mathbf{x} \in L_p$ exactly when $c_1(\mathbf{x}) = \dots = c_{p-1}(\mathbf{x}) = 0$ . The leading index $\ell(\mathbf{x})$ of a non-zero $\mathbf{x}$ is the smallest $p$ with $c_p(\mathbf{x}) \ne 0$ , so that $\mathbf{x} \in L_p \iff \ell(\mathbf{x}) \ge p \qquad (\mathbf{x} \ne \mathbf{0}) .$ For a subspace $V \subseteq F^n$ , let $J(V)$ be the set of $p \in \{1, \dots, n\}$ with $V \cap L_{p+1} \ne V \cap L_p$ . These are the indices at which the chain $V = V \cap L_1 \supseteq V \cap L_2 \supseteq \dots \supseteq V \cap L_{n+1} = \{\mathbf{0}\}$ gets strictly smaller.

Claim. Claim 2 (the jumps count the dimension). For every subspace $V \subseteq F^n$ and every $1 \le p \le n+1$ , $\dim(V \cap L_p) = \bigl\lvert J(V) \cap \{p, p+1, \dots, n\} \bigr\rvert .$ In particular $\lvert J(V)\rvert = \dim V$ . Moreover, for each $p \in J(V)$ there is $\mathbf{x} \in V$ with $\ell(\mathbf{x}) = p$ .

Proof. Fix $p \le n$ . The map $\varphi_p \colon V \cap L_p \to F$ , $\mathbf{x} \mapsto c_p(\mathbf{x})$ , is linear. A vector of $V \cap L_p$ already has $c_1 = \dots = c_{p-1} = 0$ , so it lies in $L_{p+1}$ exactly when also $c_p = 0$ ; hence $\operatorname{ker}\varphi_p = V \cap L_{p+1}$ . By Theorem 2.3.1, $\dim(V \cap L_p) - \dim(V \cap L_{p+1}) = \operatorname{rank}\varphi_p ,$ and $\operatorname{rank}\varphi_p \le \dim F = 1$ . The rank is $1$ exactly when $\operatorname{ker}\varphi_p \ne V \cap L_p$ , that is, when $p \in J(V)$ . Adding these equations for $p, p+1, \dots, n$ , the left side telescopes to $\dim(V \cap L_p) - \dim(V \cap L_{n+1}) = \dim(V \cap L_p)$ , and the right side counts the elements of $J(V)$ that are $\ge p$ . This proves the formula, which for $p = n+1$ reads $0 = 0$ . At $p = 1$ , $L_1 = F^n$ gives $\lvert J(V)\rvert = \dim V$ . Finally, if $p \in J(V)$ , pick $\mathbf{x} \in (V \cap L_p) \setminus L_{p+1}$ ; then $c_1(\mathbf{x}) = \dots = c_{p-1}(\mathbf{x}) = 0 \ne c_p(\mathbf{x})$ , so $\ell(\mathbf{x}) = p$ .

Claim. Claim 3 (distinct leading indices force independence). Non-zero vectors $\mathbf{x}_1, \dots, \mathbf{x}_r$ whose leading indices are pairwise distinct are linearly independent.

Proof. Suppose $\sum_m a_m\mathbf{x}_m = \mathbf{0}$ with not all $a_m$ zero. Among the $m$ with $a_m \ne 0$ , let $m_0$ be the one with the smallest leading index, $q = \ell(\mathbf{x}_{m_0})$ . Apply $c_q$ . Every other $\mathbf{x}_m$ with $a_m \ne 0$ has $\ell(\mathbf{x}_m) > q$ , so $c_q(\mathbf{x}_m) = 0$ . Hence $0 = a_{m_0}c_q(\mathbf{x}_{m_0})$ , a product of two non-zero numbers, which is a contradiction.

Claim. Claim 4 (a greedy selection). There are non-zero vectors $\mathbf{x}_1, \dots, \mathbf{x}_k$ with $\mathbf{x}_m \in W_m$ , with pairwise distinct leading indices $q_m = \ell(\mathbf{x}_m)$ , and such that for every $j$ , $\#\{\, m : q_m \ge i_j \,\} \ \ge\ k - j + 1 .$

Proof. Choose $q_1, \dots, q_k$ in turn: $q_m$ is the largest element of $J(W_m)$ not among $q_1, \dots, q_{m-1}$ . This is possible, because $J(W_m)$ has $\dim W_m = i_m \ge m$ elements by Claim 2, so at most $m - 1$ of them are used. By the last part of Claim 2, pick $\mathbf{x}_m \in W_m$ with $\ell(\mathbf{x}_m) = q_m$ . The $q_m$ are distinct by construction.

Fix $j$ , and for $m \ge j - 1$ let $N_m$ be the number of $l \le m$ with $q_l \ge i_j$ . We show $N_m \ge m - j + 1$ by induction on $m$ . For $m = j - 1$ this says $N_{j-1} \ge 0$ , which is true. Let $m \ge j$ and assume $N_{m-1} \ge m - j$ .

Case 1: $q_m \ge i_j$ . Then $N_m = N_{m-1} + 1 \ge m - j + 1$ .

Case 2: $q_m < i_j$ . By Claim 2, $J(W_m)$ has $i_m$ elements, of which at most $i_j - 1$ are smaller than $i_j$ . So at least $i_m - i_j + 1$ of them are $\ge i_j$ , and $i_m - i_j \ge m - j$ because the indices are strictly increasing integers. Every element of $J(W_m)$ that is $\ge i_j$ exceeds $q_m$ , so by the choice of $q_m$ as the largest unused element, each of them is already among $q_1, \dots, q_{m-1}$ . These are at least $i_m - i_j + 1 \ge m - j + 1$ of the earlier $q_l$ , all $\ge i_j$ , so $N_{m-1} \ge m - j + 1$ . Hence $N_m = N_{m-1} \ge m - j + 1$ .

At $m = k$ this gives $N_k \ge k - j + 1$ , which is the claim.

Step 3. An adapted list with a small sum: part (a). Take $\mathbf{x}_1, \dots, \mathbf{x}_k$ from Claim 4. They are linearly independent by Claim 3, so Theorem 11.2.2 applies and produces an orthonormal list $(\mathbf{y}_1, \dots, \mathbf{y}_k)$ with $\operatorname{span}(\mathbf{y}_1, \dots, \mathbf{y}_j) = \operatorname{span}(\mathbf{x}_1, \dots, \mathbf{x}_j)$ for each $j$ . Since $\mathbf{x}_m \in W_m \subseteq W_j$ for $m \le j$ , the vector $\mathbf{y}_j$ lies in $W_j$ . So $(\mathbf{y}_1, \dots, \mathbf{y}_k)$ is adapted to $\mathcal{W}$ .

Let $X = \operatorname{span}(\mathbf{y}_1, \dots, \mathbf{y}_k) = \operatorname{span}(\mathbf{x}_1, \dots, \mathbf{x}_k)$ , and let $\mathbf{B}$ be the compression of $\mathbf{A}$ to it with respect to the $\mathbf{y}_j$ . Fix $j$ . By Claim 4 at least $k - j + 1$ of the $\mathbf{x}_m$ have $q_m \ge i_j$ ; each of them lies in $L_{i_j}$ , and any $k - j + 1$ of them are independent by Claim 3. Let $S$ be the span of $k - j + 1$ of them, so $S \subseteq X \cap L_{i_j}$ and $\dim S = k - j + 1$ . On $S \subseteq L_{i_j}$ we have $R_{\mathbf{A}} \le \lambda_{i_j}$ , so Claim 1 (ii) with $m = j$ gives $\lambda_j(\mathbf{B}) \le \lambda_{i_j}$ . Summing over $j$ and using the last line of Claim 1, $\sum_{j=1}^{k}\langle \mathbf{A}\mathbf{y}_j, \mathbf{y}_j \rangle = \sum_{j=1}^{k}\lambda_j(\mathbf{B}) \ \le\ \sum_{j=1}^{k}\lambda_{i_j} .$ This proves (a).

Step 4. The minimum exists, and the max–min formula: part (c). Fix a flag $\mathcal{W}$ . Identify a list $(\mathbf{x}_1, \dots, \mathbf{x}_k)$ with the column of $F^{nk}$ obtained by stacking the $\mathbf{x}_j$ ; its Euclidean norm is $(\sum_j\left\| \mathbf{x}_j \right\|^2)^{1/2}$ . Let $\mathcal{O}$ be the set of lists adapted to $\mathcal{W}$ . It is non-empty, by the paragraph after Definition 17.7.1. It is bounded, since every element has norm $\sqrt{k}$ . And it contains the limit of each of its convergent sequences. Indeed, the conditions $\langle \mathbf{x}_i, \mathbf{x}_j \rangle = \delta_{ij}$ are equations between sums of products of the entries and their conjugates, which pass to limits. Each condition $\mathbf{x}_j \in W_j$ says $\mathbf{M}_j\mathbf{x}_j = \mathbf{0}$ for a matrix $\mathbf{M}_j$ whose null space is $W_j$ , for instance the matrix whose rows are the conjugate transposes of a basis of $W_j^{\perp}$ (the zero matrix if $W_j = F^n$ ), and this passes to limits too. So by fact (A3) of Chapter 16’s introduction, every sequence in $\mathcal{O}$ has a subsequence converging to a point of $\mathcal{O}$ . The function $(\mathbf{x}_1, \dots, \mathbf{x}_k) \mapsto \sum_j\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle$ is built from the real and imaginary parts of the entries by sums and products, so it is continuous, and it is real-valued since $\mathbf{A}$ is Hermitian. By fact (A4) it attains a minimum on $\mathcal{O}$ .

Call that minimum $v(\mathcal{W})$ . By (a), some adapted list has sum $\le \sum_j\lambda_{i_j}$ , so $v(\mathcal{W}) \le \sum_j\lambda_{i_j}$ for every $\mathcal{W}$ . By (b), every list adapted to $\mathcal{W}^{\mathbf{A}}$ has sum $\ge \sum_j\lambda_{i_j}$ , with equality at $(\mathbf{u}_{i_1}, \dots, \mathbf{u}_{i_k})$ , so $v(\mathcal{W}^{\mathbf{A}}) = \sum_j\lambda_{i_j}$ . Hence the largest value of $v(\mathcal{W})$ over all flags of the type exists, is attained at $\mathcal{W}^{\mathbf{A}}$ , and equals $\sum_j\lambda_{i_j}$ . This proves (c), and the theorem.

Remark. Where the analysis went. Parts (a) and (b) are pure algebra: a dimension count, Gram–Schmidt, and Courant–Fischer for a small matrix. The only analytic input is in Step 4, facts (A3) and (A4) of Chapter 16’s introduction. This is the first time in the chapter that an item of that list is used rather than merely mentioned, and it is used only so that the word “min” in (c) refers to a value that is attained. Every later result in this section uses (a) and (b) alone, so no later result depends on analysis; only the exercises that quote (c), such as A1(b), lean on the attained minimum.

Two index sets give back what we already have. For $k = 1$ a flag is a single subspace $W$ of dimension $i_1$ , an adapted list is a unit vector $\mathbf{x} \in W$ , and $\langle \mathbf{A}\mathbf{x}, \mathbf{x} \rangle = R_{\mathbf{A}}(\mathbf{x})$ . So (c) reads $\lambda_{i_1}(\mathbf{A}) = \max_{\dim W = i_1}\min_{\mathbf{0}\ne\mathbf{x}\in W}R_{\mathbf{A}}(\mathbf{x})$ , the max–min line of Theorem 17.2.3. For the initial segment $(1, \dots, k)$ , an adapted list is an orthonormal basis of the $k$ -dimensional $W_k$ , and conversely every orthonormal basis $(\mathbf{x}_1, \dots, \mathbf{x}_k)$ of a $k$ -dimensional subspace is adapted to the flag $\operatorname{span}(\mathbf{x}_1) \subset \operatorname{span}(\mathbf{x}_1, \mathbf{x}_2) \subset \dots$ . The sum $\sum_j\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle$ is the trace of the compression to $W_k$ . That trace does not depend on the orthonormal basis, because §06 showed that a change of orthonormal basis changes the compression by a unitary similarity. So the inner minimum is constant, and (c) says that $\sum_{j\le k}\lambda_j(\mathbf{A})$ is the largest trace of a compression to a $k$ -dimensional subspace, which is Theorem 17.6.2. What is new is everything in between: index sets with gaps, such as $(2, 4)$ , and index sets that do not start at $1$ .

Example (The selection at work, and why it is needed)

Let $\mathbf{A} = \operatorname{diag}(4, 2, 1, -1) \in M_4(\mathbb{R})$ , take the index set $(2, 4)$ , and take the flag $W_1 = \operatorname{span}\bigl((1,1,0,0),\ \mathbf{e}_4\bigr) \ \subset\ W_2 = \mathbb{R}^4 ,$ of type $(2, 4)$ . Show that the naive attempt, choosing $\mathbf{x}_j \in W_j \cap L_{i_j}$ for each $j$ separately, cannot produce an adapted list. Then follow the proof of part (a) to produce one with sum at most $\lambda_2(\mathbf{A}) + \lambda_4(\mathbf{A})$ .

Solution. Here the eigenvectors are $\mathbf{u}_p = \mathbf{e}_p$ , so $L_p = \operatorname{span}(\mathbf{e}_p, \dots, \mathbf{e}_4)$ is the set of vectors whose first $p - 1$ entries vanish, and the target is $\lambda_2 + \lambda_4 = 2 + (-1) = 1$ .

The naive attempt. A vector $a(1,1,0,0) + b\mathbf{e}_4$ of $W_1$ lies in $L_2$ exactly when its first entry $a$ is $0$ , so $W_1 \cap L_2 = \operatorname{span}(\mathbf{e}_4)$ . Also $W_2 \cap L_4 = L_4 = \operatorname{span}(\mathbf{e}_4)$ . Both vectors would have to be multiples of $\mathbf{e}_4$ , and two such vectors are never orthonormal. Each of the two intersections is non-zero, as Lemma 17.2.1 promises, but the two choices collide.

The selection. The vectors of $W_1$ have the form $(a, a, 0, b)$ . They lie in $L_2$ , $L_3$ or $L_4$ exactly when $a = 0$ , and in $L_5 = \{\mathbf{0}\}$ only when also $b = 0$ . So the dimensions of $W_1 \cap L_p$ for $p = 1, \dots, 5$ are $2, 1, 1, 1, 0$ , and the chain drops at $p = 1$ and $p = 4$ : $J(W_1) = \{1, 4\}$ . For $W_2 = \mathbb{R}^4$ the dimensions are $4, 3, 2, 1, 0$ , so $J(W_2) = \{1, 2, 3, 4\}$ . The greedy rule takes $q_1 = \max J(W_1) = 4$ , with $\mathbf{x}_1 = \mathbf{e}_4 \in W_1$ . It then takes $q_2 = \max\bigl(J(W_2) \setminus \{4\}\bigr) = 3$ , with $\mathbf{x}_2 = \mathbf{e}_3$ .

The counts of Claim 4. For $j = 1$ , $i_1 = 2$ , and both $q_1 = 4$ and $q_2 = 3$ are $\ge 2$ : the count is $2 \ge 2$ . For $j = 2$ , $i_2 = 4$ , and only $q_1 = 4$ is $\ge 4$ : the count is $1 \ge 1$ . Notice that the requirement for $j = 2$ is met by $\mathbf{x}_1$ , not by $\mathbf{x}_2$ ; insisting that $\mathbf{x}_2$ itself lie in $L_4$ is exactly the naive attempt that failed.

The list and its sum. $(\mathbf{e}_4, \mathbf{e}_3)$ is already orthonormal, so Gram–Schmidt leaves it alone, and it is adapted: $\mathbf{e}_4 \in W_1$ , $\mathbf{e}_3 \in W_2$ . Its sum is $\langle \mathbf{A}\mathbf{e}_4, \mathbf{e}_4 \rangle + \langle \mathbf{A}\mathbf{e}_3, \mathbf{e}_3 \rangle = -1 + 1 = 0 \le 1$ . The compression to $X = \operatorname{span}(\mathbf{e}_4, \mathbf{e}_3)$ is $\operatorname{diag}(-1, 1)$ , with eigenvalues $1 \le \lambda_2(\mathbf{A}) = 2$ and $-1 \le \lambda_4(\mathbf{A}) = -1$ , as Step 3 predicts one index at a time.

Quick check. Suppose “orthonormal” is weakened to “each $\mathbf{x}_j$ is a unit vector” in the definition of an adapted list. Show that the formula (c) of Theorem 17.7.1 remains true. Why is this weaker version useless for comparing two matrices?

Solution. With the $\mathbf{x}_j$ chosen independently, the inner minimum splits as $\sum_j\min_{\mathbf{0}\ne\mathbf{x}\in W_j}R_{\mathbf{A}}(\mathbf{x})$ , one term per subspace. By Theorem 17.2.3 each term is at most $\lambda_{i_j}(\mathbf{A})$ , since $\dim W_j = i_j$ , and the eigenflag makes every term equal to $\lambda_{i_j}(\mathbf{A})$ at once. So the max–min is still $\sum_j\lambda_{i_j}(\mathbf{A})$ ; it is just Courant–Fischer added up. But the lists it produces are not orthonormal, so Theorem 17.6.2 cannot be applied to them. Comparing $\mathbf{A}$ with $\mathbf{B}$ through such lists gives only the summed Weyl bound $k\,\lambda_1(\mathbf{A} - \mathbf{B})$ of the first subsection. The whole content of Wielandt’s theorem is that orthonormality costs nothing.

17.7.4. Lidskii’s inequality

The plan of the first subsection can now be carried out.

Theorem 17.7.2 (Lidskii’s Inequality)

Let $\mathbf{A}, \mathbf{B} \in M_n(F)$ be Hermitian, with $F = \mathbb{R}$ or $\mathbb{C}$ . Then for every index set $1 \le i_1 < \dots < i_k \le n$ , $\sum_{j=1}^{k}\lambda_{i_j}(\mathbf{A}) - \sum_{j=1}^{k}\lambda_{i_j}(\mathbf{B}) \ \le\ \sum_{j=1}^{k}\lambda_j(\mathbf{A} - \mathbf{B}) .$

Idea. Find one orthonormal list that is good for both matrices. Take the eigenflag of $\mathbf{A}$ . Part (b) of Theorem 17.7.1 says that every list adapted to it is good for $\mathbf{A}$ . Part (a), applied to $\mathbf{B}$ and this same flag, produces one adapted list that is good for $\mathbf{B}$ . Subtract the two sums. What remains is $\sum_j\langle (\mathbf{A} - \mathbf{B})\mathbf{x}_j, \mathbf{x}_j \rangle$ over an orthonormal list, which Theorem 17.6.2 bounds by the top $k$ eigenvalues of $\mathbf{A} - \mathbf{B}$ .

Proof. Let $(\mathbf{u}_1, \dots, \mathbf{u}_n)$ be an orthonormal basis of $F^n$ with $\mathbf{A}\mathbf{u}_p = \lambda_p(\mathbf{A})\mathbf{u}_p$ , which exists by Corollary 12.4.3 or Corollary 12.5.2, and let $\mathcal{W}^{\mathbf{A}}$ be the flag $W_j = \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_{i_j})$ , of type $(i_1, \dots, i_k)$ . By Theorem 17.7.1 (a) applied to the Hermitian matrix $\mathbf{B}$ and the flag $\mathcal{W}^{\mathbf{A}}$ , there is a list $(\mathbf{x}_1, \dots, \mathbf{x}_k)$ adapted to $\mathcal{W}^{\mathbf{A}}$ with $\sum_{j=1}^{k}\langle \mathbf{B}\mathbf{x}_j, \mathbf{x}_j \rangle \ \le\ \sum_{j=1}^{k}\lambda_{i_j}(\mathbf{B}) .$ By Theorem 17.7.1 (b) applied to $\mathbf{A}$ , the same list satisfies $\sum_{j=1}^{k}\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle \ \ge\ \sum_{j=1}^{k}\lambda_{i_j}(\mathbf{A}) .$ Subtracting the first inequality from the second, and using that the inner product is linear in its first slot, $\sum_{j=1}^{k}\lambda_{i_j}(\mathbf{A}) - \sum_{j=1}^{k}\lambda_{i_j}(\mathbf{B}) \ \le\ \sum_{j=1}^{k}\langle (\mathbf{A} - \mathbf{B})\mathbf{x}_j, \mathbf{x}_j \rangle .$ The matrix $\mathbf{A} - \mathbf{B}$ is Hermitian and $\mathbf{x}_1, \dots, \mathbf{x}_k$ are orthonormal, so Theorem 17.6.2 bounds the right-hand side by $\sum_{j=1}^{k}\lambda_j(\mathbf{A} - \mathbf{B})$ . This proves the theorem.

For the rank-one example of the first subsection, the right-hand side is $\lambda_1 + \dots + \lambda_k$ of $\mathbf{u}\mathbf{u}^{*}$ , which is $1$ for every $k$ : the theorem gives exactly the bound that the interlacing argument found there, and it gives it for every Hermitian $\mathbf{A} - \mathbf{B}$ , whatever its rank. One feature of the statement deserves a warning.

Warning. The left side compares the two spectra at the same indices; the right side always uses the top $k$ eigenvalues of $\mathbf{A} - \mathbf{B}$ , whatever the index set. The tempting “index-by-index” version $\lambda_{i}(\mathbf{A}) - \lambda_{i}(\mathbf{B}) \ \le\ \lambda_{i}(\mathbf{A} - \mathbf{B})$ is false. Take $\mathbf{A} = \operatorname{diag}(1, 1)$ and $\mathbf{B} = \operatorname{diag}(1, 0)$ , so $\mathbf{A} - \mathbf{B} = \operatorname{diag}(0, 1)$ with $\lambda_1(\mathbf{A}-\mathbf{B}) = 1$ and $\lambda_2(\mathbf{A} - \mathbf{B}) = 0$ . At $i = 2$ the left side is $1 - 0 = 1$ , which exceeds $\lambda_2(\mathbf{A} - \mathbf{B}) = 0$ . Lidskii’s bound is $\lambda_1(\mathbf{A} - \mathbf{B}) = 1$ , and it is attained.

Example (All seven index sets)

Let $\mathbf{A} = \begin{pmatrix} 0 & 2 & 0 \\ 2 & 1 & 2 \\ 0 & 2 & 2 \end{pmatrix}, \qquad \mathbf{B} = \operatorname{diag}(0, 2, -1) .$ Find the three spectra, check Theorem 17.7.2 for every index set, and compare with the summed Weyl bound $k\,\lambda_1(\mathbf{A} - \mathbf{B})$ .

Solution. The spectra. The vectors $(1, 2, 2)$ , $(2, 1, -2)$ , $(2, -2, 1)$ are eigenvectors of $\mathbf{A}$ : for instance $\mathbf{A}(1,2,2) = (4, 2 + 2 + 4, 4 + 4) = 4(1,2,2)$ , and the other two give the eigenvalues $1$ and $-2$ in the same way. So $\boldsymbol{\uplambda}(\mathbf{A}) = (4, 1, -2)$ , writing $\boldsymbol{\uplambda}(\mathbf{A})$ for the vector of eigenvalues in decreasing order. Sorting the diagonal of $\mathbf{B}$ gives $\boldsymbol{\uplambda}(\mathbf{B}) = (2, 0, -1)$ . Next, $\mathbf{A} - \mathbf{B} = \begin{pmatrix} 0 & 2 & 0 \\ 2 & -1 & 2 \\ 0 & 2 & 3 \end{pmatrix}$ has eigenvectors $(1, 2, 4)$ , $(-2, -1, 1)$ , $(2, -3, 1)$ . For example $(\mathbf{A} - \mathbf{B})(1,2,4) = (4,\ 2 - 2 + 8,\ 4 + 12) = 4(1,2,4)$ . So $\boldsymbol{\uplambda}(\mathbf{A} - \mathbf{B}) = (4, 1, -3)$ , whose running totals from the top are $4, 5, 2$ .

The inequalities. The differences at equal indices are $\lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B}) = 2, 1, -1$ for $i = 1, 2, 3$ .

index set	left side	Lidskii bound	summed Weyl bound
$(1)$ , $(2)$ , $(3)$	$2,\ 1,\ -1$	$4$	$4$
$(1,2)$ , $(1,3)$ , $(2,3)$	$3,\ 1,\ 0$	$5$	$8$
$(1,2,3)$	$2$	$2$	$12$

Every inequality holds. For $k = 3$ it is an equality, and must be: both sides are then $\operatorname{tr}\mathbf{A} - \operatorname{tr}\mathbf{B} = \operatorname{tr}(\mathbf{A} - \mathbf{B})$ , by Corollary 12.1.4 and Theorem 0.9.6 (1). The summed Weyl bound grows like $k\,\lambda_1(\mathbf{A} - \mathbf{B})$ , while Lidskii’s bound can even decrease, because the eigenvalue $-3$ of $\mathbf{A} - \mathbf{B}$ enters the sum as soon as $k = 3$ .

The index sets that give the results we already have are the two families from the discussion of Wielandt’s theorem, now at the level of two matrices.

Corollary 17.7.3 (Weyl and Ky Fan as Cases of Lidskii)

Let $\mathbf{A}, \mathbf{B} \in M_n(F)$ be Hermitian.

(a) (One index.) For every $i$ , $\lambda_n(\mathbf{A} - \mathbf{B}) \ \le\ \lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B}) \ \le\ \lambda_1(\mathbf{A} - \mathbf{B}) ,$ and in particular $\lvert\lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B})\rvert \le \left\| \mathbf{A} - \mathbf{B} \right\|_2$ .
(b) (An initial segment.) For every $k$ , $\sum_{i=1}^{k}\lambda_i(\mathbf{A}) - \sum_{i=1}^{k}\lambda_i(\mathbf{B}) \ \le\ \sum_{i=1}^{k}\lambda_i(\mathbf{A} - \mathbf{B}) .$

Idea. Both are Theorem 17.7.2 with a particular index set, the lower bound in (a) coming from the same theorem with $\mathbf{A}$ and $\mathbf{B}$ exchanged.

Proof.

(a) The upper bound is Theorem 17.7.2 with $k = 1$ and the index set $(i)$ . Exchanging $\mathbf{A}$ and $\mathbf{B}$ in the same case gives $\lambda_i(\mathbf{B}) - \lambda_i(\mathbf{A}) \le \lambda_1(\mathbf{B} - \mathbf{A})$ . By Lemma 17.3.2 with $p = 1$ , $\lambda_1(\mathbf{B} - \mathbf{A}) = \lambda_1(-(\mathbf{A} - \mathbf{B})) = -\lambda_n(\mathbf{A} - \mathbf{B})$ , and multiplying by $-1$ gives the lower bound. So $\lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B})$ lies between $\lambda_n(\mathbf{A}-\mathbf{B})$ and $\lambda_1(\mathbf{A}-\mathbf{B})$ , and its absolute value is at most $\max\bigl(\lambda_1(\mathbf{A}-\mathbf{B}), -\lambda_n(\mathbf{A}-\mathbf{B})\bigr)$ , which is $\left\| \mathbf{A} - \mathbf{B} \right\|_2$ by Lemma 17.3.5.
(b) This is Theorem 17.7.2 with the index set $(1, 2, \dots, k)$ .

Read with $\mathbf{A} = \mathbf{X} + \mathbf{Y}$ and $\mathbf{B} = \mathbf{X}$ , part (a) is Corollary 17.3.4 for the pair $\mathbf{X}, \mathbf{Y}$ ; read with $\mathbf{B} = \mathbf{Y}$ instead, it is the same corollary with $\mathbf{X}$ and $\mathbf{Y}$ exchanged. Together these are the cases of Theorem 17.3.3 in which one of the two indices on the right is $1$ (in part (a) of that theorem) or $n$ (in its part (b)); applied to negated pairs, the one-index case gives a few more, as the remark below explains. The last clause of part (a) is Corollary 17.3.6. Part (b), read the same way, is Corollary 17.6.5. Here is the hierarchy, one row per index set.

index set	Theorem 17.7.1 gives	Theorem 17.7.2 gives
$(i)$ , one index	Theorem 17.2.3, max–min line	Theorem 17.3.3 with one index $1$ or $n$ (and, through negation, with $i + j - 1 = n$ ); Corollary 17.3.6
$(1, \dots, k)$	Theorem 17.6.2	Corollary 17.6.5
any other, such as $(2, 4)$	new	new

Remark. Not all of Weyl’s inequalities are cases of Lidskii’s. To test this fairly, Theorem 17.7.2 must be allowed every pair it can see: all pairs of matrices among $\pm\mathbf{X}$ , $\pm\mathbf{Y}$ , $\pm(\mathbf{X} + \mathbf{Y})$ whose difference is another of the six. Negation matters. With it, the one-index case already reaches some Weyl inequalities with both indices inside: applied to $\mathbf{A} = -\mathbf{X}$ , $\mathbf{B} = \mathbf{Y}$ , whose difference is $-(\mathbf{X}+\mathbf{Y})$ , and read through Lemma 17.3.2, it gives $\lambda_n(\mathbf{X} + \mathbf{Y}) \le \lambda_{n+1-i}(\mathbf{X}) + \lambda_i(\mathbf{Y})$ for every $i$ , which is exactly the Weyl inequality (a) with $i + j - 1 = n$ . So a small example that ignores negation can look like a counterexample and not be one.

Even with every signed pair allowed, the family does not contain all of Weyl’s. Take $n = 4$ and the candidate spectra $\begin{aligned} \boldsymbol{\uplambda}(\mathbf{X}) &= (2, 0, 0, -1), \qquad \boldsymbol{\uplambda}(\mathbf{Y}) = (2, 0, 0, 0), \\ \boldsymbol{\uplambda}(\mathbf{X} + \mathbf{Y}) &= (2, 1, 1, -1) . \end{aligned}$ The totals agree, $1 + 2 = 3$ , and a direct check of every index set shows that all twelve signed pairs satisfy every inequality of Theorem 17.7.2. Yet Weyl’s inequality with $i = j = 2$ demands $\lambda_3(\mathbf{X} + \mathbf{Y}) \le \lambda_2(\mathbf{X}) + \lambda_2(\mathbf{Y}) = 0$ , and here $\lambda_3(\mathbf{X} + \mathbf{Y}) = 1$ . Since Theorem 17.3.3 is a theorem, no Hermitian $\mathbf{X}$ , $\mathbf{Y}$ have these spectra: the lists are ruled out by Weyl and not by Lidskii.

Remark. The majorization form. Section 8 introduces the language that turns this family of inequalities into a single statement. We record the translation here, together with exactly what has been proved. For a real vector $\mathbf{x} \in \mathbb{R}^n$ , the sum of its $k$ largest entries is the largest value of $\sum_{i \in S}x_i$ over the sets $S$ of $k$ positions: sorting the entries shows that the $k$ largest do best. Apply this to $\mathbf{x} = \boldsymbol{\uplambda}(\mathbf{A}) - \boldsymbol{\uplambda}(\mathbf{B})$ , whose $i$ -th entry is $\lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B})$ and which need not be decreasing. Then Theorem 17.7.2, over all index sets of size $k$ , says that the $k$ largest entries of $\boldsymbol{\uplambda}(\mathbf{A}) - \boldsymbol{\uplambda}(\mathbf{B})$ add up to at most $\sum_{j\le k}\lambda_j(\mathbf{A} - \mathbf{B})$ , for every $k$ . The two vectors also have the same total, $\operatorname{tr}\mathbf{A} - \operatorname{tr}\mathbf{B} = \operatorname{tr}(\mathbf{A} - \mathbf{B})$ . In the notation of Section 8 this is $\boldsymbol{\uplambda}(\mathbf{A}) - \boldsymbol{\uplambda}(\mathbf{B}) \ \prec\ \boldsymbol{\uplambda}(\mathbf{A} - \mathbf{B}) .$ Proved here: every inequality in this majorization, namely Theorem 17.7.2 for every index set, and the equality of totals, which is the trace. Not proved here, and left to Chapter 21: the general consequences of a majorization $\mathbf{x} \prec \mathbf{y}$ , namely $\sum_i\phi(x_i) \le \sum_i\phi(y_i)$ for every convex $\phi \colon \mathbb{R} \to \mathbb{R}$ , together with the matching statement for the unitarily invariant norms of that chapter. Applied to the display above, they bound $\sum_i\phi\bigl(\lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B})\bigr)$ by $\sum_i\phi\bigl(\lambda_i(\mathbf{A} - \mathbf{B})\bigr)$ for every convex $\phi$ . One case, $\phi(t) = \lvert t\rvert$ , follows from this section directly, and exercise C2 proves it. Nothing in this chapter uses the general case.

17.7.5. What the flags bought

Courant–Fischer turned each eigenvalue into an optimization that two matrices can share, and the comparison theorems of §§02–05 followed one index at a time. Ky Fan did the same for the top partial sums. Wielandt’s theorem does it for every sum, at the price of optimizing over flags instead of subspaces, and Lidskii’s inequality is what the shared optimization yields: the eigenvalue shifts $\lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B})$ , summed over any $k$ indices, never exceed the top $k$ eigenvalues of $\mathbf{A} - \mathbf{B}$ . The single idea behind it is the one the first subsection isolated. A comparison of sums needs one orthonormal list that serves both matrices, and a flag is exactly the structure that lets such a list be found by counting.

17.7.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define a flag of type $(i_1, \dots, i_k)$ in $F^n$ and a list adapted to it.
(b) State the max–min formula of Theorem 17.7.1, and name the index sets for which it reduces to Theorem 17.2.3 and to Theorem 17.6.2.
(c) Determine whether the following is true, and justify your answer: if $(\mathbf{x}_1, \dots, \mathbf{x}_k)$ is adapted to a flag $(W_1, \dots, W_k)$ , then $\operatorname{span}(\mathbf{x}_1, \dots, \mathbf{x}_j) = W_j$ for every $j$ .
(d) Determine whether the following is true for all Hermitian $\mathbf{A}, \mathbf{B} \in M_n(F)$ , and justify your answer: $\lambda_2(\mathbf{A}) - \lambda_2(\mathbf{B}) \le \lambda_2(\mathbf{A} - \mathbf{B})$ .
(e) In the proof of Theorem 17.7.2, which part of Theorem 17.7.1 is applied to $\mathbf{A}$ , which to $\mathbf{B}$ , and with which flag?

Solution.

(a) For an index set $1 \le i_1 < \dots < i_k \le n$ , a flag of that type is a list $(W_1, \dots, W_k)$ of subspaces of $F^n$ with $W_1 \subseteq \dots \subseteq W_k$ and $\dim W_j = i_j$ . A list $(\mathbf{x}_1, \dots, \mathbf{x}_k)$ is adapted to it if it is orthonormal and $\mathbf{x}_j \in W_j$ for every $j$ .
(b) $\sum_j\lambda_{i_j}(\mathbf{A})$ is the maximum over flags $\mathcal{W}$ of type $(i_1, \dots, i_k)$ of the minimum of $\sum_j\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle$ over lists adapted to $\mathcal{W}$ . For $k = 1$ , with index set $(i)$ , it is the max–min line of Courant–Fischer for $\lambda_i$ . For the initial segment $(1, \dots, k)$ it is Ky Fan’s theorem for $\sum_{j\le k}\lambda_j$ .
(c) False in general. The span of $j$ orthonormal vectors has dimension $j$ , while $\dim W_j = i_j$ , which exceeds $j$ unless $i_j = j$ . For instance, with $k = 1$ and the flag $W_1 = \mathbb{R}^2$ of type $(2)$ , the adapted list $(\mathbf{e}_1)$ spans a line. What is true is $\operatorname{span}(\mathbf{x}_1, \dots, \mathbf{x}_j) \subseteq W_j$ .
(d) False. With $\mathbf{A} = \operatorname{diag}(1,1)$ and $\mathbf{B} = \operatorname{diag}(1,0)$ , the left side is $1 - 0 = 1$ and $\lambda_2(\mathbf{A} - \mathbf{B}) = \lambda_2(\operatorname{diag}(0,1)) = 0$ . The correct bound, from Theorem 17.7.2 with $k = 1$ , is $\lambda_1(\mathbf{A} - \mathbf{B})$ .
(e) The flag is the eigenflag $\mathcal{W}^{\mathbf{A}}$ of $\mathbf{A}$ for the given index set. Part (b) is applied to $\mathbf{A}$ : every list adapted to $\mathcal{W}^{\mathbf{A}}$ has $\mathbf{A}$ -sum at least $\sum_j\lambda_{i_j}(\mathbf{A})$ . Part (a) is applied to $\mathbf{B}$ with the same flag: some adapted list has $\mathbf{B}$ -sum at most $\sum_j\lambda_{i_j}(\mathbf{B})$ .

B. Practice

Exercise (B1: Running the selection)

Let $\mathbf{A} = \operatorname{diag}(4, 1, -1) \in M_3(\mathbb{R})$ , take the index set $(1, 3)$ , and let $\mathcal{W}$ be the flag $W_1 = \operatorname{span}\bigl((1,1,1)\bigr) \subset W_2 = \mathbb{R}^3$ .

(a) Compute $\lambda_1(\mathbf{A}) + \lambda_3(\mathbf{A})$ , and show directly that every list adapted to the eigenflag $\operatorname{span}(\mathbf{e}_1) \subset \mathbb{R}^3$ has sum at least this number.
(b) Follow the proof of Theorem 17.7.1 (a) for $\mathcal{W}$ : find $J(W_1)$ and $J(W_2)$ , select $\mathbf{x}_1, \mathbf{x}_2$ , apply Gram–Schmidt, and compute $\sum_j\langle \mathbf{A}\mathbf{y}_j, \mathbf{y}_j \rangle$ .
(c) Compute the compression $\mathbf{B}$ of $\mathbf{A}$ to $\operatorname{span}(\mathbf{y}_1, \mathbf{y}_2)$ and its eigenvalues, and check $\lambda_j(\mathbf{B}) \le \lambda_{i_j}(\mathbf{A})$ for $j = 1, 2$ .
(d) Find the minimum of $\sum_j\langle \mathbf{A}\mathbf{x}_j, \mathbf{x}_j \rangle$ over all lists adapted to $\mathcal{W}$ . Is it the value found in (b)?

Solution.

(a) The eigenvalues are $4, 1, -1$ with eigenvectors $\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3$ , so $\lambda_1 + \lambda_3 = 3$ , and $\operatorname{span}(\mathbf{e}_1) \subset \mathbb{R}^3$ is the eigenflag of type $(1, 3)$ . An adapted list has $\mathbf{x}_1 = \pm\mathbf{e}_1$ , the unit vectors of the line, so $\langle \mathbf{A}\mathbf{x}_1, \mathbf{x}_1 \rangle = 4$ . Its $\mathbf{x}_2$ is a unit vector orthogonal to $\mathbf{e}_1$ , so $\mathbf{x}_2 = (0, b, c)$ with $b^2 + c^2 = 1$ , and $\langle \mathbf{A}\mathbf{x}_2, \mathbf{x}_2 \rangle = b^2 - c^2 \ge -1$ . The sum is at least $4 - 1 = 3$ , with equality at $\mathbf{x}_2 = \pm\mathbf{e}_3$ , as part (b) of the theorem says.
(b) Here $L_p = \operatorname{span}(\mathbf{e}_p, \dots, \mathbf{e}_3)$ . The line $W_1$ is spanned by $\mathbf{w} = (1,1,1)$ , whose first entry is non-zero, so $W_1 \cap L_2 = \{\mathbf{0}\}$ and $J(W_1) = \{1\}$ . For $W_2 = \mathbb{R}^3$ , $J(W_2) = \{1, 2, 3\}$ . The greedy rule gives $q_1 = 1$ with $\mathbf{x}_1 = \mathbf{w}$ , and $q_2 = \max\{2, 3\} = 3$ with $\mathbf{x}_2 = \mathbf{e}_3$ . The counts of Claim 4 hold: for $j = 1$ , both $q$ ’s are $\ge i_1 = 1$ ; for $j = 2$ , $q_2 = 3 \ge i_2 = 3$ . Gram–Schmidt gives $\mathbf{y}_1 = \tfrac{1}{\sqrt3}(1,1,1)$ and $\mathbf{e}_3 - \langle \mathbf{e}_3, \mathbf{y}_1 \rangle\mathbf{y}_1 = \tfrac13(-1, -1, 2), \qquad \mathbf{y}_2 = \tfrac{1}{\sqrt6}(-1, -1, 2) .$ Then $\langle \mathbf{A}\mathbf{y}_1, \mathbf{y}_1 \rangle = \tfrac13(4 + 1 - 1) = \tfrac43$ and $\langle \mathbf{A}\mathbf{y}_2, \mathbf{y}_2 \rangle = \tfrac16(4 + 1 - 4) = \tfrac16$ , so the sum is $\tfrac32 \le 3$ , as the theorem requires.
(c) The off-diagonal entry is $\langle \mathbf{A}\mathbf{y}_2, \mathbf{y}_1 \rangle = \tfrac{1}{\sqrt{18}}(-4 - 1 - 2) = -\tfrac{7}{3\sqrt2}$ , so $\mathbf{B} = \begin{pmatrix} 4/3 & -7/(3\sqrt2) \\ -7/(3\sqrt2) & 1/6 \end{pmatrix}, \qquad \operatorname{tr}\mathbf{B} = \tfrac32, \quad \det\mathbf{B} = \tfrac29 - \tfrac{49}{18} = -\tfrac52 .$ The characteristic polynomial is $t^2 - \tfrac32 t - \tfrac52$ , that is $\tfrac12(2t - 5)(t + 1)$ , so $\lambda_1(\mathbf{B}) = \tfrac52 \le 4 = \lambda_1(\mathbf{A})$ and $\lambda_2(\mathbf{B}) = -1 \le -1 = \lambda_3(\mathbf{A})$ . The second is an equality, as it must be: Theorem 17.6.1 with $n = 3$ , $k = 2$ gives the reverse bound $\lambda_2(\mathbf{B}) \ge \lambda_3(\mathbf{A})$ .
(d) An adapted list has $\mathbf{x}_1 = \pm\mathbf{y}_1$ , contributing $\tfrac43$ , and $\mathbf{x}_2$ is any unit vector of $\mathbf{w}^{\perp}$ . By Lemma 17.2.2 the smallest value of $\langle \mathbf{A}\mathbf{x}_2, \mathbf{x}_2 \rangle$ there is the smallest eigenvalue of the compression of $\mathbf{A}$ to $\mathbf{w}^{\perp}$ . With the orthonormal basis $\tfrac1{\sqrt2}(1,-1,0)$ , $\tfrac1{\sqrt6}(1,1,-2)$ of $\mathbf{w}^{\perp}$ , that compression is $\begin{pmatrix} 5/2 & \sqrt3/2 \\ \sqrt3/2 & 1/6 \end{pmatrix},$ with trace $\tfrac83$ , determinant $\tfrac5{12} - \tfrac34 = -\tfrac13$ , and characteristic polynomial $\tfrac13(3t^2 - 8t - 1)$ . Its smaller eigenvalue is $\tfrac13(4 - \sqrt{19})$ . So the minimum over lists adapted to $\mathcal{W}$ is $\tfrac43 + \tfrac13(4 - \sqrt{19}) = \tfrac13(8 - \sqrt{19}) \approx 1.214 .$ This is smaller than $\tfrac32$ . The construction in the proof finds an adapted list below the bound $3$ , which is all part (a) asks; it need not find the best one. Both numbers are below $3$ , the value at the eigenflag, as part (c) requires.

Exercise (B2: A complex pair)

Let $\mathbf{A} = \begin{pmatrix} 2 & 1 + i \\ 1 - i & 1 \end{pmatrix}, \qquad \mathbf{B} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \quad\text{in } M_2(\mathbb{C}) .$

(a) Check that $\mathbf{A}$ and $\mathbf{B}$ are Hermitian, and compute $\boldsymbol{\uplambda}(\mathbf{A})$ , $\boldsymbol{\uplambda}(\mathbf{B})$ and $\boldsymbol{\uplambda}(\mathbf{A} - \mathbf{B})$ .
(b) Verify Theorem 17.7.2 for all three index sets, and say which inequality is an equality and why it had to be.
(c) Verify both bounds of Corollary 17.7.3 (a), and explain why here every $\lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B})$ had to be non-negative.

Solution.

(a) The diagonal of $\mathbf{A}$ is real and $a_{21} = 1 - i = \overline{a_{12}}$ , so $\mathbf{A}^{*} = \mathbf{A}$ ; $\mathbf{B}$ is real diagonal. For $\mathbf{A}$ , $\operatorname{tr}\mathbf{A} = 3$ and $\det\mathbf{A} = 2 - (1+i)(1-i) = 2 - 2 = 0$ , so $\boldsymbol{\uplambda}(\mathbf{A}) = (3, 0)$ . Next, $\boldsymbol{\uplambda}(\mathbf{B}) = (1, -1)$ . Finally $\mathbf{A} - \mathbf{B} = \begin{pmatrix} 1 & 1 + i \\ 1 - i & 2 \end{pmatrix}$ has trace $3$ and determinant $2 - 2 = 0$ , so $\boldsymbol{\uplambda}(\mathbf{A} - \mathbf{B}) = (3, 0)$ .
(b) The differences at equal indices are $3 - 1 = 2$ and $0 - (-1) = 1$ . For $(1)$ : $2 \le 3$ . For $(2)$ : $1 \le 3$ . For $(1, 2)$ : $3 \le 3 + 0 = 3$ , an equality. It had to be one, since for the full index set both sides equal $\operatorname{tr}\mathbf{A} - \operatorname{tr}\mathbf{B} = \operatorname{tr}(\mathbf{A} - \mathbf{B})$ .
(c) The bounds are $\lambda_2(\mathbf{A} - \mathbf{B}) = 0 \le 2 \le 3$ and $0 \le 1 \le 3$ . The lower bound $\lambda_n(\mathbf{A} - \mathbf{B}) = 0$ is non-negative because $\mathbf{A} - \mathbf{B} \succeq 0$ : it is Hermitian with eigenvalues $3, 0 \ge 0$ (Theorem 13.1.4). So $\mathbf{A} \succeq \mathbf{B}$ , and Corollary 17.2.4 already forces $\lambda_i(\mathbf{A}) \ge \lambda_i(\mathbf{B})$ for each $i$ .

Exercise (B3: The lower bound)

Let $\mathbf{A}, \mathbf{B} \in M_n(F)$ be Hermitian and $1 \le i_1 < \dots < i_k \le n$ . Prove that $\sum_{j=1}^{k}\lambda_{i_j}(\mathbf{A}) - \sum_{j=1}^{k}\lambda_{i_j}(\mathbf{B}) \ \ge\ \sum_{j=n-k+1}^{n}\lambda_j(\mathbf{A} - \mathbf{B}) ,$ that is, the shifts over any $k$ indices add up to at least the $k$ smallest eigenvalues of $\mathbf{A} - \mathbf{B}$ . Check the result on Example (All seven index sets).

Solution. Apply Theorem 17.7.2 with the roles of $\mathbf{A}$ and $\mathbf{B}$ exchanged: $\sum_{j=1}^{k}\lambda_{i_j}(\mathbf{B}) - \sum_{j=1}^{k}\lambda_{i_j}(\mathbf{A}) \ \le\ \sum_{j=1}^{k}\lambda_j(\mathbf{B} - \mathbf{A}) .$ Since $\mathbf{B} - \mathbf{A} = -(\mathbf{A} - \mathbf{B})$ , Lemma 17.3.2 gives $\lambda_j(\mathbf{B} - \mathbf{A}) = -\lambda_{n+1-j}(\mathbf{A} - \mathbf{B})$ . As $j$ runs over $1, \dots, k$ , the index $n + 1 - j$ runs over $n, \dots, n - k + 1$ , so the right-hand side is $-\sum_{j=n-k+1}^{n}\lambda_j(\mathbf{A} - \mathbf{B})$ . Multiplying the inequality by $-1$ gives the claim.

In Example (All seven index sets), $\boldsymbol{\uplambda}(\mathbf{A} - \mathbf{B}) = (4, 1, -3)$ , whose bottom partial sums are $-3$ , $-2$ , $2$ for $k = 1, 2, 3$ . The left sides are $2, 1, -1$ for $k = 1$ , then $3, 1, 0$ for $k = 2$ , then $2$ for $k = 3$ . Each is at least the corresponding bottom sum.

C. Going deeper

Exercise (C1: A second proof of Lidskii’s inequality)

Let $\mathbf{A}, \mathbf{B} \in M_n(F)$ be Hermitian, put $\mathbf{C} = \mathbf{A} - \mathbf{B}$ , and fix an index set $1 \le i_1 < \dots < i_k \le n$ .

(a) Let $c \in \mathbb{R}$ . Show that replacing $\mathbf{A}$ by $\mathbf{A} - c\mathbf{I}$ , with $\mathbf{B}$ unchanged, lowers both sides of Theorem 17.7.2 by $kc$ . Deduce that it suffices to prove the inequality when $\lambda_k(\mathbf{C}) = 0$ .
(b) Assume $\lambda_k(\mathbf{C}) = 0$ . Write $\mathbf{C} = \mathbf{U}\mathbf{D}\mathbf{U}^{*}$ with $\mathbf{U}$ unitary and $\mathbf{D} = \operatorname{diag}(\lambda_1(\mathbf{C}), \dots, \lambda_n(\mathbf{C}))$ , and put $\mathbf{C}_+ = \mathbf{U}\mathbf{D}_+\mathbf{U}^{*}$ , where $\mathbf{D}_+$ replaces each negative diagonal entry of $\mathbf{D}$ by $0$ . Prove that $\mathbf{C}_+ \succeq \mathbf{C}$ , $\mathbf{C}_+ \succeq 0$ and $\operatorname{tr}\mathbf{C}_+ = \sum_{j\le k}\lambda_j(\mathbf{C})$ .
(c) Prove that $\lambda_i(\mathbf{A}) \le \lambda_i(\mathbf{B} + \mathbf{C}_+)$ and $\lambda_i(\mathbf{B} + \mathbf{C}_+) \ge \lambda_i(\mathbf{B})$ for every $i$ , and deduce Theorem 17.7.2.
(d) Which of the ingredients of this proof were available before this section? What does this proof not give that Theorem 17.7.1 does?

Hint: Corollary 17.2.4.

Solution.

(a) For every Hermitian $\mathbf{M}$ and real $c$ , $\lambda_i(\mathbf{M} - c\mathbf{I}) = \lambda_i(\mathbf{M}) - c$ for all $i$ . Indeed, if $\mathbf{M} = \mathbf{U}\mathbf{D}\mathbf{U}^{*}$ with $\mathbf{U}$ unitary and $\mathbf{D}$ real diagonal (Corollary 12.4.3, or Corollary 12.5.2 over $\mathbb{R}$ ), then $\mathbf{M} - c\mathbf{I} = \mathbf{U}(\mathbf{D} - c\mathbf{I})\mathbf{U}^{*}$ , and subtracting $c$ from every diagonal entry keeps the order. Replacing $\mathbf{A}$ by $\mathbf{A} - c\mathbf{I}$ lowers each $\lambda_{i_j}(\mathbf{A})$ by $c$ , so the left side drops by $kc$ . It also replaces $\mathbf{C}$ by $\mathbf{C} - c\mathbf{I}$ , so each $\lambda_j(\mathbf{C})$ drops by $c$ and the right side drops by $kc$ . So the inequality for $(\mathbf{A} - c\mathbf{I}, \mathbf{B})$ is equivalent to the one for $(\mathbf{A}, \mathbf{B})$ . With $c = \lambda_k(\mathbf{C})$ , the new difference $\mathbf{C} - c\mathbf{I}$ has $\lambda_k = 0$ .
(b) $\mathbf{C}_+ - \mathbf{C} = \mathbf{U}(\mathbf{D}_+ - \mathbf{D})\mathbf{U}^{*}$ , and $\mathbf{D}_+ - \mathbf{D}$ is diagonal with entries $\max(-\lambda_i(\mathbf{C}), 0) \ge 0$ . So $\mathbf{C}_+ - \mathbf{C}$ is Hermitian with non-negative eigenvalues, hence $\mathbf{C}_+ - \mathbf{C} \succeq 0$ by Theorem 13.1.4, that is, $\mathbf{C}_+ \succeq \mathbf{C}$ . In the same way $\mathbf{C}_+ \succeq 0$ , since the entries of $\mathbf{D}_+$ are $\ge 0$ . For the trace, $\operatorname{tr}\mathbf{C}_+ = \operatorname{tr}\mathbf{D}_+ = \sum_i\max(\lambda_i(\mathbf{C}), 0)$ by Theorem 0.9.6 (3). For $i \le k$ , $\lambda_i(\mathbf{C}) \ge \lambda_k(\mathbf{C}) = 0$ , so the term is $\lambda_i(\mathbf{C})$ . For $i > k$ , $\lambda_i(\mathbf{C}) \le 0$ , so the term is $0$ . Hence $\operatorname{tr}\mathbf{C}_+ = \sum_{j\le k}\lambda_j(\mathbf{C})$ .
(c) $\mathbf{A} = \mathbf{B} + \mathbf{C} \preceq \mathbf{B} + \mathbf{C}_+$ by (b), and $\mathbf{B} + \mathbf{C}_+ \succeq \mathbf{B}$ because $\mathbf{C}_+ \succeq 0$ . Corollary 17.2.4 turns both into the stated eigenvalue inequalities. Therefore $\begin{aligned} \sum_{j=1}^{k}\bigl(\lambda_{i_j}(\mathbf{A}) - \lambda_{i_j}(\mathbf{B})\bigr) &\le \sum_{j=1}^{k}\bigl(\lambda_{i_j}(\mathbf{B} + \mathbf{C}_+) - \lambda_{i_j}(\mathbf{B})\bigr) \\ &\le \sum_{i=1}^{n}\bigl(\lambda_i(\mathbf{B} + \mathbf{C}_+) - \lambda_i(\mathbf{B})\bigr) , \end{aligned}$ the second step adding the $n - k$ omitted terms, each $\ge 0$ . The last sum is $\operatorname{tr}(\mathbf{B} + \mathbf{C}_+) - \operatorname{tr}\mathbf{B} = \operatorname{tr}\mathbf{C}_+$ , by Corollary 12.1.4 and Theorem 0.9.6 (1), and $\operatorname{tr}\mathbf{C}_+ = \sum_{j\le k}\lambda_j(\mathbf{C})$ by (b).
(d) Everything used here was available after §02: the spectral theorem, the characterization of positive semidefiniteness by eigenvalues, the trace, and Corollary 17.2.4. The proof never looks at a flag. What it does not give is the variational description itself. Theorem 17.7.1 expresses $\sum_j\lambda_{i_j}(\mathbf{A})$ as an optimization involving $\mathbf{A}$ alone, and like Courant–Fischer and Ky Fan before it, such a description can be reused for other comparisons. This proof is a clever route to one consequence of that description.

Exercise (C2: The total absolute shift)

Let $\mathbf{A}, \mathbf{B} \in M_n(F)$ be Hermitian.

(a) Prove that $\sum_{i=1}^{n}\bigl\lvert\lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B})\bigr\rvert \ \le\ \sum_{i=1}^{n}\bigl\lvert\lambda_i(\mathbf{A} - \mathbf{B})\bigr\rvert .$
(b) Show that equality holds when $\mathbf{A} \succeq \mathbf{B}$ . Compute both sides for Example (All seven index sets), and compare with the bound $n\left\| \mathbf{A} - \mathbf{B} \right\|_2$ obtained by adding the bounds of Corollary 17.3.6.

Hint for (a): use the set of indices at which $\lambda_i(\mathbf{A}) > \lambda_i(\mathbf{B})$ .

Solution.

(a) Write $d_i = \lambda_i(\mathbf{A}) - \lambda_i(\mathbf{B})$ and $\mu_j = \lambda_j(\mathbf{A} - \mathbf{B})$ . Let $S = \{i : d_i > 0\}$ and $k = \lvert S\rvert$ . Then $\sum_{i=1}^{n}\lvert d_i\rvert = \sum_{i \in S}d_i - \sum_{i \notin S}d_i = 2\sum_{i\in S}d_i - \sum_{i=1}^{n}d_i .$ The total is $\sum_i d_i = \operatorname{tr}\mathbf{A} - \operatorname{tr}\mathbf{B} = \operatorname{tr}(\mathbf{A} - \mathbf{B}) = \sum_j\mu_j$ , by Corollary 12.1.4 and Theorem 0.9.6 (1). If $k \ge 1$ , Theorem 17.7.2 with the elements of $S$ as index set gives $\sum_{i\in S}d_i \le \sum_{j\le k}\mu_j$ ; if $k = 0$ both sides of this inequality are the empty sum $0$ . In either case $\sum_{i=1}^{n}\lvert d_i\rvert \ \le\ 2\sum_{j\le k}\mu_j - \sum_{j=1}^{n}\mu_j = \sum_{j\le k}\mu_j - \sum_{j>k}\mu_j \ \le\ \sum_{j=1}^{n}\lvert\mu_j\rvert ,$ the last step because $\pm\mu_j \le \lvert\mu_j\rvert$ for each $j$ .
(b) If $\mathbf{A} \succeq \mathbf{B}$ then every $d_i \ge 0$ by Corollary 17.2.4, and every $\mu_j \ge 0$ by Theorem 13.1.4. Both sides then equal their plain sums, and those are equal, both being $\operatorname{tr}(\mathbf{A} - \mathbf{B})$ .

In Example (All seven index sets), the $d_i$ are $2, 1, -1$ , so the left side is $4$ ; the $\mu_j$ are $4, 1, -3$ , so the right side is $8$ . By Lemma 17.3.5, $\left\| \mathbf{A} - \mathbf{B} \right\|_2 = \max(4, 3) = 4$ , and adding the three bounds of Corollary 17.3.6 gives $3 \cdot 4 = 12$ . The bound of (a) is never worse than this one: each $\lvert\mu_j\rvert \le \left\| \mathbf{A} - \mathbf{B} \right\|_2$ , so the right side of (a) is at most $n\left\| \mathbf{A} - \mathbf{B} \right\|_2$ , and it is often much smaller.