Chapter 4 Formula Sheet

Reference, not teaching. Each entry names the book’s number, states the result, gives the condition it needs, and names the call that computes it. Read the concept pages first; come back here when you are working.

The one-line summary

Every decomposition in this chapter trades a condition for a capability:

$$\underbrace{\text{SPD}}_{\text{Cholesky}} \;\subset\; \underbrace{\text{symmetric}}_{\mathbf{P}\mathbf{D}\mathbf{P}^\top} \;\subset\; \underbrace{\text{non-defective square}}_{\mathbf{P}\mathbf{D}\mathbf{P}^{-1}} \;\subset\; \underbrace{\text{any matrix at all}}_{\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top}$$

Read it right to left and the SVD is the one with no entry fee. Read it left to right and each step buys something cheaper: Cholesky costs $\tfrac13n^3$ where an SVD costs about $20n^3$.

§4.1 Determinant and trace

#	result	condition	NumPy
Thm 4.1	$\mathbf{A}$ is invertible $\iff \det\mathbf{A} \neq 0$	square	np.linalg.det
Eq 4.5	$2\times2$: $\det = a_{11}a_{22} - a_{12}a_{21}$	—	—
Eq 4.6	Sarrus for $3\times3$: three down-right products minus three down-left	$3\times3$ only	—
Thm 4.2	Laplace expansion along row or column $j$: $\det\mathbf{A} = \sum_k (-1)^{k+j}a_{kj}\det\mathbf{A}_{k,j}$	square	—
Eq 4.8	triangular matrix: $\det\mathbf{A} = \prod_i a_{ii}$	triangular	—
Thm 4.3	$\det(\mathbf{A}\mathbf{B}) = \det\mathbf{A}\det\mathbf{B}$; $\det\mathbf{A}^\top = \det\mathbf{A}$; $\det\mathbf{A}^{-1} = 1/\det\mathbf{A}$; similar matrices share a determinant; row operations, sign rules	square	—
Thm 4.3	$\det\mathbf{A} \neq 0 \iff \mathrm{rk}(\mathbf{A}) = n$	square	np.linalg.matrix_rank
Def 4.4	$\mathrm{tr}(\mathbf{A}) = \sum_i a_{ii}$	square	np.trace
Eq 4.19	$\mathrm{tr}(\mathbf{A}\mathbf{B}) = \mathrm{tr}(\mathbf{B}\mathbf{A})$ — so the trace is cyclic	shapes must compose both ways	—
Eq 4.21	$\mathrm{tr}(\mathbf{x}\mathbf{y}^\top) = \mathbf{y}^\top\mathbf{x}$	—	—
—	trace is invariant under basis change: $\mathrm{tr}(\mathbf{S}^{-1}\mathbf{A}\mathbf{S}) = \mathrm{tr}(\mathbf{A})$	$\mathbf{S}$ invertible	—

The cost warning. Laplace expansion is about $n!$ multiplications; Gaussian elimination is about $n^3/3$. Determinants are a theoretical tool.

§4.2 Eigenvalues and eigenvectors

#	result	condition	NumPy
Def 4.6	$\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$, $\mathbf{x} \neq \mathbf{0}$	square	np.linalg.eig
Thm 4.8	$\lambda$ is an eigenvalue $\iff$ it is a root of $p_\mathbf{A}(\lambda) = \det(\mathbf{A}-\lambda\mathbf{I})$	square	np.roots on the char. poly (don’t)
Def 4.9	algebraic multiplicity: multiplicity as a root of $p_\mathbf{A}$	—	—
Def 4.11	eigenspace $E_\lambda = \ker(\mathbf{A}-\lambda\mathbf{I})$; geometric multiplicity $= \dim E_\lambda$	—	n - matrix_rank(A - lam*I)
—	$1 \leq$ geometric $\leq$ algebraic, always	—	—
Def 4.13	defective: geometric multiplicities sum to less than $n$	square	—
Thm 4.12	eigenvectors for distinct eigenvalues are linearly independent	—	—
Thm 4.14	$\mathbf{A}^\top\mathbf{A}$ is symmetric positive semidefinite; positive definite iff $\mathrm{rk}(\mathbf{A}) = n$	any shape	—
Thm 4.15	spectral theorem: a symmetric matrix has an orthonormal basis of eigenvectors and real eigenvalues	symmetric	np.linalg.eigh
Thm 4.16	$\det\mathbf{A} = \prod_i\lambda_i$, counting algebraic multiplicity	square	—
Thm 4.17	$\mathrm{tr}\,\mathbf{A} = \sum_i\lambda_i$, counting algebraic multiplicity	square	—
Eq 4.23–4.24	for a $2\times2$: $p_\mathbf{A}(\lambda) = \lambda^2 - (\mathrm{tr}\,\mathbf{A})\lambda + \det\mathbf{A}$	$2\times2$	—
—	$\lvert\det\mathbf{A}\rvert$ is the volume scaling; its sign is the orientation	square	—

