Week 13: The SVD and Complex Matrices

Take $A = \begin{pmatrix} 2 & 0 & 0 \\ 2 & 2 & 0 \\ 1 & 2 & 2 \end{pmatrix}$. It is triangular, so its eigenvalues are the diagonal: $2$, $2$ and $2$. That reads like "A doubles every length". Feed it the unit vector $v_1 = (2, 2, 1)/3$ and out comes $(4, 8, 8)/3$, of length $4$. Eigenvalues measure stretch only along eigenvectors. Singular values measure it in every direction.

The scene opens at $t = 3$, after all three moves. Slide $t$ back to $0$, then forward. From $0$ to $1$ the sphere turns by $V^T$, and every length stays $1$. From $1$ to $2$, $\Sigma$ stretches it along the axes by $4$, $2$ and $1$. From $2$ to $3$, $U$ turns the ellipsoid into place, and the amber arrow that started as $v_1$ ends as $Av_1 = 4u_1$.

Every matrix turns, stretches and turns#

Week 10 wrote a square matrix as $A = S\Lambda S^{-1}$, but only when it had a full set of independent eigenvectors. This $A$ does not. $A - 2I$ has rank $2$, so the eigenvalue $2$ has a single eigenvector direction, and $A$ cannot be diagonalized.

The SVDSingular Value Decomposition has no such limits. Every real $m \times n$ matrix factors as

with $U$ and $V$ orthogonal and $\Sigma$ an $m \times n$ diagonal matrix of singular values $\sigma_1 \ge \sigma_2 \ge \cdots \ge 0$. Read $Ax = U(\Sigma(V^Tx))$ right to left, as the slider does:

1. $V^T$ is orthogonal, here a rotation. It moves the right singular vectors $v_i$ onto the axes $e_i$ and keeps the sphere a sphere.
2. $\Sigma$ multiplies coordinate $i$ by $\sigma_i$. The sphere becomes an ellipsoid with half-axes $\sigma_i$ along the axes.
3. $U$ rotates that ellipsoid so its axes point along the left singular vectors $u_i$.

So $Av_i = \sigma_i u_i$: each $v_i$ goes to $u_i$, scaled by $\sigma_i$. The longest half-axis $\sigma_1$ is the largest stretch, $\|A\|_2 = \max_{\|x\|=1}\|Ax\|$. For square $A$, the shortest half-axis $\sigma_n$ is the smallest.

Constructing the SVD in the scene's numbers#

Take lengths squared: $\|Ax\|^2 = x^T(A^TA)x$. The Gram matrix

is symmetric and positive semidefinite, so Week 12's spectral theorem applies: $A^TA = V\Lambda V^T$ with orthonormal $v_i$. Its eigenvalues are $16$, $4$ and $1$. Check two invariants. The trace is $9 + 8 + 4 = 21 = 16 + 4 + 1$, and $\det(A^TA) = (\det A)^2 = 64 = 16 \cdot 4 \cdot 1$. Check one eigenvector:

The singular values are the square roots, $\sigma = 4, 2, 1$. The left singular vectors come from $u_i = Av_i/\sigma_i$, so $u_1 = (4, 8, 8)/(3 \cdot 4) = (1, 2, 2)/3$. In general, $AV = U\Sigma$ column by column, and $A^TA = V\Sigma^T\Sigma V^T$. The $u_i$ are also the eigenvectors of $AA^T$.

Singular values are not eigenvalues. The eigenvalues of $A$ are $2, 2, 2$, and the singular values are $4, 2, 1$. Their products agree in absolute value, since both give the volume factor: $|\det A| = 2 \cdot 2 \cdot 2 = 4 \cdot 2 \cdot 1 = 8$. An eigenvector is a direction that $A$ keeps. On the unit sphere, $\|Ax\|$ is largest, smallest or stationary at the singular vectors, and their images are perpendicular. The two notions coincide for a symmetric positive semidefinite matrix, where $U = V = Q$ and $\Sigma = \Lambda$, which is the Week 12 picture.

