17.6 Subspaces and Sums of Eigenvalues

Section 4 deleted a row and the matching column, which is a coordinate-dependent operation, and got a coordinate-free conclusion: the spectra interlace. That is a hint. This section replaces “delete some coordinates” by “restrict to a subspace”, which is the same operation with the accident of a basis removed, and the interlacing survives in a stronger form. Then it asks a question Courant–Fischer cannot answer one eigenvalue at a time: not “what is $\lambda_2$ ?” but “what is $\lambda_1 + \lambda_2$ ?” That sum turns out to be a maximum over a set of subspaces, and the answer discharges a promise Chapter 13 made about singular values.

Throughout this section $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})$ .

17.6.1. Restricting a matrix to a subspace

A principal submatrix of $\mathbf{A}$ records what the quadratic form $\mathbf{x} \mapsto \langle \mathbf{A}\mathbf{x}, \mathbf{x} \rangle$ does to vectors supported on a few coordinates. Nothing in that description needs the coordinates to be the standard ones: any subspace $W$ and any orthonormal basis of it will do, and the matrix that results plays the same role.

Definition 17.6.1 (Compression to a subspace)

Let $\mathbf{A} \in M_n(F)$ , let $1 \le k \le n$ , and let $\mathbf{q}_1, \dots, \mathbf{q}_k$ be an orthonormal list in $F^{n}$ , so that the matrix $\mathbf{Q} \in M_{n \times k}(F)$ with these columns satisfies $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k$ . The compression of $\mathbf{A}$ to $W = \operatorname{span}(\mathbf{q}_1, \dots, \mathbf{q}_k)$ with respect to this basis is the $k \times k$ matrix $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}, \qquad (\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})_{ij} = \langle \mathbf{A}\mathbf{q}_j, \mathbf{q}_i \rangle .$

The entry formula is just $(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})_{ij} = \mathbf{q}_i^{*}\mathbf{A}\mathbf{q}_j$ , and $\mathbf{q}_i^{*}\mathbf{y} = \langle \mathbf{y}, \mathbf{q}_i \rangle$ for the standard inner product. If $\mathbf{A}$ is Hermitian so is $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ , since $(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})^{*} = \mathbf{Q}^{*}\mathbf{A}^{*}\mathbf{Q} = \mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ .

The eigenvalues do not depend on the basis chosen. Let $(\mathbf{q}'_1, \dots, \mathbf{q}'_k)$ be another orthonormal basis of the same $W$ , with matrix $\mathbf{Q}'$ . Each $\mathbf{q}'_j$ lies in $W = \operatorname{col}(\mathbf{Q})$ , so $\mathbf{Q}' = \mathbf{Q}\mathbf{U}$ for some $\mathbf{U} \in M_k(F)$ , and then $\mathbf{I}_k = (\mathbf{Q}')^{*}\mathbf{Q}' = \mathbf{U}^{*}\mathbf{Q}^{*}\mathbf{Q}\mathbf{U} = \mathbf{U}^{*}\mathbf{U}$ , so $\mathbf{U}$ is unitary. Hence $(\mathbf{Q}')^{*}\mathbf{A}\mathbf{Q}' = \mathbf{U}^{*}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})\mathbf{U} ,$ a unitary similarity, which leaves the eigenvalues alone. So it is legitimate to speak of the eigenvalues of the compression of $\mathbf{A}$ to $W$ , and we do.

Three cases to keep in mind.

Coordinate subspaces. If $\mathbf{q}_j = \mathbf{e}_{i_j}$ for indices $i_1 < \dots < i_k$ , then $(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})_{lj} = a_{i_l i_j}$ : the compression is the principal submatrix $\mathbf{A}_{I,I}$ of Definition 7.7.1 on the index set $I = \{i_1, \dots, i_k\}$ . Compression generalizes “delete rows and the matching columns”.
$k = n$ . Then $\mathbf{Q}$ is a unitary matrix and $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ is unitarily similar to $\mathbf{A}$ : nothing is lost and nothing is learned.
$k = 1$ . Then $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ is the $1 \times 1$ matrix $\langle \mathbf{A}\mathbf{q}_1, \mathbf{q}_1 \rangle = R_{\mathbf{A}}(\mathbf{q}_1)$ , the Rayleigh quotient of Definition 17.1.1 at a unit vector. Everything below is a statement about $k$ Rayleigh quotients at once.

Drop the orthonormality and the notion collapses. With $\mathbf{A} = \operatorname{diag}(1, 0)$ and the single column $\mathbf{Q} = (2, 0)^{\top}$ , which has $\mathbf{Q}^{*}\mathbf{Q} = (4) \ne \mathbf{I}_1$ , the “compression” is the $1 \times 1$ matrix $(4)$ , whose eigenvalue $4$ is larger than every eigenvalue of $\mathbf{A}$ . The clause that fails is $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k$ , and with it every conclusion of this section.

17.6.2. Interlacing without coordinates

Theorem 17.6.1 (Poincaré Separation Theorem)

Let $\mathbf{A} \in M_n(F)$ be Hermitian, let $1 \le k \le n$ , and let $\mathbf{B} = \mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ be the compression of $\mathbf{A}$ to a $k$ -dimensional subspace $W \subseteq F^{n}$ , as in Definition 17.6.1. Then $\lambda_i(\mathbf{A}) \ \ge\ \lambda_i(\mathbf{B}) \ \ge\ \lambda_{i + n - k}(\mathbf{A}) \qquad (1 \le i \le k) .$

Idea. Both inequalities come from the same observation, used twice. The map $\mathbf{y} \mapsto \mathbf{Q}\mathbf{y}$ carries $F^{k}$ isometrically onto $W$ , and it carries the Rayleigh quotient of $\mathbf{B}$ to the Rayleigh quotient of $\mathbf{A}$ . So each of the two Courant–Fischer descriptions of $\lambda_i(\mathbf{B})$ — a maximum of minima, and a minimum of maxima — is the corresponding description of $\lambda_i(\mathbf{A})$ with the competing subspaces restricted to those lying inside $W$ . A maximum over fewer competitors is smaller; a minimum over fewer competitors is larger. That is the whole proof; the only care needed is in matching the dimensions, and it is there that $n - k$ appears.

