Positive Matrices and the Singular Value Decomposition

A matrix that is not square has no eigenvalues. There is no equation $\mathbf{A}\mathbf{v}=\lambda \mathbf{v}$ to write down, because $\mathbf{A}\mathbf{v}$ and $\mathbf{v}$ live in different spaces, and everything Chapters 9 to 12 built on that equation is unavailable. Yet the geometric picture that opened Chapter 12 survives untouched: push the unit sphere of $F^n$ through any $\mathbf{A}\in M_{m\times n}(F)$, square or not, and what comes out is an ellipsoid. It has semi-axes, they are perpendicular, and the directions they came from were perpendicular too. Reading that picture as a factorization gives $\mathbf{A}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^{\ast }$, the singular value decomposition: every matrix whatsoever maps some orthonormal basis to an orthogonal set. It is the most used factorization in applied linear algebra, and this chapter’s business is to earn it and then spend it.

The road runs through positivity. A nonsquare $\mathbf{A}$ has no eigenvalues, but ${\mathbf{A}}^{\ast }\mathbf{A}$ does, and ${\mathbf{A}}^{\ast }\mathbf{A}$ is self-adjoint with a nonnegative quadratic form — it is a positive semidefinite matrix, the analogue of a nonnegative number. Chapter 12 left that class unexamined; here it comes first, with its many equivalent tests, its square root, and the triangular factorization that elimination finds. From the square root comes the absolute value $|\mathbf{A}|$, from $|\mathbf{A}|$ the polar decomposition $\mathbf{A}=\mathbf{W}|\mathbf{A}|$, and from the spectral theorem applied to ${\mathbf{A}}^{\ast }\mathbf{A}$ the singular value decomposition itself. Once it is in hand, a series of questions that look unrelated turn out to have one answer: what are orthonormal bases of the four fundamental subspaces, what is the best rank-$k$ approximation of a matrix, what should ${\mathbf{A}}^{-1}$ mean when $\mathbf{A}$ is not invertible, and when is a projection orthogonal. The field is $\mathbb{R}$ or $\mathbb{C}$ throughout, as in Chapters 11 and 12, and every statement says which one it needs.

What you need. From Chapter 12, the two spectral theorems and their matrix forms (Theorem 12.4.2, Corollary 12.4.3, Theorem 12.5.1, Corollary 12.5.2, Corollary 12.5.4, Theorem 12.5.5), the elementary theory of self-adjoint operators (Theorem 12.2.1, Theorem 12.2.3, Theorem 12.2.6, Exercise (C1: The operator $S^{\ast }S$)), commuting families (Corollary 12.7.2, Corollary 12.7.3), and the functional calculus with its square root (Definition 12.8.1, Theorem 12.8.1, Theorem 12.8.3, Theorem 12.8.4). From Chapter 12 §10, the Sylvester equation and the Lyapunov equation it specializes to (Theorem 12.10.2, Definition 12.10.2), used in §06. From Chapter 9, the eigenvalue form of the Invertible Matrix Theorem, which §§01 and 06 use to turn a positivity question into a statement about the spectrum (Theorem 9.2.6), and the trace and determinant as sum and product of the eigenvalues (Theorem 9.3.3). From Chapter 11, the Frobenius norm and its unitary invariance (Lemma 11.7.5), the adjoint and what it does to the four subspaces (Definition 11.6.1, Theorem 11.6.2, Theorem 11.6.3, Theorem 11.6.5, Corollary 11.6.6), orthogonal decompositions and projections (Theorem 11.3.2, Definition 11.3.2, Theorem 11.3.3, Theorem 11.3.5), least squares (Theorem 11.4.2, Corollary 11.4.4, Theorem 11.4.5, Lemma 11.4.3), Gram matrices (Definition 11.2.3, Theorem 11.2.5), isometries (Definition 11.7.1, Theorem 11.7.3, Definition 11.7.2), and the QR factorization (Theorem 11.8.1). From Chapter 8, block multiplication and Schur complements (Theorem 8.1.1, Definition 8.3.1, Theorem 8.3.1, Theorem 8.3.2, Theorem 8.3.3, Theorem 8.3.4). From Chapter 7, multiplicativity of the determinant, triangular determinants, and the nonnegativity of Gram determinants (Theorem 7.5.4, Theorem 7.4.6, Corollary 7.7.3). From Chapter 6, Lagrange interpolation (Theorem 6.6.1). From Chapter 4, projections along a complement (Definition 4.5.1, Theorem 4.5.1). From Chapter 3, the $\mathbf{L}\mathbf{D}{\mathbf{L}}^{\mathrm{\top }}$ factorization and the invertible matrix theorem it started (Theorem 3.6.8, Theorem 3.4.4). From Chapter 1, one fact, in §13: a subspace of the same finite dimension as a space containing it is the whole of it (Theorem 1.6.8).