Use eigh for symmetric input — faster, real, sorted ascending, orthonormal eigenvectors. Never on non-symmetric input: it reads only the lower triangle.

§4.3 Cholesky decomposition

#	result	condition	NumPy
Thm 4.18	$\mathbf{A} = \mathbf{L}\mathbf{L}^\top$ with $\mathbf{L}$ lower triangular and positive diagonal, uniquely	symmetric positive definite	np.linalg.cholesky
Eq 4.44	$\det\mathbf{A} = \prod_i l_{ii}^2$	SPD	—
—	sampling: $\mathbf{x} = \boldsymbol{\mu} + \mathbf{L}\mathbf{z}$ with $\mathbf{z}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$ gives $\mathbf{x}\sim\mathcal{N}(\boldsymbol{\mu},\boldsymbol{\Sigma})$	$\boldsymbol{\Sigma}$ SPD	—
—	cost $\tfrac13n^3$, about half an LU factorisation	SPD	—
—	a raised LinAlgError is the positive-definiteness test	—	try/except

cholesky reads only the lower triangle

np.linalg.cholesky([[2,1],[0,2]]) succeeds on a matrix that is neither symmetric nor positive definite. Check np.allclose(M, M.T) first, or the test proves nothing.

§4.4 Eigendecomposition and diagonalization

#	result	condition	NumPy
Def 4.19	diagonalizable: similar to a diagonal matrix, $\mathbf{D} = \mathbf{P}^{-1}\mathbf{A}\mathbf{P}$	square	—
Eq 4.50	$\mathbf{A}\mathbf{P} = \mathbf{P}\mathbf{D} \iff$ the columns of $\mathbf{P}$ are eigenvectors and $\mathbf{D}$ holds the eigenvalues	—	—
Thm 4.20	$\mathbf{A} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}$ iff the eigenvectors form a basis of $\mathbb{R}^n$	square, non-defective	np.linalg.eig
Thm 4.21	a symmetric matrix can always be diagonalized, and $\mathbf{P}$ can be taken orthogonal so $\mathbf{D} = \mathbf{P}^\top\mathbf{A}\mathbf{P}$	symmetric	np.linalg.eigh
Eq 4.62	$\mathbf{A}^k = \mathbf{P}\mathbf{D}^k\mathbf{P}^{-1}$	diagonalizable	np.linalg.matrix_power
Eq 4.63	$\det\mathbf{A} = \prod_i d_{ii}$	diagonalizable	—
—	geometry: $\mathbf{P}^{-1}$ into the eigenbasis, $\mathbf{D}$ scales, $\mathbf{P}$ back. Rotations only if symmetric	—	—
—	defective matrices need the Jordan normal form — outside this book	—	—

§4.5 Singular value decomposition