Proof. Step 1: transport. Throughout, $R_{\mathbf{A}}$ and $R_{\mathbf{B}}$ are the Rayleigh quotients of Definition 17.1.1. For $\mathbf{0} \ne \mathbf{y} \in F^{k}$ we have $\mathbf{Q}\mathbf{y} \ne \mathbf{0}$ , since $\left\| \mathbf{Q}\mathbf{y} \right\|^{2} = \mathbf{y}^{*}\mathbf{Q}^{*}\mathbf{Q}\mathbf{y} = \left\| \mathbf{y} \right\|^{2}$ and $\mathbf{y} \ne \mathbf{0}$ . The same computation with $\mathbf{A}$ inserted gives $\langle \mathbf{B}\mathbf{y}, \mathbf{y} \rangle = \mathbf{y}^{*}\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}\mathbf{y} = \langle \mathbf{A}(\mathbf{Q}\mathbf{y}), \mathbf{Q}\mathbf{y} \rangle ,$ so $R_{\mathbf{B}}(\mathbf{y}) = R_{\mathbf{A}}(\mathbf{Q}\mathbf{y})$ . Moreover $\mathbf{y} \mapsto \mathbf{Q}\mathbf{y}$ is injective and linear, so it maps the subspaces of $F^{k}$ of dimension $j$ bijectively onto the subspaces of $W$ of dimension $j$ , for every $j$ . Consequently, for each $j$ , $\bigl\{\,R_{\mathbf{B}}(\mathbf{y}) : \mathbf{0} \ne \mathbf{y} \in S \,\bigr\} = \bigl\{\,R_{\mathbf{A}}(\mathbf{x}) : \mathbf{0} \ne \mathbf{x} \in \mathbf{Q} S \,\bigr\}$ for every subspace $S \subseteq F^{k}$ .

Step 2: the upper bound. By the max–min form of Theorem 17.2.3 applied to $\mathbf{B} \in M_k(F)$ , $\begin{aligned} \lambda_i(\mathbf{B}) &= \max_{\substack{S \subseteq F^{k} \\ \dim S = i}} \ \min_{\mathbf{0} \ne \mathbf{y} \in S} R_{\mathbf{B}}(\mathbf{y}) \\ &= \max_{\substack{U \subseteq W \\ \dim U = i}} \ \min_{\mathbf{0} \ne \mathbf{x} \in U} R_{\mathbf{A}}(\mathbf{x}) , \end{aligned}$ the second equality by Step 1. The subspaces $U \subseteq W$ of dimension $i$ form a subfamily of the subspaces $U \subseteq F^{n}$ of dimension $i$ , and enlarging the family over which a maximum is taken cannot decrease it. So by the max–min form of Theorem 17.2.3 applied to $\mathbf{A}$ , the right-hand side is at most $\lambda_i(\mathbf{A})$ .

Step 3: the lower bound. By the min–max form of Theorem 17.2.3 applied to $\mathbf{B} \in M_k(F)$ , with the complementary dimension $k - i + 1$ , $\begin{aligned} \lambda_i(\mathbf{B}) &= \min_{\substack{S \subseteq F^{k} \\ \dim S = k-i+1}} \ \max_{\mathbf{0} \ne \mathbf{y} \in S} R_{\mathbf{B}}(\mathbf{y}) \\ &= \min_{\substack{U \subseteq W \\ \dim U = k-i+1}} \ \max_{\mathbf{0} \ne \mathbf{x} \in U} R_{\mathbf{A}}(\mathbf{x}) , \end{aligned}$ again by Step 1. Put $l = i + n - k$ , so that $1 \le l \le n$ and $n - l + 1 = k - i + 1$ . The min–max form of Theorem 17.2.3 applied to $\mathbf{A}$ therefore reads $\lambda_{l}(\mathbf{A}) = \min_{\substack{U \subseteq F^{n} \\ \dim U = k-i+1}} \ \max_{\mathbf{0} \ne \mathbf{x} \in U} R_{\mathbf{A}}(\mathbf{x}) ,$ a minimum over a larger family than the one above, hence no larger. So $\lambda_i(\mathbf{B}) \ge \lambda_{i+n-k}(\mathbf{A})$ . This proves the theorem.

Remark. Taking $W$ to be the coordinate hyperplane $\operatorname{span}(\mathbf{e}_j : j \ne l)$ makes $\mathbf{B}$ the principal submatrix obtained by deleting row $l$ and column $l$ , and $k = n-1$ turns the conclusion into $\lambda_i(\mathbf{A}) \ge \lambda_i(\mathbf{B}) \ge \lambda_{i+1}(\mathbf{A})$ . That is Theorem 17.4.2. What the present theorem adds is that the coordinates played no part, and that deleting $n - k$ dimensions at once costs exactly $n - k$ indices.

Example (A compression of a diagonal matrix)

Let $\mathbf{A} = \operatorname{diag}(5, 3, -2)$ and let $\mathbf{q}_1 = \tfrac13(2, 2, 1), \qquad \mathbf{q}_2 = \tfrac13(-2, 1, 2) .$ Check that $(\mathbf{q}_1, \mathbf{q}_2)$ is orthonormal, compute the compression $\mathbf{B}$ of $\mathbf{A}$ to $W = \operatorname{span}(\mathbf{q}_1, \mathbf{q}_2)$ and its eigenvalues, and verify Theorem 17.6.1.

Solution. Orthonormality. $\left\| \mathbf{q}_1 \right\|^{2} = (4 + 4 + 1)/9 = 1$ and $\left\| \mathbf{q}_2 \right\|^{2} = (4 + 1 + 4)/9 = 1$ , while $9\langle \mathbf{q}_1, \mathbf{q}_2 \rangle = -4 + 2 + 2 = 0$ .

The compression. Multiplying by the diagonal matrix, $3\mathbf{A}\mathbf{q}_1 = (10, 6, -2)$ and $3\mathbf{A}\mathbf{q}_2 = (-10, 3, -4)$ . Hence $\begin{aligned} b_{11} &= \tfrac19(2, 2, 1)\cdot(10, 6, -2) = \tfrac{20 + 12 - 2}{9} = \tfrac{10}{3}, \\ b_{21} &= \tfrac19(-2, 1, 2)\cdot(10, 6, -2) = \tfrac{-20 + 6 - 4}{9} = -2, \\ b_{22} &= \tfrac19(-2, 1, 2)\cdot(-10, 3, -4) = \tfrac{20 + 3 - 8}{9} = \tfrac53 , \end{aligned}$ and $b_{12} = b_{21}$ because $\mathbf{B}$ is symmetric. So $\mathbf{B} = \begin{pmatrix} 10/3 & -2 \\ -2 & 5/3 \end{pmatrix} .$

Its eigenvalues. $\operatorname{tr}\mathbf{B} = 5$ and $\det\mathbf{B} = \tfrac{50}{9} - 4 = \tfrac{14}{9}$ , so the characteristic polynomial is $x^{2} - 5x + \tfrac{14}{9}$ , that is $9x^{2} - 45x + 14$ . Its discriminant is $2025 - 504 = 1521 = 39^{2}$ , so the roots are $(45 \pm 39)/18$ , namely $\lambda_1(\mathbf{B}) = \tfrac{14}{3}$ and $\lambda_2(\mathbf{B}) = \tfrac13$ .

The separation. Here $n = 3$ and $k = 2$ , so the theorem says $\lambda_i(\mathbf{A}) \ge \lambda_i(\mathbf{B}) \ge \lambda_{i+1}(\mathbf{A})$ for $i = 1, 2$ : $5 \ \ge\ \tfrac{14}{3} \ \ge\ 3 \ \ge\ \tfrac13 \ \ge\ -2 ,$ and every inequality is strict. Note also $\operatorname{tr}\mathbf{B} = 5 \le 5 + 3 = \lambda_1(\mathbf{A}) + \lambda_2(\mathbf{A})$ ; the next theorem says that this is no accident and that $8$ is the best possible ceiling.

