Norms and Matrix Analysis

Nine chapters have been writing promissory notes. Chapter 9 asked what happens to ${\mathbf{A}}^m$ and Chapter 10 §10 answered exactly, entry by entry, with no number attached to the answer: Theorem 10.10.2 says whether the powers die out, never how fast. Chapter 10 §09 built $e^{\mathbf{A}}$ out of a series (Definition 10.9.2) and promised that the estimates would come once there was something to estimate with. Chapter 11 solved the least-squares problem (Theorem 11.4.2) and then, at Theorem 11.8.1, recommended one algorithm over another for a reason it could not yet state. Chapter 12 §01 proved that every matrix has a diagonalizable matrix arbitrarily close to it (Corollary 12.1.6) and left the word “close” doing work no definition supported. Chapter 13 §08 met a number, the largest stretching factor of a matrix, and said that this chapter would give it a name. Every one of those debts is the same debt: the book has had no way to say how big a vector or a matrix is, except through one particular inner product.

A norm is that way. It keeps exactly what measurement needs — a length is zero only for the zero vector, it scales with the scalar, and a detour is never shorter than the direct route — and it throws away the inner product that Chapter 11 used to produce it. There are many norms, and the first surprise is that in finite dimension it does not matter which one you pick: any two of them are trapped between constant multiples of each other, so they agree about every limit, every bounded set and every continuous function. The second surprise is that the constants cannot be made independent of the dimension, and that the whole theorem collapses in infinite dimension. From there the chapter measures matrices, and then uses the measurements: the spectral radius as the infimum of all the norms, a geometric series that inverts $\mathbf{I}-\mathbf{A}$, quantitative bounds for the exponential, the continuity of eigenvalues, and finally the condition number, which is the exact constant in the sentence “a small change in the data produces a small change in the answer”.

The field in this chapter is $\mathbb{R}$ or $\mathbb{C}$. A norm returns a real number and its homogeneity clause uses $|c|$, so the scalars must have an absolute value; no other field in this book has one. This is the same restriction Chapters 11 to 13 worked under, and for the same reason.

The analysis this chapter imports

This chapter leans on analysis harder than any before it, and the book’s practice is to name what it borrows rather than let it pass unnoticed — as Chapter 14 §06 did with Taylor’s theorem, and Chapter 11 with the theorem of Abel and Ruffini. Here is the complete list. Each item is standard, each is quoted without proof, and each is named again at the point where it is used.

Alongside these, the elementary algebra of limits is used throughout without further comment: limits respect sums, products and quotients with non-vanishing denominator; sums, products and composites of continuous functions are continuous; and a non-strict inequality survives a limit, so that $a_k\le M$ for every $k$ forces $lim{a}_k\le M$. Chapter 10 §09 quoted the same package as its fact (A3). What the list above records is everything beyond that.

Several of these speak of continuity, which the book has not needed until now, so fix the meaning here. A function $f$ defined on a subset of a normed space is continuous at $\mathbf{x}$ when $\Vert {\mathbf{x}}_k-\mathbf{x}\Vert \to 0$ forces $f({\mathbf{x}}_k)\to f(\mathbf{x})$ for every sequence $({\mathbf{x}}_k)$ in its domain, and continuous when it is continuous at every point of its domain. This is the sequential form, matching the way (A3) is stated. Every continuity claim in this chapter is established the same cheap way: by exhibiting a constant $M$ with $|f(\mathbf{x})-f(\mathbf{y})|\le M\Vert \mathbf{x}-\mathbf{y}\Vert$, which gives the implication at once. §02 proves the first such bound.

Nothing else analytic enters silently. Where a section needs a fact outside this list — the differentiability of the entries of a matrix-valued function, or the continuous dependence of the roots of a polynomial on its coefficients — it is recorded as an assumption in the same manner, with a counterexample proved where one is available, and never used as a step in a proof that pretends to be self-contained.

What you need

The chapter is built on results the book already has. Gathered by source, so that a reader can go back to one place at a time:

• Chapter 0 §06 and §09 — two small facts, each used once: the triangle inequality for complex numbers, which §07 needs before it can bound a sum of moduli, and the cyclic invariance of the trace, which §06 uses on the Frobenius inner product: Theorem 0.6.4, Theorem 0.9.6.
• Chapter 2, with Chapter 1 for the words — bases, dimension and coordinates: Definition 1.5.1, Definition 1.6.1, Definition 1.5.2, Theorem 1.5.2, Corollary 2.5.5. What the proofs cite is the coordinate isomorphism; basis and dimension are vocabulary the chapter assumes rather than results it leans on.
• Chapter 11 §01 and §07 — the inner product and the norm it induces, with their three properties and the two inequalities that follow: Definition 11.1.1, Definition 11.1.3, Theorem 11.1.2, Theorem 11.1.5, Corollary 11.1.6, together with the two exercises that recover an inner product from its norm, Exercise (C1: The parallelogram law characterizes inner-product norms) and Exercise (C2: Recovering the inner product from the norm); and, from §07, the Frobenius norm and its unitary invariance, Lemma 11.7.5.
• Chapter 11 §04 and §08 — least squares and the $\mathbf{Q}\mathbf{R}$ factorization whose stability claim was deferred: Theorem 11.4.2, Corollary 11.4.4, Theorem 11.8.1.
• Chapter 10 §10 — the whole convergence apparatus that this chapter re-proves with numbers attached: Definition 10.10.1, Lemma 10.10.1, Theorem 10.10.2, Theorem 10.10.3, Theorem 10.10.4, Theorem 10.10.6, Corollary 10.10.5.
• Chapter 10 §09 and §03 — the matrix exponential and the Jordan form: Definition 10.9.2, Theorem 10.9.3, Theorem 10.9.4, Theorem 10.3.1.
• Chapter 7 — determinants, and only in §§06 and 07: the Leibniz formula, minors and cofactors, Laplace expansion and the adjugate identity, which between them make the entries of an inverse polynomial in the entries of the matrix; and the characteristic polynomial: Theorem 7.4.3, Definition 7.6.1, Theorem 7.6.1, Definition 7.6.2, Theorem 7.6.2, Theorem 7.10.2, Theorem 7.10.3.
• Chapter 9 — where the spectral radius comes from: the characterizations of an eigenvalue and the algebraic multiplicity, the eigenvalues on the diagonal of a triangular form, and the spectral mapping theorem: Theorem 9.2.1, Definition 9.3.1, Theorem 9.7.4, Theorem 9.10.1.
• Chapter 12 — Schur triangularization with its density corollary, and the defect the Frobenius norm measures: Theorem 12.1.2, Corollary 12.1.6, Theorem 12.11.1, Definition 12.11.1.
• Chapter 13 — the singular value decomposition and the two constructions built on it: Theorem 13.8.1, Definition 13.8.1, Definition 13.11.1.

Roadmap

• Norms. The three axioms, the $1$-, $2$- and $\mathrm{\infty }$-norms with their unit balls drawn, and the test that decides which norms come from an inner product: the parallelogram law. This pays off a promise made in Chapter 11 §01.
• All norms agree. On a finite-dimensional space any two norms are trapped between constant multiples of each other. Compactness enters the book here, and the payoff is that Chapter 10 §10’s entrywise convergence is simply the convergence, whatever norm one prefers.
• Measuring a matrix. Submultiplicativity, and the operator norm $\Vert \mathbf{A}\Vert =max\{\Vert \mathbf{A}\mathbf{x}\Vert :\Vert \mathbf{x}\Vert =1\}$ induced by a vector norm. Its formulas for $p=1,2,\mathrm{\infty }$, including ${\Vert \mathbf{A}\Vert }_2={\sigma }_1(\mathbf{A})$, which is the name Chapter 13 §08 asked for.
• The spectral radius. $\rho (\mathbf{A})\le \Vert \mathbf{A}\Vert$ for every matrix norm, a norm that comes within $\epsilon$ of $\rho (\mathbf{A})$, and Gelfand’s formula $\rho (\mathbf{A})=lim{\Vert {\mathbf{A}}^k\Vert }^{1/k}$.
• Inverting a perturbation of the identity. The Neumann series, the openness of the invertible matrices, and the first perturbation estimate.
• The exponential, with bounds; and derivatives. $\Vert e^{\mathbf{A}}\Vert \le e^{\Vert \mathbf{A}\Vert }$, decay when the spectrum sits in the left half plane, and the derivatives of the determinant and of the inverse.
• Eigenvalues move continuously. Continuously as a multiset, and no better: a Jordan block’s eigenvalues move like ${\epsilon }^{1/k}$.
• How wrong can the answer be? The condition number $\kappa (\mathbf{A})=\Vert \mathbf{A}\Vert \Vert {\mathbf{A}}^{-1}\Vert$, what it predicts about solving $\mathbf{A}\mathbf{x}=\mathbf{b}$, and why the normal equations square it.

Named moves

• Compactness turns “for all unit vectors” into a maximum. A supremum over the unit sphere is hard to control; a maximum is attained at a vector you can name and feed back into the argument. Both the equivalence of norms and the very existence of the operator norm are this one move.
• Ask for submultiplicativity. A matrix is a vector, so a matrix norm is a vector norm; what makes it useful is the extra clause $\Vert \mathbf{A}\mathbf{B}\Vert \le \Vert \mathbf{A}\Vert \Vert \mathbf{B}\Vert$, which is the only reason a bound on $\Vert \mathbf{A}\Vert$ says anything about ${\mathbf{A}}^k$. Test every candidate against it, and expect natural-looking candidates to fail.
• Bound the tail of a series. Neumann, the exponential and Gelfand all reduce to estimating $\sum _{k\ge K}{\Vert \mathbf{A}\Vert }^k$ or $\sum _{k\ge K}{\Vert \mathbf{A}\Vert }^k/k!$ by something that visibly tends to zero.
• Perturb and compare. Replace $\mathbf{A}$ by $\mathbf{A}+\mathbf{E}$, subtract the two conclusions, and read the result as a bound on the relative change in the answer by a constant times the relative change in the data. The constant is the condition number.
• Reduce to the $2$-norm. Equivalence of norms means any single norm may be used as the hub: prove the estimate for the Euclidean norm, where the inner product and the singular value decomposition are available, and transfer.