Rank. The rank is the number of positive $\sigma_i$. Zeroing the smallest ones gives the best low-rank approximation (Eckart–Young), the basis of PCA in Week 14.

Complex matrices#

Over $\mathbb{C}$, each real notion has a counterpart built from the conjugate transpose $A^H = \overline{A}^T$:

• Hermitian, $A^H = A$, is the analogue of symmetric. Its eigenvalues are real, and $A = U\Lambda U^H$.
• Unitary, $U^HU = I$, is the analogue of orthogonal. It keeps lengths: $\|Ux\|^2 = x^HU^HUx = \|x\|^2$.

Every complex $m \times n$ matrix has an SVD $A = U\Sigma V^H$ with unitary $U$ and $V$ and real $\sigma_i \ge 0$. The discrete Fourier matrix, divided by $\sqrt{n}$, is unitary.

Knowledge Check#

Browser lab: the stretch of A between 1 and 4#

Compute the SVD of the scene's matrix and measure $\|Ax\|$ over many unit vectors.

import numpy as np
import matplotlib.pyplot as plt

A = np.array([[2., 0., 0.],
              [2., 2., 0.],
              [1., 2., 2.]])

U, S, Vt = np.linalg.svd(A)
print("singular values =", S.round(6))
print("eigenvalues     =", np.linalg.eigvals(A).real.round(6))
print("A = U Σ Vᵀ:", np.allclose(U @ np.diag(S) @ Vt, A))
for i in range(3):
    v, u = Vt[i], U[:, i]
    print(f"v{i+1} = {np.round(3 * v).astype(int)}/3   A v = {S[i]:.0f} u:", np.allclose(A @ v, S[i] * u))

rng = np.random.default_rng(0)
x = rng.normal(size=(3, 20000))
x /= np.linalg.norm(x, axis=0)
stretch = np.linalg.norm(A @ x, axis=0)
print(f"min ‖Ax‖ = {stretch.min():.3f}, max ‖Ax‖ = {stretch.max():.3f}")

plt.hist(stretch, bins=60)
plt.axvline(S[-1], color="k", linestyle="--")
plt.axvline(S[0], color="k", linestyle="--")
plt.xlabel("‖Ax‖ for unit x")
plt.ylabel("count")
plt.show()

The singular values print as [4. 2. 1.] and the eigenvalues as [2. 2. 2.]. NumPy may flip the sign of a pair $u_i, v_i$ together, so a printed $v_i$ can be the negative of the scene's. The product $Av_i = \sigma_i u_i$ still holds. Every sampled stretch falls between the dashed lines at $\sigma_3 = 1$ and $\sigma_1 = 4$. Try A.T @ A: it is symmetric positive semidefinite, so its singular values equal its eigenvalues.

Key takeaways#

Every matrix factors as $A = U\Sigma V^T$: a rotation, a stretch along the axes, and a second rotation. The singular values are the square roots of the eigenvalues of $A^TA$ and the half-axes of the image of the unit sphere. In general they are not the eigenvalues of $A$: the scene's $A$ has eigenvalues $2, 2, 2$ and stretches unit vectors from $1$ to $4$. The SVD exists even where diagonalization fails.

Further reading#

• Gilbert Strang, Introduction to Linear Algebra (6th ed., Wellesley-Cambridge Press, 2023). Chapter 7 develops the SVD, its geometry, and its connection to principal component analysis.
• Lloyd N. Trefethen & David Bau, Numerical Linear Algebra (SIAM, 1997). Lectures 4–5 derive the SVD and prove the low-rank approximation theorem (Eckart–Young).
• Steven L. Brunton & J. Nathan Kutz, Data-Driven Science and Engineering (Cambridge University Press, 2019). Chapter 1 uses the SVD as the workhorse for data-driven low-rank structure.