Quick check. Let $\mathbf{A}$ be Hermitian $n \times n$ and let $\mathbf{B}$ be its compression to a $k$ -dimensional subspace. Which single inequality of Theorem 17.6.1 says that a compression of a positive semidefinite matrix is positive semidefinite?

Solution. The case $i = k$ of the lower bound: $\lambda_k(\mathbf{B}) \ge \lambda_{k+n-k}(\mathbf{A}) = \lambda_n(\mathbf{A})$ . If $\mathbf{A} \succeq \mathbf{O}$ then $\lambda_n(\mathbf{A}) \ge 0$ by Theorem 13.1.4 (b), so every eigenvalue of $\mathbf{B}$ is $\ge 0$ , and $\mathbf{B}$ is Hermitian, so $\mathbf{B} \succeq \mathbf{O}$ by the same theorem. (A direct proof is also one line: $\langle \mathbf{B}\mathbf{y}, \mathbf{y} \rangle = \langle \mathbf{A}\mathbf{Q}\mathbf{y}, \mathbf{Q}\mathbf{y} \rangle \ge 0$ . The point of the check is to locate the statement inside the interlacing.)

17.6.3. The top eigenvalues, summed

Chapter 13 described $\lambda_1$ as a maximum over the unit sphere (Lemma 13.5.2), and Section 1 pointed out that $\lambda_2$ is not the “second largest value” of anything. But $\lambda_1 + \lambda_2$ is a maximum again — over pairs of orthonormal vectors rather than single ones. The pattern continues for every $k$ , and it is the sum, never the individual eigenvalue, that behaves.

Theorem 17.6.2 (Ky Fan Maximum Principle)

Let $\mathbf{A} \in M_n(F)$ be Hermitian and let $1 \le k \le n$ . Then $\begin{aligned} \sum_{i=1}^{k}\lambda_i(\mathbf{A}) &= \max\Bigl\{ \sum_{i=1}^{k}\langle \mathbf{A}\mathbf{q}_i, \mathbf{q}_i \rangle \ :\ \mathbf{q}_1, \dots, \mathbf{q}_k \text{ orthonormal} \Bigr\} \\ &= \max\bigl\{ \operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}) \ :\ \mathbf{Q} \in M_{n \times k}(F),\ \mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k \bigr\} , \end{aligned}$ and the maximum is attained by $\mathbf{Q} = (\mathbf{u}_1 \ \dots \ \mathbf{u}_k)$ for any orthonormal basis $(\mathbf{u}_1, \dots, \mathbf{u}_n)$ of $F^{n}$ with $\mathbf{A}\mathbf{u}_i = \lambda_i(\mathbf{A})\mathbf{u}_i$ .

Idea. The two right-hand sides are the same number written twice, since the diagonal entries of $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ are exactly the $k$ numbers $\langle \mathbf{A}\mathbf{q}_i, \mathbf{q}_i \rangle$ . That reformulation is the whole idea: the quantity to be maximized is the trace of a compression, and Theorem 17.6.1 already bounds every eigenvalue of a compression by the matching eigenvalue of $\mathbf{A}$ . Add $k$ such bounds and read the left-hand side as a trace. The maximizing $\mathbf{Q}$ is the one that makes the compression diagonal with the top eigenvalues on it, and there is no cleverness in guessing it.

Proof. Write $\mathbf{B} = \mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ for a matrix $\mathbf{Q}$ with orthonormal columns $\mathbf{q}_1, \dots, \mathbf{q}_k$ . Its diagonal entries are $b_{ii} = \langle \mathbf{A}\mathbf{q}_i, \mathbf{q}_i \rangle$ by Definition 17.6.1, so $\operatorname{tr}\mathbf{B} = \sum_{i=1}^{k}\langle \mathbf{A}\mathbf{q}_i, \mathbf{q}_i \rangle ,$ and the two sets over which the maxima are taken consist of the same numbers. It therefore suffices to prove the statement for $\operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})$ .

The bound. Let $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k$ and put $\mathbf{B} = \mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ , a Hermitian matrix in $M_k(F)$ . By Corollary 12.1.4, $\operatorname{tr}\mathbf{B} = \sum_{i=1}^{k}\lambda_i(\mathbf{B})$ . By Theorem 17.6.1, $\lambda_i(\mathbf{B}) \le \lambda_i(\mathbf{A})$ for every $1 \le i \le k$ . Summing these $k$ inequalities, $\operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}) = \sum_{i=1}^{k}\lambda_i(\mathbf{B}) \ \le\ \sum_{i=1}^{k}\lambda_i(\mathbf{A}) .$

Attainment. Since $\mathbf{A}$ is Hermitian, Corollary 12.4.3 (for $F = \mathbb{C}$ ) or Corollary 12.5.2 (for $F = \mathbb{R}$ ) provides an orthonormal basis $(\mathbf{u}_1, \dots, \mathbf{u}_n)$ of $F^{n}$ of eigenvectors, in any prescribed order; take the order with $\mathbf{A}\mathbf{u}_i = \lambda_i(\mathbf{A})\mathbf{u}_i$ . Let $\mathbf{Q}$ have columns $\mathbf{u}_1, \dots, \mathbf{u}_k$ ; these are orthonormal, so $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k$ . Then $\langle \mathbf{A}\mathbf{u}_i, \mathbf{u}_i \rangle = \lambda_i(\mathbf{A})\langle \mathbf{u}_i, \mathbf{u}_i \rangle = \lambda_i(\mathbf{A}) ,$ so $\operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}) = \sum_{i \le k}\lambda_i(\mathbf{A})$ .

The bound is therefore attained, so the supremum is a maximum and equals $\sum_{i\le k}\lambda_i(\mathbf{A})$ . This proves the theorem.

For $k = 1$ this is Lemma 13.5.2 of Chapter 13: $\lambda_1$ is the largest value of $\langle \mathbf{A}\mathbf{x}, \mathbf{x} \rangle$ on the unit sphere. For $k = n$ it degenerates in an instructive way: every $\mathbf{Q}$ is unitary, every $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ is unitarily similar to $\mathbf{A}$ , and the “maximum” is attained everywhere, at the common value $\operatorname{tr}\mathbf{A}$ . The content is in between.

Example (Which pairs of directions capture the most)

Let $\mathbf{A} = \begin{pmatrix} 2 & 1 & 0 \\ 1 & 2 & 0 \\ 0 & 0 & -1 \end{pmatrix} .$ Find $\max\{\operatorname{tr}(\mathbf{Q}^{\top}\mathbf{A}\mathbf{Q}) : \mathbf{Q}^{\top}\mathbf{Q} = \mathbf{I}_2\}$ and a maximizer, and compare the values at $\mathbf{Q} = (\mathbf{e}_1\ \mathbf{e}_2)$ and $\mathbf{Q} = (\mathbf{e}_1\ \mathbf{e}_3)$ .