#	result	condition	NumPy
Thm 4.22	$\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top$ with $\mathbf{U} \in \mathbb{R}^{m\times m}$, $\mathbf{V} \in \mathbb{R}^{n\times n}$ both orthogonal, $\boldsymbol{\Sigma} \in \mathbb{R}^{m\times n}$ with $\sigma_i \geq 0$ descending	none	np.linalg.svd
Eq 4.65–4.66	$\boldsymbol{\Sigma}$ has the shape of $\mathbf{A}$: zero rows below if $m>n$, zero columns to the right if $m<n$	—	—
Eq 4.73	$\mathbf{A}^\top\mathbf{A} = \mathbf{V}\,\mathrm{diag}(\sigma_i^2)\,\mathbf{V}^\top$ — the eigenvectors of $\mathbf{A}^\top\mathbf{A}$ are $\mathbf{V}$	—	—
Eq 4.76	$\mathbf{A}\mathbf{A}^\top = \mathbf{U}\,\mathrm{diag}(\sigma_i^2)\,\mathbf{U}^\top$ — the eigenvectors of $\mathbf{A}\mathbf{A}^\top$ are $\mathbf{U}$	—	—
Eq 4.78	$\mathbf{u}_i = \mathbf{A}\mathbf{v}_i/\sigma_i$	$\sigma_i \neq 0$	—
Eq 4.79	singular value equation $\mathbf{A}\mathbf{v}_i = \sigma_i\mathbf{u}_i$, $i = 1,\dots,r$	—	—
Eq 4.80	$\mathbf{A}\mathbf{V} = \mathbf{U}\boldsymbol{\Sigma}$	—	—
—	the trailing columns of $\mathbf{V}$ are an orthonormal basis of $\ker\mathbf{A}$	—	Vt[r:].T
Eq 4.89	reduced SVD: $\mathbf{U}$ is $m\times n$, $\boldsymbol{\Sigma}$ is $n\times n$ square	$m \geq n$	full_matrices=False
—	$\prod_i\sigma_i = \lvert\det\mathbf{A}\rvert$ and $\sigma_1 = \lVert\mathbf{A}\rVert_2$	square for the first	—
—	$\sigma_i = \lvert\lambda_i\rvert$ only for symmetric matrices	symmetric	—
—	for symmetric $\mathbf{A}$ the eigendecomposition and the SVD coincide	symmetric	—

Never compute an SVD through a Gram matrix. $\kappa(\mathbf{A}^\top\mathbf{A}) = \kappa(\mathbf{A})^2$; measured, the smallest singular value is $4\%$ wrong at $\kappa = 10^8$ and lost entirely at $10^{12}$.

§4.6 Matrix approximation

#	result	condition	NumPy
Eq 4.90	$\mathbf{A}_i = \mathbf{u}_i\mathbf{v}_i^\top$, a rank-1 outer product	—	np.outer
Eq 4.91	$\mathbf{A} = \sum_{i=1}^r \sigma_i\mathbf{u}_i\mathbf{v}_i^\top$	—	—
Eq 4.92	$\hat{\mathbf{A}}(k) = \sum_{i=1}^k \sigma_i\mathbf{u}_i\mathbf{v}_i^\top$, with $\mathrm{rk}(\hat{\mathbf{A}}(k)) = k$ exactly	$k \leq r$	(U[:,:k]*s[:k]) @ Vt[:k]
Def 4.23	spectral norm $\lVert\mathbf{A}\rVert_2 = \max_\mathbf{x}\lVert\mathbf{A}\mathbf{x}\rVert_2/\lVert\mathbf{x}\rVert_2$	—	np.linalg.norm(A, 2)
Thm 4.24	$\lVert\mathbf{A}\rVert_2 = \sigma_1$	—	—
Thm 4.25	Eckart-Young: $\hat{\mathbf{A}}(k) = \operatorname*{argmin}_{\mathrm{rk}(\mathbf{B})=k}\lVert\mathbf{A}-\mathbf{B}\rVert_2$ and $\lVert\mathbf{A}-\hat{\mathbf{A}}(k)\rVert_2 = \sigma_{k+1}$	—	—
Eq 4.96	$\mathbf{A} - \hat{\mathbf{A}}(k) = \sum_{i=k+1}^r\sigma_i\mathbf{u}_i\mathbf{v}_i^\top$	—	—
—	Frobenius error: $\lVert\mathbf{A}-\hat{\mathbf{A}}(k)\rVert_F = \sqrt{\sum_{i>k}\sigma_i^2}$, also optimal	—	—
—	storage: $k(m+n+1)$ numbers, so it saves only when $k < mn/(m+n+1)$	—	—

§4.7 Matrix phylogeny

