Matrix Inequalities

Five chapters have left inequalities unpaid, and they turn out to be one inequality seen from five sides. Chapter 13 §09 and §10 said that the truncated singular value decomposition and the unitary polar factor are nearest in “every unitarily invariant norm”, a phrase it could not define. Chapter 16 §08 admitted that it had never said which norms those are. Chapter 17 §06 found a family of functionals that fail to be norms on Hermitian matrices and guessed the repair; §07 proved a majorization and left its consequences open; §11 stated Loewner’s theorem once, promised this chapter’s proof four times, and proved none of it. Chapter 18 §10 and §11 deferred the convexity of $\mathbf{A} \mapsto \operatorname{tr} f(\mathbf{A})$ . Chapter 19 §07 and §09 deferred the theorem of Hardy, Littlewood and Pólya. Chapter 20 §05, §10 and §11 wanted Weyl’s, Mirsky’s and Hoffman–Wielandt’s bounds inside one statement.

The organizing fact behind all of them is majorization, the order $\mathbf{x} \prec \mathbf{y}$ that Chapter 17 §08 defined. This chapter closes the circle in four movements.

Majorization is a doubly stochastic map. $\mathbf{x} \prec \mathbf{y}$ exactly when $\mathbf{x} = \mathbf{D}\mathbf{y}$ for a doubly stochastic $\mathbf{D}$ , and with Birkhoff’s theorem, exactly when $\mathbf{x}$ lies in the convex hull of the permutations of $\mathbf{y}$ . Convexity then acts one row at a time, and every convex function respects the order.
A majorization becomes a norm inequality. The norms that cannot tell coordinates apart are the symmetric gauge functions; composing one with the singular values gives a unitarily invariant norm, and every unitarily invariant norm arises this way exactly once. Ky Fan dominance then says that “ $\left|\!\left|\!\left| \mathbf{A} \right|\!\right|\!\right| \le \left|\!\left|\!\left| \mathbf{B} \right|\!\right|\!\right|$ for every unitarily invariant norm” and “ $\sigma(\mathbf{A}) \prec_w \sigma(\mathbf{B})$ ” are the same statement.
The deferred theorems fall out. Eckart–Young, the nearest unitary matrix, Lidskii and Mirsky, each in every unitarily invariant norm at once.
The order-theoretic side. Which functions preserve the Loewner order $\mathbf{A} \succeq \mathbf{B}$ ? Very few: Loewner’s theorem says they are exactly the functions with a particular integral representation, and the powers $t^{p}$ qualify only for $0 \le p \le 1$ . The chapter ends with the exponential, where Golden and Thompson’s trace inequality replaces the identity $e^{a+b} = e^{a}e^{b}$ that matrices cannot have.

Matrices are complex unless a statement says otherwise, and $f$ applied to a Hermitian matrix always means the spectral functional calculus of Chapter 12 §08 (Definition 12.8.2). Four notational conventions hold throughout.

$\boldsymbol{\uplambda}(\mathbf{A})$ is the decreasing eigenvalue list of a Hermitian $\mathbf{A}$ , $\sigma(\mathbf{A})$ the decreasing singular value list, and $\mathbf{x}^{\downarrow}$ the decreasing rearrangement of a real vector, as in Chapter 17.
Majorization is Chapter 17 §08’s (Definition 17.8.1), with $\prec_w$ the top-sums version.
A unitarily invariant norm is written $\left|\!\left|\!\left| \mathbf{A} \right|\!\right|\!\right|$ , with triple bars, to keep it apart from any particular norm. Symmetric gauge functions are $\Phi$ ; Chapter 18 §04’s gauge $p_K$ of a convex set is a different object with the same word, and §03 says so once.
The order on matrices is always the Loewner order $\mathbf{A} \succeq \mathbf{B}$ of Chapter 13 §05 (Definition 13.5.1). No matrix is ever compared entrywise: the order of Chapters 18 and 19 is used here only on vectors, as $\mathbf{x} \le \mathbf{y}$ in §03, which says so at its head.

The analysis this chapter imports