Solution. The eigenvalues: $\mathbf{e}_3$ is an eigenvector for $-1$ , and the top-left block $\begin{psmallmatrix} 2 & 1 \\ 1 & 2\end{psmallmatrix}$ has eigenvectors $(1, 1)$ and $(1, -1)$ for $3$ and $1$ . So $\lambda_1 = 3$ , $\lambda_2 = 1$ , $\lambda_3 = -1$ , with orthonormal eigenvectors $\mathbf{u}_1 = \tfrac1{\sqrt2}(1,1,0)$ , $\mathbf{u}_2 = \tfrac1{\sqrt2}(1,-1,0)$ , $\mathbf{u}_3 = \mathbf{e}_3$ . By Theorem 17.6.2 the maximum is $3 + 1 = 4$ , attained at $\mathbf{Q} = (\mathbf{u}_1\ \mathbf{u}_2)$ .

At $\mathbf{Q} = (\mathbf{e}_1\ \mathbf{e}_2)$ the trace is $a_{11} + a_{22} = 4$ : this is also a maximizer. That is no accident — $\operatorname{span}(\mathbf{e}_1, \mathbf{e}_2) = \operatorname{span}(\mathbf{u}_1, \mathbf{u}_2)$ , and the trace of a compression, like its eigenvalues, depends only on the subspace. At $\mathbf{Q} = (\mathbf{e}_1\ \mathbf{e}_3)$ the trace is $2 + (-1) = 1$ , well below the ceiling, as Theorem 17.6.2 requires.

The simplest competitors are the standard basis vectors, and they give a statement about the diagonal of $\mathbf{A}$ for free.

Corollary 17.6.3 (Partial Sums of the Diagonal)

Let $\mathbf{A} \in M_n(F)$ be Hermitian with diagonal entries $a_{11}, \dots, a_{nn}$ , and let $1 \le i_1 < \dots < i_k \le n$ . Then $\sum_{j=1}^{k} a_{i_j i_j} \ \le\ \sum_{i=1}^{k}\lambda_i(\mathbf{A}) ,$ with equality for $k = n$ .

Proof. The list $(\mathbf{e}_{i_1}, \dots, \mathbf{e}_{i_k})$ is orthonormal, and $\langle \mathbf{A}\mathbf{e}_{i}, \mathbf{e}_{i} \rangle = a_{ii}$ . Apply Theorem 17.6.2. For $k = n$ both sides equal $\operatorname{tr}\mathbf{A}$ , by Corollary 12.1.4.

Quick check. Can a Hermitian $3 \times 3$ matrix with diagonal entries $5, 1, 0$ have eigenvalues $4, 2, 0$ ? Can it have eigenvalues $6, 0, 0$ ?

Solution. Not the first: the case $k = 1$ of Corollary 17.6.3 says every diagonal entry is at most $\lambda_1$ , and $5 > 4$ . The second passes every test — $5 \le 6$ , $5 + 1 \le 6$ , $6 = 6$ — and is realized: with $\mathbf{v} = (\sqrt5, 1, 0)$ , the matrix $\mathbf{v}\mathbf{v}^{\top}$ has diagonal $5, 1, 0$ ; it sends $\mathbf{v}$ to $\left\| \mathbf{v} \right\|^{2}\mathbf{v} = 6\mathbf{v}$ and kills the plane orthogonal to $\mathbf{v}$ , so its eigenvalues are $6, 0, 0$ . Whether passing every test is always enough is the converse question, which Section 8 takes up.

17.6.4. The promise from Chapter 13

Chapter 13 §11 proved a bound on how much of a matrix an orthonormal list can capture (Lemma 13.11.2), and said of it: it “is the extreme case of a family of statements about sums of the largest eigenvalues of a Hermitian matrix; Chapter 17 develops the family through the Courant–Fischer min–max theorem”. Theorem 17.6.2 is that family. Here is the lemma, recovered from it in four lines.

Corollary 17.6.4 (The Capture Bound as a Case of Ky Fan)

Let $\mathbf{A} \in M_{m \times n}(F)$ with singular values $\sigma_1 \ge \dots \ge \sigma_p$ , $p = \min(m,n)$ , extended by $\sigma_i = 0$ for $p < i \le m$ , and let $\mathbf{q}_1, \dots, \mathbf{q}_s$ be an orthonormal list in $F^{m}$ . Then $\sum_{j=1}^{s}\left\| \mathbf{A}^{*}\mathbf{q}_j \right\|^{2} \ \le\ \sum_{i=1}^{s}\sigma_i^{2} .$

Proof. If $s = 0$ both sides are empty sums, equal to $0$ ; so assume $s \ge 1$ . Put $\mathbf{M} = \mathbf{A}\mathbf{A}^{*} \in M_m(F)$ , which is Hermitian. For each $j$ , $\left\| \mathbf{A}^{*}\mathbf{q}_j \right\|^{2} = (\mathbf{A}^{*}\mathbf{q}_j)^{*}(\mathbf{A}^{*}\mathbf{q}_j) = \mathbf{q}_j^{*}\mathbf{M}\mathbf{q}_j = \langle \mathbf{M}\mathbf{q}_j, \mathbf{q}_j \rangle .$ Fix a singular value decomposition $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ (Theorem 13.9.1). Since $\mathbf{V}^{*}\mathbf{V} = \mathbf{I}_n$ , $\mathbf{M} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}\mathbf{V}\boldsymbol{\Sigma}^{*}\mathbf{U}^{*} = \mathbf{U}(\boldsymbol{\Sigma}\boldsymbol{\Sigma}^{*})\mathbf{U}^{*} ,$ and $\boldsymbol{\Sigma}\boldsymbol{\Sigma}^{*}$ is the $m \times m$ diagonal matrix with diagonal $\sigma_1^{2}, \dots, \sigma_p^{2}$ followed by $m - p$ zeros — that is, $\sigma_1^{2} \ge \dots \ge \sigma_m^{2}$ in the extended notation. So this display is a unitary diagonalization of $\mathbf{M}$ , and Corollary 12.4.3 identifies its diagonal as the eigenvalue list: $\lambda_i(\mathbf{M}) = \sigma_i^{2}$ for $1 \le i \le m$ . Now Theorem 17.6.2 applied to $\mathbf{M}$ with $k = s$ gives $\sum_{j=1}^{s}\langle \mathbf{M}\mathbf{q}_j, \mathbf{q}_j \rangle \ \le\ \sum_{i=1}^{s}\lambda_i(\mathbf{M}) = \sum_{i=1}^{s}\sigma_i^{2} ,$ which is the claim.

This is Lemma 13.11.2 exactly, hypotheses and conclusion, so the debt is paid. Two things are worth saying about the shape of the payment.

First, Chapter 13 had to prove the inequality by hand, weight by weight, because it had no min–max theorem; the argument there is a careful estimate on a weighted sum of a decreasing sequence. Here the same estimate is invisible: it has been absorbed into Theorem 17.2.3, whose proof is a dimension count, and passed on through Theorem 17.6.1.