Roadmap

• Positive semidefinite and positive definite matrices. The definition, the real-versus-complex asymmetry that trips everyone, and the full list of equivalent tests, ending in Sylvester’s criterion and the trap that comes with it.
• The square root and Cholesky. The unique positive square root, why it is a polynomial in the matrix, the absolute value $|\mathbf{A}|$, and the factorization $\mathbf{A}=\mathbf{L}{\mathbf{L}}^{\ast }$ whose algorithm is itself the test for definiteness.
• Gram matrices. A matrix is a Gram matrix exactly when it is positive semidefinite; the Gram determinant as a squared volume, and distance to a subspace computed two ways.
• Two forms at once. A positive definite form and a self-adjoint one can be diagonalized simultaneously — by congruence, not by similarity — and the generalized eigenvalue problem $\mathbf{B}\mathbf{x}=\lambda \mathbf{A}\mathbf{x}$ follows.
• The Loewner order. What $\mathbf{A}⪰\mathbf{B}$ means, what monotonicity survives it (traces, determinants, inverses), and the chapter’s negative result: squaring does not.
• Blocks and Schur complements. Testing a block matrix for positive definiteness one block at a time, and the positive definite solution of the Lyapunov equation, which the same test delivers: a certificate of stability that computes no eigenvalue.
• Determinant inequalities. What the same block decomposition says about the size of a determinant: Fischer’s inequality for two diagonal blocks, and Hadamard’s for the diagonal entries and for the lengths of the columns.
• Products entry by entry. The Schur product theorem — the Hadamard product of positive matrices is positive — and Oppenheim’s inequality.
• The singular value decomposition. Every matrix is $\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^{\ast }$; the singular values are determined, the unitaries are not, and the compact form reads off orthonormal bases of all four fundamental subspaces.
• Polar decomposition and Takagi. $\mathbf{A}=\mathbf{W}|\mathbf{A}|$ is $z=e^{i\theta }r$ for matrices; $\mathbf{W}$ is the nearest unitary matrix to $\mathbf{A}$; and a complex symmetric matrix factors as $\mathbf{U}\mathbf{\Sigma }{\mathbf{U}}^{\mathrm{\top }}$.
• Low-rank approximation. Truncating the singular value sum gives the best approximation of each rank, in the Frobenius norm, with an error one can write down.
• The pseudoinverse. Inverting the nonzero singular values defines ${\mathbf{A}}^{+}$; it is pinned down by four conditions, and ${\mathbf{A}}^{+}\mathbf{b}$ is the minimum-norm least-squares solution promised in Chapter 11.
• Projections revisited. An idempotent is an orthogonal projection exactly when it is self-adjoint; everything else is oblique, and the obliqueness is a measurable angle.

Named moves

• Test with $⟨\mathbf{A}\mathbf{x},\mathbf{x}⟩$. Positivity is a statement about one scalar function of one vector. Most proofs in the first half of the chapter consist of evaluating that function at a cleverly chosen $\mathbf{x}$ — a standard basis vector, a vector supported on a few coordinates, an eigenvector, or $\mathbf{S}\mathbf{y}$ for a substitution $\mathbf{S}$.
• Factor as ${\mathbf{B}}^{\ast }\mathbf{B}$. Every positive semidefinite matrix is one, and that form turns a statement about the matrix into a statement about lengths: $⟨{\mathbf{B}}^{\ast }\mathbf{B}\mathbf{x},\mathbf{x}⟩={\Vert \mathbf{B}\mathbf{x}\Vert }^2$. It is also what makes every positive semidefinite matrix a Gram matrix.
• Diagonalize, do it to the eigenvalues, come back. The square root, the pseudoinverse, and the whole functional calculus are this one move. The work is always in checking that the result does not depend on the diagonalization chosen.
• Apply the spectral theorem to ${\mathbf{A}}^{\ast }\mathbf{A}$. When the matrix in front of you is not square, not normal, or not even an operator, this is the way in. The singular value decomposition is nothing but the spectral theorem for ${\mathbf{A}}^{\ast }\mathbf{A}$, read back through $\mathbf{A}$.
• Truncate the sum. Writing $\mathbf{A}=\sum _i{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{\ast }$ turns a matrix into a sum of rank-one pieces ordered by importance. Cutting the sum short gives the compact form, the best low-rank approximation, and the pseudoinverse, three times from one idea.