The list is Chapter 16’s, facts (A1)–(A6) of that chapter’s introduction — completeness, monotone convergence, compactness of closed bounded sets, the extreme value theorem, the intermediate value theorem and the mean value theorem — together with the algebra of limits. Each is named again where it is used, except the intermediate value theorem (A5), which this chapter never needs. The weight falls on three: (A1) and (A3) build §10’s integral, completeness for the convergence of the Riemann sums and compactness for the uniform continuity of the integrand, and (A6) is how §09 turns a non-negative derivative into monotonicity along a segment. Section 9 also uses (A3) and (A4) for the same two jobs, uniform continuity and boundedness on a compact interval, and (A2) bounds the improper integral of §10 that represents $t^{p}$ .

One fact is quoted beyond that list, and it is this chapter’s own. Loewner’s theorem cannot be proved from (A1)–(A6): its analytic half is a theorem about functions of a complex variable. The book’s practice, as with Taylor’s theorem in Chapter 14 §06 and the theorem of Abel and Ruffini in Chapter 11, is to quote one named result at its point of use and prove everything else. So:

(A7) (Pick and Nevanlinna.) Let $I \subseteq \mathbb{R}$ be an open interval and $f \colon I \to \mathbb{R}$ . Suppose the Loewner matrix $\bigl[f[t_i, t_j]\bigr]_{i,j=1}^{n}$ of divided differences is positive semidefinite for every $n$ and all $t_1, \dots, t_n \in I$ . Then $f$ is the restriction to $I$ of a function that is analytic on $\mathbb{C} \setminus (\mathbb{R} \setminus I)$ and maps the upper half plane into its closure; and every such function has the integral representation of Chapter 17 §11’s Theorem 17.11.9 (ii). In particular such an $f$ is automatically infinitely differentiable on $I$ .

(A7) is stated once, in §10, and used three times there. Its clause (c) supplies the smoothness that §09’s criterion asks for, its clause (a) the implication (i) $\Rightarrow$ (iii) of Loewner’s theorem, and its clause (b) the implication (iii) $\Rightarrow$ (ii). Together they give the one thing the chapter cannot prove: that a function which is operator monotone of every order has the integral representation. No other section uses it, and everything else in the chapter is proved.

What this means in practice is worth spelling out, because the reader should know which results are conditional.

Resting on (A7): only the implication just named, and therefore only the “hard” direction of Theorem 17.11.9 — that (i) implies (ii). Section 10 marks each step where it enters.
Not resting on (A7): everything in §§01–08, §11 and §12; the whole of §09, including the criterion that, for a continuously differentiable $f$ , monotonicity of order $n$ is exactly positivity of every $n \times n$ Loewner matrix, which is the elementary heart of Loewner’s theorem and is proved in full; the easy direction of Loewner’s theorem, that the integral representation forces operator monotonicity, which §10 proves outright; the operator monotonicity of $t^{p}$ for $0 \le p \le 1$ and of $\log t$ , both obtained from that easy direction together with an explicit representation; and the three negative results — that $t^{p}$ fails for every $p > 1$ , that $t^{2}$ fails already at order $2$ , and that $e^{t}$ is not operator monotone — which come from §09’s criterion and from explicit two-by-two witnesses.

Section 10 also integrates a continuous matrix-valued function over a compact interval. That is not imported: the section builds the integral entrywise as a limit of Riemann sums, using only (A1)–(A4), and proves the one property it needs, that an integral of positive semidefinite matrices is positive semidefinite. Beyond the list, the only analytic fact quoted is the fundamental theorem of calculus, which §10 uses twice and flags both times: in a remark, to check the logarithm’s integral representation, and in an exercise, to evaluate the constant $K_{1/2}$ . Neither use is a step in a proof. In particular §09’s derivative of a matrix function is obtained without the implicit function theorem, exactly as Chapter 20 §11’s derivative of a simple eigenvalue was.

What you need