Second, the words “extreme case”. Strictly, the lemma is a special case of the family rather than an extreme one: it is the instance in which the Hermitian matrix is a product $\mathbf{A}\mathbf{A}^{*}$ , so that every eigenvalue is a squared singular value. Its crudest instance, $s = 1$ , says $\left\| \mathbf{A}^{*}\mathbf{q} \right\|^{2} \le \sigma_1^{2}$ for a unit $\mathbf{q}$ , that is, $\left\| \mathbf{A}^{*} \right\|_2 = \sigma_1$ . The same one line of Ky Fan, run with the other product — Theorem 17.6.2 with $k = 1$ applied to the Hermitian matrix $\mathbf{A}^{*}\mathbf{A} \in M_n(F)$ — whose largest eigenvalue is $\sigma_1^{2}$ by Definition 13.9.1 — gives $\max_{\left\| \mathbf{x} \right\| = 1}\left\| \mathbf{A}\mathbf{x} \right\|^{2} = \max_{\left\| \mathbf{x} \right\| = 1}\langle \mathbf{A}^{*}\mathbf{A}\mathbf{x}, \mathbf{x} \rangle = \lambda_1(\mathbf{A}^{*}\mathbf{A}) = \sigma_1^{2} .$ So the largest singular value is the largest stretching factor, which is Theorem 16.3.3 (c), $\left\| \mathbf{A} \right\|_2 = \sigma_1(\mathbf{A})$ . Chapter 16 proved that from the singular value decomposition; here it is one line of Ky Fan.

17.6.5. Sums are convex; individual eigenvalues are not

Corollary 17.6.5 (Subadditivity of the Top Partial Sums)

Let $\mathbf{A}, \mathbf{B} \in M_n(F)$ be Hermitian and let $1 \le k \le n$ . Then $\sum_{i=1}^{k}\lambda_i(\mathbf{A} + \mathbf{B}) \ \le\ \sum_{i=1}^{k}\lambda_i(\mathbf{A}) + \sum_{i=1}^{k}\lambda_i(\mathbf{B}) .$

Proof. By Theorem 17.6.2 applied to the Hermitian matrix $\mathbf{A} + \mathbf{B}$ , there is a $\mathbf{Q} \in M_{n\times k}(F)$ with $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k$ attaining the maximum, so that $\sum_{i=1}^{k}\lambda_i(\mathbf{A}+\mathbf{B}) = \operatorname{tr}\bigl(\mathbf{Q}^{*}(\mathbf{A}+\mathbf{B})\mathbf{Q}\bigr) .$ By Theorem 0.9.6 (1) the right-hand side is $\operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}) + \operatorname{tr}(\mathbf{Q}^{*}\mathbf{B}\mathbf{Q})$ . This one $\mathbf{Q}$ is a competitor in each of the two maximization problems of Theorem 17.6.2, for $\mathbf{A}$ and for $\mathbf{B}$ , so each summand is at most the corresponding maximum. Adding the two bounds proves the corollary.

Write $s_k(\mathbf{A}) = \sum_{i \le k}\lambda_i(\mathbf{A})$ for the function just bounded. Two properties have now been proved: it is subadditive, $s_k(\mathbf{A} + \mathbf{B}) \le s_k(\mathbf{A}) + s_k(\mathbf{B})$ , and it is positively homogeneous, $s_k(t\mathbf{A}) = ts_k(\mathbf{A})$ for $t \ge 0$ , since multiplying a Hermitian matrix by $t \ge 0$ multiplies each eigenvalue by $t$ without disturbing the order. Together these say that for $t \in [0,1]$ , $s_k\bigl(t\mathbf{A} + (1-t)\mathbf{B}\bigr) \ \le\ ts_k(\mathbf{A}) + (1-t)s_k(\mathbf{B}) :$ $s_k$ is a convex function on the real vector space of Hermitian matrices. That is exactly what one expects of a maximum of linear functions, which is what Theorem 17.6.2 says $s_k$ is: each fixed $\mathbf{Q}$ makes $\mathbf{A} \mapsto \operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})$ linear, and $s_k$ is the pointwise maximum of this family. Chapter 18 studies convex functions in general, and the observation that a pointwise supremum of linear functions is convex is one of its basic facts.

Corollary 17.6.6 (The Bottom Partial Sums as a Minimum)

Let $\mathbf{A} \in M_n(F)$ be Hermitian and let $1 \le k \le n$ . Then $\sum_{i=n-k+1}^{n}\lambda_i(\mathbf{A}) = \min\bigl\{\operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}) : \mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k\bigr\} ,$ the minimum being attained at the bottom $k$ eigenvectors.

Proof. The eigenvalues of $-\mathbf{A}$ , with multiplicity, are the negatives of those of $\mathbf{A}$ , and negation reverses order, so $\lambda_i(-\mathbf{A}) = -\lambda_{n+1-i}(\mathbf{A}) \qquad (1 \le i \le n) .$ Apply Theorem 17.6.2 to $-\mathbf{A}$ . Its left-hand side is $\sum_{i=1}^{k}\lambda_i(-\mathbf{A}) = -\sum_{i=1}^{k}\lambda_{n+1-i}(\mathbf{A}) = -\sum_{i=n-k+1}^{n}\lambda_i(\mathbf{A}) ,$ the last step re-indexing the sum. Its right-hand side is $\max_{\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k}\operatorname{tr}\bigl(\mathbf{Q}^{*}(-\mathbf{A})\mathbf{Q}\bigr) = -\min_{\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k}\operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}) ,$ using Theorem 0.9.6 (1) and the fact that maximizing $-g$ is minimizing $g$ . Negating both sides gives the claim, and the maximizer for $-\mathbf{A}$ is a list of top eigenvectors of $-\mathbf{A}$ , which are bottom eigenvectors of $\mathbf{A}$ .

Warning. Only the sums are convex. A single eigenvalue $\lambda_k$ with $1 < k < n$ is neither convex nor concave in $\mathbf{A}$ . Both failures happen among $3 \times 3$ diagonal matrices, where $\lambda_2$ is just the middle entry; for general $n$ and $1 < k < n$ , take the direct sum of each witness with $2\mathbf{I}_{k-2}$ above and $-\mathbf{I}_{n-k-1}$ below, which moves the middle entry to position $k$ without changing the computation.

Not convex. Take $\mathbf{A} = \operatorname{diag}(1,0,0)$ and $\mathbf{B} = \operatorname{diag}(0,1,0)$ , so $\lambda_2(\mathbf{A}) = \lambda_2(\mathbf{B}) = 0$ . Their midpoint is $\tfrac12(\mathbf{A}+\mathbf{B}) = \operatorname{diag}(\tfrac12, \tfrac12, 0)$ , with $\lambda_2 = \tfrac12$ . Convexity would require $\tfrac12 \le 0$ .

Not concave. Take $\mathbf{A} = \operatorname{diag}(1,1,0)$ and $\mathbf{B} = \operatorname{diag}(1,0,1)$ , so $\lambda_2(\mathbf{A}) = \lambda_2(\mathbf{B}) = 1$ . Their midpoint is $\operatorname{diag}(1, \tfrac12, \tfrac12)$ , with $\lambda_2 = \tfrac12$ . Concavity would require $\tfrac12 \ge 1$ .