class	condition	what it gives you
real, any shape	—	SVD, pseudo-inverse
square	$m = n$	determinant, trace, eigenvalues
regular / invertible	$\det \neq 0$	$\mathbf{A}^{-1}$
non-defective	$n$ independent eigenvectors	$\mathbf{P}\mathbf{D}\mathbf{P}^{-1}$
normal	$\mathbf{A}^\top\mathbf{A} = \mathbf{A}\mathbf{A}^\top$	singular and eigen directions align
orthogonal (Def 3.8)	$\mathbf{A}^\top\mathbf{A} = \mathbf{A}\mathbf{A}^\top = \mathbf{I}$	$\mathbf{A}^{-1} = \mathbf{A}^\top$, free
rotation	orthogonal with $\det = +1$	preserves orientation
symmetric	$\mathbf{S} = \mathbf{S}^\top$	real eigenvalues, orthonormal eigenbasis
positive definite	$\mathbf{x}^\top\mathbf{P}\mathbf{x} > 0$	unique Cholesky, $\lambda > 0$, invertible
diagonal	$a_{ij} = 0$, $i \neq j$	everything elementwise
identity	$\mathbf{A} = \mathbf{I}$	—

Non-singular and non-defective are independent

A rotation matrix is invertible with complex eigenvalues; $\mathrm{diag}(1,0)$ is diagonal and singular. All four combinations occur — Exercise 4.5 gives one $2\times2$ witness each.

Diagonal matrices are closed under multiplication and addition but form a group only when every diagonal entry is nonzero.

Numbers worth remembering

quantity	value	where
Laplace vs elimination at $n = 20$	ratio $1.6\times10^{15}$	§4.1
Cholesky cost	$\tfrac13n^3$, half an LU	§4.3
eigendecomposition cost	about $10n^3$ symmetric	§4.4
SVD cost	about $20n^3$ square	§4.5
$\mathbf{A}^k$ crossover, $n=6$	eigen route wins from $k = 14$	§4.4
defective random $4\times4$ Gaussians	$0$ of $4000$	§4.4
defective small-integer $4\times4$	$2.675\%$	§4.4
$\det$ of np.linalg.qr’s $\mathbf{Q}$	$(-1)^{n-1}$, exactly	§4.7
Eckart-Young agreement over 420 truncations	$6.22\times10^{-15}$	§4.6
random rank-$k$ competitors below the bound	$0$ of $420$	§4.6
Stonehenge rank-5 storage	$16\,715$ of $2\,735\,120$, $0.611\%$	§4.6
Gram route error at $\kappa = 10^{12}$	$100\%$ — the singular value is lost	§4.5

The exercises, in one line each

#	answer
4.1	$0$; $\mathbf{r}_3 = 2\mathbf{r}_1 - \mathbf{r}_2$
4.2	$6$
4.3	(a) defective, $\lambda=1$ geometric $1$; (b) $\lambda = 2, -3$, diagonalizable
4.4	$\lambda = 2, 1, -1$ ($-1$ doubled, geometric $1$) — defective
4.5	all four invertible-by-diagonalizable combinations
4.6	(a) defective $2/3$; (b) diagonalizable $4/4$
4.7	(a) $2\pm2i$, no over $\mathbb{R}$; (b) yes; (c) defective $3/4$; (d) yes
4.8	$\sigma = 5, 3$
4.9	$\sigma = 2\sqrt2, \sqrt2$, with $\mathbf{U} = \mathbf{I}$
4.10	$\tfrac52\begin{bmatrix}1&1&0\\1&1&0\end{bmatrix}$, error $3$
4.11	multiply by $\mathbf{A}$; needs $\lambda \neq 0$ to keep $\mathbf{A}\mathbf{v} \neq \mathbf{0}$
4.12	orthogonal factors preserve length; the max is at $\mathbf{x} = \mathbf{v}_1$

Where each section is used later

from	used in
§4.1 determinant, trace	Ch 5 Jacobians; Ch 6 Gaussian densities carry $\det\boldsymbol{\Sigma}$
§4.2 eigenvalues	Ch 7 the Hessian’s spectrum decides minimum vs saddle; Ch 10 variance along a component
§4.2 spectral theorem	Ch 10 orthogonal principal components; Ch 12 kernel matrices
§4.3 Cholesky	Ch 6 Gaussian sampling and the reparametrisation trick; Ch 11 GMM covariances
§4.4 eigendecomposition	Ch 10 PCA as an eigendecomposition of a covariance matrix
§4.5 SVD	Ch 9 the pseudo-inverse and least squares; Ch 10 PCA by another route
§4.6 Eckart-Young	Ch 10 the reconstruction-error derivation of PCA