Chapter 0 §09 — matrix multiplication, and the trace with its cyclic invariance: Definition 0.9.9, Theorem 0.9.6.
Chapter 3 — the invertibility criteria and permutation matrices: Theorem 3.4.4, Definition 3.4.2, Lemma 3.4.7.
Chapter 6 §06 — Lagrange interpolation: Theorem 6.6.1.
Chapter 7 §05 — multiplicativity of the determinant and the determinant test for invertibility, in the exercises of §§06 and 11 only; no proof in the chapter needs a determinant: Theorem 7.5.4, Theorem 7.5.3.
Chapter 8 §01 — block multiplication: Theorem 8.1.1.
Chapter 9 — the trace and determinant read off the eigenvalues, and the spectra of $\mathbf{A}\mathbf{B}$ and $\mathbf{B}\mathbf{A}$ : Theorem 9.3.3, Theorem 9.10.4.
Chapter 10 §09 — the matrix exponential: Definition 10.9.2, Theorem 10.9.4.
Chapter 11 §01 and §07 — the Frobenius inner product, Pythagoras and Cauchy–Schwarz, and the unitary invariance of the Frobenius norm: Theorem 11.1.3, Theorem 11.1.5, Lemma 11.7.5.
Chapter 12 — the spectral theorem, the spectral resolution and the functional calculus: Corollary 12.1.4, Theorem 12.2.1, Corollary 12.4.3, Corollary 12.5.2, Definition 12.8.1, Theorem 12.8.1, Theorem 12.8.2, Definition 12.8.2, Theorem 12.8.3, Theorem 12.8.5.
Chapter 13 — positive semidefiniteness, square roots, the Loewner order, the Schur product theorem and the singular value and polar decompositions: Definition 13.1.1, Proposition 13.1.2, Theorem 13.1.4, Theorem 13.1.5, Theorem 13.2.1, Definition 13.5.1, Proposition 13.5.1, Lemma 13.5.2, Theorem 13.5.3, Example (Squaring does not preserve the Loewner order), Proposition 13.5.4, Theorem 13.6.1, Definition 13.7.1, Theorem 13.7.2, Definition 13.8.1, Theorem 13.8.1, Theorem 13.8.2, Theorem 13.9.1, Corollary 13.9.2, Definition 13.10.1, Theorem 13.10.3.
Chapter 15 §04 — the pairing Chapter 15 calls a contraction, a word §08 gives a different meaning: Definition 15.4.1 (named so that the clash is visible, not used).
Chapter 16 — norms, the operator norm, entrywise convergence, bounds for the exponential and the derivative of a matrix-valued function: Definition 16.1.1, Example (The $1$ -, $2$ - and $\infty$ -norms on $F^n$ ), Corollary 16.2.4, Definition 16.3.2, Theorem 16.3.2, Theorem 16.3.3, Theorem 16.6.1, Definition 16.6.1.
Chapter 17 — the variational descriptions, Weyl’s and Lidskii’s inequalities, majorization, the Hermitian dilation and the operator monotone functions: Corollary 17.2.4, Lemma 17.3.5, Corollary 17.3.6, Theorem 17.6.2, Corollary 17.6.5, Exercise (C2: Partial sums that behave like a norm), Theorem 17.7.2, Definition 17.8.1, Example (A chain, the two extremes, and size one), Proposition 17.8.1, Lemma 17.8.3, Lemma 17.8.6, Lemma 17.9.1, Theorem 17.9.2, Proposition 17.9.3, Theorem 17.9.4, Corollary 17.9.5, Theorem 17.9.6, Definition 17.11.1, Proposition 17.11.1, Proposition 17.11.2, Proposition 17.11.3, Proposition 17.11.4, Corollary 17.11.5, Proposition 17.11.8, Theorem 17.11.9.
Chapter 18 — convex sets and hulls, convex functions, Jensen’s inequality, gauges and duality, and the classical inequalities: Example (The vectors majorized by a fixed vector), Proposition 18.1.1, Lemma 18.1.2, Definition 18.1.4, Theorem 18.1.3, Definition 18.4.1, Definition 18.4.4, Proposition 18.4.6, Proposition 18.4.7, Theorem 18.4.8, Definition 18.8.3, Definition 18.8.4, Definition 18.10.1, Example (First convex functions), Theorem 18.10.2, Proposition 18.10.3, Lemma 18.10.5, Theorem 18.10.6, Lemma 18.11.1, Corollary 18.11.5, Theorem 18.11.6.
Chapter 19 §07 — Birkhoff’s theorem and the half of Hardy–Littlewood–Pólya already proved: Theorem 19.7.2, Proposition 19.7.6.
Chapter 20 — the derivative of a simple eigenvalue, the norm toolkit behind Davis–Kahan, and the perturbation bounds this chapter upgrades: Corollary 20.5.4, Lemma 20.9.1, Theorem 20.10.1, Theorem 20.11.2.

Roadmap