The partial sum $s_2$ satisfies the convexity inequality on both pairs, as it must: in the first pair its values at the two matrices and their midpoint are $1, 1, 1$ , and in the second $2, 2, \tfrac32$ . The moral is that $\lambda_k = s_k - s_{k-1}$ is a difference of two convex functions, and a difference of convex functions has, in general, no convexity property at all. This is why the sharpest statements in this chapter are about sums, and why a statement about a single intermediate eigenvalue usually has to be proved as a statement about two sums.

17.6.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define the compression of $\mathbf{A}$ to a subspace, and say what has to be checked before the phrase “the eigenvalues of the compression” makes sense.
(b) State Theorem 17.6.2, including where the maximum is attained.
(c) Explain why the maximum in Theorem 17.6.2 does not need an appeal to compactness.
(d) Is $\mathbf{A} \mapsto \lambda_1(\mathbf{A})$ convex on the Hermitian matrices? Is $\mathbf{A} \mapsto \lambda_n(\mathbf{A})$ ? Justify each answer.
(e) State Theorem 17.6.1 and say which case of it is Theorem 17.4.2.

Solution.

(a) For an orthonormal list $\mathbf{q}_1, \dots, \mathbf{q}_k$ with matrix $\mathbf{Q}$ , the compression of $\mathbf{A}$ to $W = \operatorname{span}(\mathbf{q}_1,\dots,\mathbf{q}_k)$ is $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ , the $k \times k$ matrix with entries $\langle \mathbf{A}\mathbf{q}_j, \mathbf{q}_i \rangle$ . What must be checked is that changing the orthonormal basis of $W$ changes $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ only by a unitary similarity, so the eigenvalues depend on $W$ alone.
(b) For Hermitian $\mathbf{A} \in M_n(F)$ and $1 \le k \le n$ , $\sum_{i\le k}\lambda_i(\mathbf{A})$ is the maximum of $\operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})$ over all $\mathbf{Q} \in M_{n\times k}(F)$ with $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k$ , equivalently the maximum of $\sum_{i\le k}\langle \mathbf{A}\mathbf{q}_i, \mathbf{q}_i \rangle$ over orthonormal lists. It is attained at $\mathbf{Q} = (\mathbf{u}_1\ \dots\ \mathbf{u}_k)$ for an orthonormal eigenbasis ordered with $\mathbf{A}\mathbf{u}_i = \lambda_i(\mathbf{A})\mathbf{u}_i$ .
(c) Because the proof exhibits both a bound valid for every competitor and a competitor achieving it. A supremum that is achieved is a maximum, whatever the topology of the competing set.
(d) Incorrect. Take $\mathbf{A} = \operatorname{diag}(1,0,0)$ and $\mathbf{B} = \operatorname{diag}(0,1,0)$ as in the warning: $\lambda_2(\mathbf{A}) = \lambda_2(\mathbf{B}) = 0$ while $\mathbf{A} + \mathbf{B} = \operatorname{diag}(1,1,0)$ has $\lambda_2 = 1$ . What is true is the statement about sums, Corollary 17.6.5: here $\lambda_1 + \lambda_2$ of the sum is $2$ , and $(1+0) + (1+0) = 2$ .
(e) If $\mathbf{B}$ is the compression of the Hermitian $\mathbf{A} \in M_n(F)$ to a $k$ -dimensional subspace, then $\lambda_i(\mathbf{A}) \ge \lambda_i(\mathbf{B}) \ge \lambda_{i+n-k}(\mathbf{A})$ for $1 \le i \le k$ . Cauchy interlacing is the case $k = n-1$ with the subspace a coordinate hyperplane.

B. Practice

Exercise (B1: A compression, and two bounds)

Let $\mathbf{A} = \operatorname{diag}(5, 0, -2)$ and let $\mathbf{q}_1 = \tfrac13(1, 2, 2)$ , $\mathbf{q}_2 = \tfrac13(2, 1, -2)$ .

(a) Verify that $(\mathbf{q}_1, \mathbf{q}_2)$ is orthonormal and compute the compression $\mathbf{B}$ of $\mathbf{A}$ to $\operatorname{span}(\mathbf{q}_1, \mathbf{q}_2)$ .
(b) Find the eigenvalues of $\mathbf{B}$ and verify Theorem 17.6.1.
(c) Compare $\operatorname{tr}\mathbf{B}$ with the bound of Theorem 17.6.2, and say how far this subspace is from optimal.

Solution.

(a) $\left\| \mathbf{q}_1 \right\|^{2} = (1+4+4)/9 = 1$ , $\left\| \mathbf{q}_2 \right\|^{2} = (4+1+4)/9 = 1$ , and $9\langle \mathbf{q}_1, \mathbf{q}_2 \rangle = 2 + 2 - 4 = 0$ . Next $3\mathbf{A}\mathbf{q}_1 = (5, 0, -4)$ and $3\mathbf{A}\mathbf{q}_2 = (10, 0, 4)$ , so $\begin{aligned} b_{11} &= \tfrac19(1,2,2)\cdot(5,0,-4) = \tfrac{5 - 8}{9} = -\tfrac13, \\ b_{12} &= \tfrac19(1,2,2)\cdot(10,0,4) = \tfrac{10 + 8}{9} = 2, \\ b_{22} &= \tfrac19(2,1,-2)\cdot(10,0,4) = \tfrac{20 - 8}{9} = \tfrac43 , \end{aligned}$ so $\mathbf{B} = \begin{psmallmatrix} -1/3 & 2 \\ 2 & 4/3\end{psmallmatrix}$ .
(b) $\operatorname{tr}\mathbf{B} = 1$ and $\det\mathbf{B} = -\tfrac49 - 4 = -\tfrac{40}{9}$ , so $9x^{2} - 9x - 40 = 0$ , with discriminant $81 + 1440 = 1521 = 39^{2}$ and roots $(9 \pm 39)/18$ . Hence $\lambda_1(\mathbf{B}) = \tfrac83$ and $\lambda_2(\mathbf{B}) = -\tfrac53$ . The separation $\lambda_i(\mathbf{A}) \ge \lambda_i(\mathbf{B}) \ge \lambda_{i+1}(\mathbf{A})$ reads $5 \ \ge\ \tfrac83 \ \ge\ 0 \ \ge\ -\tfrac53 \ \ge\ -2 ,$ all strict.
(c) $\operatorname{tr}\mathbf{B} = 1$ , while Theorem 17.6.2 gives $\lambda_1(\mathbf{A}) + \lambda_2(\mathbf{A}) = 5 + 0 = 5$ as the maximum, attained at $\operatorname{span}(\mathbf{e}_1, \mathbf{e}_2)$ . So this subspace scores $1$ out of a possible $5$ ; it is far from optimal, and one can see why. Between them $\mathbf{q}_1$ and $\mathbf{q}_2$ put weight $\tfrac49 + \tfrac49 = \tfrac89$ on the third coordinate, where $\mathbf{A}$ is $-2$ , and only $\tfrac19 + \tfrac49 = \tfrac59$ on the first, where it is $5$ : indeed $5\cdot\tfrac59 + 0 - 2\cdot\tfrac89 = 1$ .