The six mistakes this chapter is designed to prevent

1. Computing a determinant by cofactor expansion. $n!$ against $n^3/3$. Use elimination, or Cholesky if the matrix is SPD.
2. Assuming invertible means diagonalizable. Measured, the implication holds $85\%$ one way and $98\%$ the other. Neither is a theorem.
3. Assuming a repeated eigenvalue means defective. Exercise 4.6b has an eigenvalue repeated three times and is perfectly diagonalizable. What matters is $\dim\ker(\mathbf{A}-\lambda\mathbf{I})$.
4. Writing $\mathbf{P}^{-1} = \mathbf{P}^\top$ without checking symmetry. Example 4.5 is diagonalizable with $\lVert\mathbf{P}^\top\mathbf{P}-\mathbf{I}\rVert = 0.3162$.
5. Constructing an SVD through $\mathbf{A}^\top\mathbf{A}$. The condition number squares. The construction is a proof, not an algorithm.
6. Reading individual eigenvector or singular-vector components across a repeated value. Any rotation inside the repeated eigenspace is equally valid, so different builds report different vectors.

pch.quizTag Can you place each result?

1. Which decomposition needs no condition on the matrix at all?

   A Cholesky B The eigendecomposition C The SVD D LU without pivoting
   pch.quizShowAnswer

   C — The SVD — Theorem 4.22 holds for every real matrix of every shape, with rank anywhere from 0 to min(m,n). Cholesky needs symmetric positive definite; the eigendecomposition needs square and non-defective.

2. Theorem 4.24 says the spectral norm equals sigma_1. What makes Equation 4.95 follow almost immediately?

   A Nothing; it needs the full Eckart-Young argument B That A minus A-hat(k) is the tail of the SVD sum, so it is already in SVD form with largest singular value sigma-k-plus-one C That the Frobenius norm equals the spectral norm D That the truncation has rank exactly k
   pch.quizShowAnswer

   B — That A minus A-hat(k) is the tail of the SVD sum, so it is already in SVD form with largest singular value sigma-k-plus-one — Equation 4.96 makes that explicit. The hard half of Theorem 4.25 is optimality, Equation 4.94, which needs the rank-nullity contradiction.

3. Which single result does the rest of the chapter lean on most heavily?

   A Theorem 4.1, det nonzero iff invertible B Theorem 4.15, the spectral theorem: a symmetric matrix has real eigenvalues and an orthonormal eigenbasis C Theorem 4.2, Laplace expansion D Definition 4.4, the trace
   pch.quizShowAnswer

   B — Theorem 4.15, the spectral theorem: a symmetric matrix has real eigenvalues and an orthonormal eigenbasis — It gives Theorem 4.21 for symmetric matrices, it is what makes the SVD construction of §4.5.2 work at all since A-transpose A is always symmetric, and it is why PCA in Chapter 10 gets orthogonal components without asking.

Recall card

• The chapter is a ladder of conditions: Cholesky needs SPD, the eigendecomposition needs square and non-defective, the SVD needs nothing — and the cheaper the decomposition, the stricter the condition.
• Determinant and trace are basis-independent, so they describe the mapping rather than the matrix; both equal a symmetric function of the eigenvalues (product and sum).
• The spectral theorem is the load-bearing result: symmetric implies real eigenvalues and an orthonormal eigenbasis, which is what makes Theorem 4.21, the SVD construction and PCA all work.
• Diagonalizability is about the count of independent eigenvectors, which is the sum of the geometric multiplicities — not about repeats and not about invertibility.
• The SVD’s two outer factors are orthogonal and live in different spaces, so unlike P and P-inverse they are not inverses of each other; Sigma has the shape of A and pads with zeros.
• Eckart-Young gives the error before you compute the approximation: exactly sigma-k-plus-one in the spectral norm, and the square root of the discarded tail in the Frobenius norm.
• Low rank is not few numbers: a rank-k factorisation costs k(m+n+1), so the saving depends on the ratio of k to mn/(m+n+1).
• Three library traps: cholesky and eigh read only the lower triangle; np.linalg.qr returns a Q with determinant exactly (-1) to the (n-1); and eig returns P for a defective matrix without complaint.

Back to: Matrix Decompositions Overview — or on to Chapter 5, Vector Calculus.