Doubly stochastic maps. T-transforms average two coordinates, and finitely many of them turn $\mathbf{y}$ into any $\mathbf{x} \prec \mathbf{y}$ . That is the theorem of Hardy, Littlewood and Pólya, and with Birkhoff’s theorem it says that the majorization order is containment of permutation polytopes.
Convex functions of a majorization. Karamata’s inequality, its converse, Schur-convex and Schur-concave functions, and the convexity of $\mathbf{A} \mapsto \operatorname{tr} f(\mathbf{A})$ for every convex $f$ .
Symmetric gauge functions. Norms on $\mathbb{R}^{n}$ blind to the order and the signs of the coordinates. They are monotone under weak majorization, and they have a duality theory of their own.
Unitarily invariant norms. The norms unchanged by unitary factors on either side: the Frobenius and spectral norms, the Ky Fan $k$ -norms and the Schatten $p$ -norms. Von Neumann’s correspondence matches them exactly with the symmetric gauges, through $\left|\!\left|\!\left| \mathbf{A} \right|\!\right|\!\right| = \Phi(\sigma(\mathbf{A}))$ .
The trace inequality. $\lvert\operatorname{tr}(\mathbf{A}^{*}\mathbf{B})\rvert \le \sum_i\sigma_i(\mathbf{A})\sigma_i(\mathbf{B})$ , and the duality it gives between a unitarily invariant norm and the norm of the dual gauge.
Ky Fan dominance. Weak majorization of singular values is equivalent to domination in every unitarily invariant norm. Eckart–Young and the nearest unitary matrix follow, in every such norm.
Lidskii in majorization form. Chapter 17’s majorization, run through the previous three sections, yields one bound for every convex function and one for every unitarily invariant norm, with Hoffman–Wielandt and Mirsky as special cases.
Operator convex functions. The Hansen–Pedersen–Jensen inequality $f(\mathbf{V}^{*}\mathbf{A}\mathbf{V}) \preceq \mathbf{V}^{*}f(\mathbf{A})\mathbf{V}$ for a contraction $\mathbf{V}$ , proved by dilating $\mathbf{V}$ to a unitary matrix, and the contrast with the far weaker trace convexity of §02.
Loewner matrices. The derivative of $f$ at a diagonal matrix is a Hadamard product with the matrix of divided differences. With the Schur product theorem this makes monotonicity of order $n$ equivalent to positivity of every $n \times n$ Loewner matrix.
Loewner’s theorem. The three conditions of Chapter 17 §11 are equivalent. One implication quotes (A7); the rest is proved, including the integral machinery. The powers $t^{p}$ are operator monotone exactly for $0 \le p \le 1$ , $\log t$ is, and $e^{t}$ is not.
Means and matrix Cauchy–Schwarz. Cauchy–Schwarz and the arithmetic–geometric mean inequality for matrices, each holding in every unitarily invariant norm at once; then the matrix geometric mean $\mathbf{A} \# \mathbf{B}$ , its surprising symmetry, and the chain from the harmonic through the geometric to the arithmetic mean in the Loewner order.
Golden–Thompson. Lie’s product formula, a trace inequality for powers of a product of two positive matrices, and $\operatorname{tr} e^{\mathbf{A}+\mathbf{B}} \le \operatorname{tr}(e^{\mathbf{A}}e^{\mathbf{B}})$ . Three matrices break it. Then Klein’s inequality and the relative entropy, Lieb’s concavity theorem stated and not proved, and a summary that closes the chapter and Part V.

Named moves

A majorization is a doubly stochastic map. Turn the family of partial-sum inequalities into a single linear map, and let convexity act one row at a time.
A symmetric gauge turns a weak majorization into a norm inequality. To prove one inequality for a whole family of norms, find the combinatorial statement about the underlying numbers that every member of the family respects.
A Hermitian dilation turns singular values into eigenvalues. Every theorem about the eigenvalues of a Hermitian matrix has a singular-value twin, obtained by applying it to $\mathcal{H}(\mathbf{A})$ .
The Schur product theorem turns a Loewner matrix into monotonicity. Differentiate a matrix function, recognize the derivative as an entrywise product with a positive semidefinite matrix, and integrate along a segment.
A limit of Riemann sums carries the Loewner order through an integral. An order defined by a closed convex cone survives every limit, so it survives integration.
Lie’s product formula turns a sum in the exponent into a product. Split one operation into $k$ small steps, make the error of a single step $O(1/k^{2})$ , and let telescoping absorb the factor $k$ .