Exercise (B2: Reading the sums off the spectrum)

A Hermitian $\mathbf{A} \in M_4(\mathbb{R})$ has eigenvalues $6, 4, 1, -3$ .

(a) Compute $\max\{\operatorname{tr}(\mathbf{Q}^{\top}\mathbf{A}\mathbf{Q}) : \mathbf{Q}^{\top}\mathbf{Q} = \mathbf{I}_k\}$ for $k = 1, 2, 3, 4$ .
(b) Compute the corresponding minima, using Corollary 17.6.6.
(c) For $\mathbf{A} = \operatorname{diag}(6, 4, 1, -3)$ and $\mathbf{q}_1 = \tfrac1{\sqrt2}(1,1,0,0)$ , $\mathbf{q}_2 = \tfrac1{\sqrt2}(0,0,1,1)$ , compute $\operatorname{tr}(\mathbf{Q}^{\top}\mathbf{A}\mathbf{Q})$ and check it against (a) and (b).

Solution.

(a) By Theorem 17.6.2 the maxima are the partial sums from the top: $6$ , $10$ , $11$ , $8$ .
(b) By Corollary 17.6.6 the minima are the partial sums from the bottom: $-3$ , $-2$ , $2$ , $8$ . The two agree at $k = 4$ , as they must, both being $\operatorname{tr}\mathbf{A}$ .
(c) $\langle \mathbf{A}\mathbf{q}_1, \mathbf{q}_1 \rangle = \tfrac12(6 + 4) = 5$ and $\langle \mathbf{A}\mathbf{q}_2, \mathbf{q}_2 \rangle = \tfrac12(1 - 3) = -1$ , so $\operatorname{tr}(\mathbf{Q}^{\top}\mathbf{A}\mathbf{Q}) = 4$ . Indeed $-2 \le 4 \le 10$ , as (a) and (b) require for $k = 2$ .

Exercise (B3: Subadditivity, and how loose it can be)

Let $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 1 & 1\end{pmatrix}, \qquad \mathbf{B} = \begin{pmatrix} 1 & -1 \\ -1 & 1\end{pmatrix} .$

(a) Compute the eigenvalues of $\mathbf{A}$ , of $\mathbf{B}$ , and of $\mathbf{A} + \mathbf{B}$ .
(b) Verify Corollary 17.6.5 for $k = 1$ and $k = 2$ , and say for which $k$ it is strict.
(c) Give a pair of Hermitian $2 \times 2$ matrices for which the $k = 1$ inequality is an equality.

Solution.

(a) $\mathbf{A}$ has trace $2$ and determinant $0$ , so its eigenvalues are $2, 0$ ; the same for $\mathbf{B}$ . And $\mathbf{A} + \mathbf{B} = 2\mathbf{I}_2$ has eigenvalues $2, 2$ .
(b) For $k = 1$ : $\lambda_1(\mathbf{A}+\mathbf{B}) = 2$ and $\lambda_1(\mathbf{A}) + \lambda_1(\mathbf{B}) = 4$ , so $2 \le 4$ , strictly. For $k = 2$ : $4 \le 2 + 2 = 4$ , an equality — as it must be, since for $k = n$ both sides are traces and Theorem 0.9.6 (1) makes the trace additive.
(c) Take $\mathbf{A} = \mathbf{B} = \operatorname{diag}(1,0)$ . Then $\mathbf{A} + \mathbf{B} = \operatorname{diag}(2,0)$ and $\lambda_1(\mathbf{A}+\mathbf{B}) = 2 = 1 + 1$ . More generally equality holds at $k = 1$ whenever $\mathbf{A}$ and $\mathbf{B}$ have a common top eigenvector, because then that one vector attains all three maxima at once.

C. Going deeper

Exercise (C1: The Loewner order and the partial sums)

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

(a) Prove that $\mathbf{A} \succeq \mathbf{B}$ implies $\sum_{i\le k}\lambda_i(\mathbf{A}) \ge \sum_{i\le k}\lambda_i(\mathbf{B})$ for every $k$ . Hint: compare the two maximization problems of Theorem 17.6.2 competitor by competitor.
(b) Show that the converse fails: give Hermitian $\mathbf{A}, \mathbf{B}$ satisfying all $n$ of these inequalities with $\mathbf{A} \not\succeq \mathbf{B}$ .

Solution.

(a) Let $\mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k$ with columns $\mathbf{q}_1, \dots, \mathbf{q}_k$ . Since $\mathbf{A} - \mathbf{B} \succeq \mathbf{O}$ , clause (P2) of Definition 13.1.1 gives $\langle (\mathbf{A}-\mathbf{B})\mathbf{q}_i, \mathbf{q}_i \rangle \ge 0$ for each $i$ , that is, $\langle \mathbf{A}\mathbf{q}_i, \mathbf{q}_i \rangle \ge \langle \mathbf{B}\mathbf{q}_i, \mathbf{q}_i \rangle$ . Summing over $i$ , $\operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}) \ \ge\ \operatorname{tr}(\mathbf{Q}^{*}\mathbf{B}\mathbf{Q}) .$ Now take $\mathbf{Q}$ to be a maximizer for $\mathbf{B}$ in Theorem 17.6.2. Then $\sum_{i\le k}\lambda_i(\mathbf{B}) = \operatorname{tr}(\mathbf{Q}^{*}\mathbf{B}\mathbf{Q}) \le \operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}) \le \sum_{i\le k}\lambda_i(\mathbf{A}) ,$ the last step because $\mathbf{Q}$ is one competitor in the maximization for $\mathbf{A}$ .
(b) Take $\mathbf{A} = \operatorname{diag}(2, 0)$ and $\mathbf{B} = \operatorname{diag}(1, 1)$ . The partial sums are $2 \ge 1$ for $k = 1$ and $2 \ge 2$ for $k = 2$ . But $\mathbf{A} - \mathbf{B} = \operatorname{diag}(1, -1)$ has a negative eigenvalue, so $\mathbf{A} - \mathbf{B} \not\succeq \mathbf{O}$ by Theorem 13.1.4 (b), and $\mathbf{A} \not\succeq \mathbf{B}$ . Concretely, $\langle (\mathbf{A}-\mathbf{B})\mathbf{e}_2, \mathbf{e}_2 \rangle = -1 < 0$ .

Exercise (C2: Partial sums that behave like a norm)

For positive semidefinite $\mathbf{A} \in M_n(F)$ and $1 \le k \le n$ , consider $s_k(\mathbf{A}) = \sum_{i\le k}\lambda_i(\mathbf{A})$ , the partial sum of this section, now restricted to the positive semidefinite matrices.

(a) Prove that $N_k(\mathbf{A}) \ge 0$ , with equality if and only if $\mathbf{A} = \mathbf{O}$ .
(b) Prove that $N_k(c\mathbf{A}) = cN_k(\mathbf{A})$ for every real $c \ge 0$ , and that $N_k(\mathbf{A} + \mathbf{B}) \le N_k(\mathbf{A}) + N_k(\mathbf{B})$ for positive semidefinite $\mathbf{A}, \mathbf{B}$ .
(c) The positive semidefinite matrices form a cone, not a vector space, so a norm cannot be defined on them. Deduce instead that $s_k$ is positive, positively homogeneous, and subadditive on this cone. Which step of your argument for (a) uses positive semidefiniteness, and what goes wrong without it?

Solution.

(a) By Theorem 13.1.4 (b) every eigenvalue of $\mathbf{A}$ is $\ge 0$ , so $N_k(\mathbf{A}) \ge \lambda_1(\mathbf{A}) \ge 0$ for $k \ge 1$ . If $N_k(\mathbf{A}) = 0$ then in particular $\lambda_1(\mathbf{A}) = 0$ , so every eigenvalue is $0$ ; by Corollary 12.4.3 (or Corollary 12.5.2) $\mathbf{A} = \mathbf{U}\mathbf{O}\mathbf{U}^{*} = \mathbf{O}$ . Conversely $N_k(\mathbf{O}) = 0$ .
(b) Multiplying a Hermitian matrix by $c \ge 0$ multiplies each eigenvalue by $c$ and preserves the decreasing order, so $\lambda_i(c\mathbf{A}) = c\lambda_i(\mathbf{A})$ and the first claim follows by summing. The second is Corollary 17.6.5, which needs no positivity at all.
(c) Positivity with $N_k(\mathbf{A}) = 0$ only for $\mathbf{A} = \mathbf{O}$ is (a); homogeneity under scalars $c \ge 0$ is (b); subadditivity is (b). So $N_k$ behaves as a norm wherever it is defined. It cannot be extended to all Hermitian matrices by the same formula: for $\mathbf{A} = \operatorname{diag}(0, -1)$ and $k = 1$ we get $N_1(\mathbf{A}) = 0$ with $\mathbf{A} \ne \mathbf{O}$ , so the positivity clause fails, and for $c = -1$ the value $N_1(-\mathbf{A}) = 1$ differs from $\lvert c\rvert N_1(\mathbf{A}) = 0$ . The repair is to apply $N_k$ to the singular values instead of the eigenvalues, which is what Chapter 21 does.

Exercise (C3: How much of a matrix a subspace holds)

Let $\mathbf{A} \in M_{m\times n}(F)$ with singular values $\sigma_1 \ge \dots \ge \sigma_p$ extended by zeros as in Corollary 17.6.4, let $S \subseteq F^{m}$ have dimension $k$ , and let $\mathbf{Q}$ have as columns an orthonormal basis of $S$ , so that $P_S = \mathbf{Q}\mathbf{Q}^{*}$ by Theorem 11.3.3 (a).

(a) Prove that $\left\| P_S\mathbf{A} \right\|_F^{2} = \operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{A}^{*}\mathbf{Q})$ .
(b) Deduce from Theorem 17.6.2 that $\left\| P_S\mathbf{A} \right\|_F^{2} \le \sigma_1^{2} + \dots + \sigma_k^{2}$ , with equality when $S$ is spanned by the first $k$ left singular vectors.
(c) Hence recover the value $\sum_{i>k}\sigma_i^{2}$ of the minimum in Corollary 13.11.4. Hint: $\mathbf{a} - P_S\mathbf{a}$ is orthogonal to $P_S\mathbf{a}$ .

Solution.

(a) The Frobenius norm satisfies $\left\| \mathbf{X} \right\|_F^{2} = \operatorname{tr}(\mathbf{X}^{*}\mathbf{X})$ , because the $(j,j)$ entry of $\mathbf{X}^{*}\mathbf{X}$ is the squared length of the $j$ -th column of $\mathbf{X}$ . With $P_S = \mathbf{Q}\mathbf{Q}^{*}$ , which is Hermitian and satisfies $P_S^{2} = \mathbf{Q}(\mathbf{Q}^{*}\mathbf{Q})\mathbf{Q}^{*} = P_S$ , $\left\| P_S\mathbf{A} \right\|_F^{2} = \operatorname{tr}(\mathbf{A}^{*}P_S^{*}P_S\mathbf{A}) = \operatorname{tr}(\mathbf{A}^{*}\mathbf{Q}\mathbf{Q}^{*}\mathbf{A}) = \operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{A}^{*}\mathbf{Q}) ,$ the last step by Theorem 0.9.6 (3) applied to $\mathbf{A}^{*}\mathbf{Q}$ and $\mathbf{Q}^{*}\mathbf{A}$ .
(b) The matrix $\mathbf{M} = \mathbf{A}\mathbf{A}^{*}$ is Hermitian with $\lambda_i(\mathbf{M}) = \sigma_i^{2}$ , as computed in the proof of Corollary 17.6.4. By Theorem 17.6.2 with $k$ columns, $\operatorname{tr}(\mathbf{Q}^{*}\mathbf{M}\mathbf{Q}) \le \sum_{i\le k}\lambda_i(\mathbf{M}) = \sum_{i\le k}\sigma_i^{2} ,$ with equality when the columns of $\mathbf{Q}$ are top eigenvectors of $\mathbf{M}$ . From $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}$ the columns $\mathbf{u}_1, \dots, \mathbf{u}_m$ of $\mathbf{U}$ are exactly such an eigenbasis, so equality holds for $S = \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_k)$ .
(c) Write $\mathbf{a}_1, \dots, \mathbf{a}_n$ for the columns of $\mathbf{A}$ . For each $j$ the vectors $P_S\mathbf{a}_j$ and $\mathbf{a}_j - P_S\mathbf{a}_j$ are orthogonal, so Theorem 11.1.3 gives $\left\| \mathbf{a}_j \right\|^{2} = \left\| P_S\mathbf{a}_j \right\|^{2} + \left\| \mathbf{a}_j - P_S\mathbf{a}_j \right\|^{2}$ . Summing over $j$ , $\sum_{j} d(\mathbf{a}_j, S)^{2} = \left\| \mathbf{A} \right\|_F^{2} - \left\| P_S\mathbf{A} \right\|_F^{2} .$ By Lemma 13.11.1, $\left\| \mathbf{A} \right\|_F^{2} = \sum_i \sigma_i^{2}$ . By (b) the subtracted term is at most $\sum_{i\le k}\sigma_i^{2}$ , with equality for $S = \operatorname{span}(\mathbf{u}_1,\dots,\mathbf{u}_k)$ . Hence the total squared distance is at least $\sum_{i>k}\sigma_i^{2}$ , and equals it for that $S$ ; a subspace of smaller dimension $k' < k$ does no better, since the same argument bounds what it captures by $\sum_{i \le k'}\sigma_i^{2} \le \sum_{i\le k}\sigma_i^{2}$ — which is Corollary 13.11.4, now read as a statement about a maximum of traces rather than a minimum of distances.