Week 13: The SVD and Complex Matrices

Why We Need the SVD#

Week 10 diagonalized a square matrix as $A = S\Lambda S^{-1}$ when $A$ had a full set of independent eigenvectors. Week 12 upgraded that story for symmetric $A$: eigenvalues are real and $S$ can be chosen orthogonal, so $A = Q\Lambda Q^T$. Both tools are powerful — and both are picky about the matrix they accept.

Eigendecomposition requires $A$ to be square and diagonalizable. Many matrices that show up in data and geometry fail one or both tests:

• A data matrix of $m$ samples and $n$ features is $m \times n$, often with $m \neq n$ — eigenvalues are not even defined.
• A square but defective matrix (not enough independent eigenvectors) cannot be written $S\Lambda S^{-1}$.
• Even when diagonalization exists, the eigenvector matrix $S$ need not be orthogonal, so the change of basis can stretch and shear rather than pure rotate.

The SVDSingular Value Decomposition (singular value decomposition) removes those restrictions. For every real $m \times n$ matrix $A$ — square or rectangular, full rank or rank-deficient — there exist orthogonal matrices $U$ and $V$ and a rectangular “diagonal” matrix $\Sigma$ of nonnegative numbers such that

No eigenvalue computation on $A$ itself is required. The construction uses only the spectral theorem on the symmetric Gram matrices $A^TA$ and $AA^T$, which always work. That is why the SVD is the workhorse factorization of applied linear algebra: least squares, low-rank approximation, PCA, and pseudoinverses all build on it. PCA and representation learning pick it up directly in Generative Models Week 11: Representation Learning with Generative Models, and covariance structure through the SVD appears in Probability & Statistics Week 6: Multivariate Gaussians.

Constructing the SVD#

Start from any real $m \times n$ matrix $A$. Form the Gram matrix

This matrix is always symmetric ($(A^TA)^T = A^TA$) and positive semidefinite ($x^T(A^TA)x = \|Ax\|^2 \ge 0$). By the spectral theorem from Week 12 it has an orthonormal basis of eigenvectors $v_1,\ldots,v_n$ and nonnegative eigenvalues $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n \ge 0$:

The singular values of $A$ are the square roots of those eigenvalues:

Conventionally we order them $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r > 0$ (where $r = \operatorname{rank}(A)$), and pack them into an $m \times n$ rectangular diagonal matrix $\Sigma$: $\sigma_i$ in the diagonal entries, zeros everywhere else.

The columns of $V$ are the right singular vectors. The left singular vectors $u_i$ come from applying $A$ and normalizing. For each positive singular value,

(Equivalently, the $u_i$ are orthonormal eigenvectors of the other Gram matrix $AA^T$.) Extend $\{u_1,\ldots,u_r\}$ to a full orthonormal basis of $\mathbb{R}^m$ if $r < m$, and pack the result into the orthogonal matrix $U$. The defining identity is then

Why it works. Multiplying $A = U\Sigma V^T$ on the right by $V$ gives $AV = U\Sigma$. Column $i$ of that equation is exactly $Av_i = \sigma_i u_i$. Multiplying $A = U\Sigma V^T$ on the left by $A^T$ recovers $A^TA = V\Sigma^T\Sigma V^T$, so the squared singular values are the eigenvalues of $A^TA$ — consistent by construction.

Worked sketch. Let

Then

The trace of $A^TA$ is $50$, so $\sigma_1^2 + \sigma_2^2 = 50$. The eigenvalues of $A^TA$ are $\lambda = 45$ and $\lambda = 5$ (solve $\det(A^TA - \lambda I) = (25-\lambda)^2 - 400 = 0$), hence singular values $\sigma_1 = \sqrt{45} = 3\sqrt{5}$ and $\sigma_2 = \sqrt{5}$. The browser lab below recovers $U$, $\Sigma$, and $V^T$ numerically and checks that the product reconstructs $A$.

Connection to rank. The number of positive singular values equals $\operatorname{rank}(A)$. Zero singular values mark the nullspace directions: $Av_i = 0$ when $\sigma_i = 0$. Truncating small singular values (setting them to zero) produces the best low-rank approximation of $A$ in the Frobenius and spectral norms — the Eckart–Young theorem (Eckart & Young, 1936), which Week 14 uses for PCA.

Geometric Picture#

The factorization $A = U\Sigma V^T$ is a composition of three simple maps. For a vector $x \in \mathbb{R}^n$,

Read right to left:

1. $V^T$ — an orthogonal change of coordinates in the input space (a rotation or reflection). The new coordinates are the components of $x$ along the right singular vectors.
2. $\Sigma$ — axis-aligned stretching (and possible zeroing). Coordinate $i$ is multiplied by $\sigma_i$; if $m \neq n$, some coordinates are padded with zeros or dropped so the dimensions match.
3. $U$ — an orthogonal change of coordinates in the output space: reassemble the stretched components along the left singular vectors.

So every linear map $\mathbb{R}^n \to \mathbb{R}^m$ is a rotation, followed by stretch along the coordinate axes, followed by another rotation. That is strictly stronger than diagonalization: the orthonormal bases on the two sides — $V$ in $\mathbb{R}^n$, $U$ in $\mathbb{R}^m$ — need not even live in the same dimension.

Unit circle picture. Map the unit circle $\|x\| = 1$ through $A$. Because $V^T$ preserves lengths, $V^Tx$ still traces the unit circle. $\Sigma$ turns that circle into an axis-aligned ellipse with half-axes $\sigma_1,\sigma_2,\ldots$. $U$ then rotates (or reflects) the ellipse into its final orientation. The longest stretch of the ellipse is $\sigma_1 = \|A\|_2$, the operator (spectral) norm of $A$.

$A = U\Sigma V^T$ in three steps: $V^T$ rotates the unit circle (lengths unchanged), $\Sigma$ stretches it along the coordinate axes into an axis-aligned ellipse, and $U$ rotates that ellipse into its final orientation.

When $A$ is symmetric and positive semidefinite. The eigenvalues are already nonnegative, so the SVD and the spectral theorem coincide exactly: $U = V = Q$ and $\Sigma = \Lambda$, so $A = Q\Lambda Q^T$. For a symmetric $A$ that is not PSD, the singular values are the absolute values of the eigenvalues (from $A^TA = Q\Lambda^2Q^T$) and the sign ambiguity is absorbed by $U$ and $V$. The SVD is the generalization that keeps working after symmetry and squareness are dropped.

Complex Matrices#

Many applications — Fourier analysis, quantum states, circuit phasors, and next week's discrete Fourier transform — live over $\mathbb{C}$ rather than $\mathbb{R}$. The real notions of transpose, symmetry, and orthogonality each have a complex counterpart built from the conjugate transpose

(also written $A^*$). Conjugate every entry, then transpose. For real matrices, conjugation does nothing, so $A^H = A^T$ and the two stories agree.

Hermitian matrices. A square complex matrix $A$ is Hermitian when

This is the complex analogue of symmetry. Diagonal entries of a Hermitian matrix must be real ($a_{ii} = \overline{a_{ii}}$), and off-diagonal pairs satisfy $a_{ji} = \overline{a_{ij}}$. The spectral theorem upgrades cleanly: every Hermitian matrix has real eigenvalues and an orthonormal basis of eigenvectors with respect to the complex inner product $\langle x, y \rangle = y^H x$. In matrix form

with $U$ unitary (defined next) and $\Lambda$ real diagonal.

Unitary matrices. A square complex matrix $U$ is unitary when

(equivalently $U^{-1} = U^H$, or $UU^H = I$). This is the complex analogue of an orthogonal matrix's $Q^TQ = I$. Unitary maps preserve the complex Euclidean norm: $\|Ux\|^2 = x^H U^H U x = x^H x = \|x\|^2$ for every $x$. Columns of a unitary matrix form an orthonormal basis of $\mathbb{C}^n$.

SVD over $\mathbb{C}$. The same construction works with conjugate transposes: every complex $m \times n$ matrix factors as $A = U\Sigma V^H$ with unitary $U$, $V$ and real nonnegative singular values on $\Sigma$. The squared singular values are the eigenvalues of the Hermitian positive-semidefinite matrix $A^HA$.

Why this matters next week. The discrete Fourier matrix is unitary up to the standard $1/\sqrt{n}$ normalization — the $n$-th roots of unity sum to zero, so distinct rows are orthogonal. PCA is built directly on the SVD of a data matrix. Both rely on the geometry you just met: orthogonal (or unitary) changes of basis that expose axis-aligned stretches.

Knowledge check#

Browser lab: SVD reconstruction#

Compute the SVD with numpy.linalg.svd and verify it reconstructs A.

import numpy as np

A = np.array([[3., 0.],
              [4., 5.]])

U, S, Vt = np.linalg.svd(A)

print("U =\n", U)
print("singular values =", S)
print("V^T =\n", Vt)

A_reconstructed = U @ np.diag(S) @ Vt
print("Reconstructed A ≈ original:", np.allclose(A_reconstructed, A))

print("Notice: singular values are [6.708, 2.236] and 'Reconstructed A ≈ original: True'.")

np.linalg.svd returns the factors in “thin” or “full” form depending on options; the default full form for a square $A$ gives orthogonal $U$ and $V^T$ with S as a 1-D array of singular values in descending order. Rebuilding $\Sigma = \operatorname{diag}(S)$ and multiplying $U\Sigma V^T$ recovers $A$ up to floating-point roundoff — the check np.allclose should print True. You can also verify $\sigma_1^2 + \sigma_2^2 \approx 50$, matching the trace identity from the knowledge check.

Done when#

You can write the SVD $A=U\Sigma V^\top$, compute singular values as $\sqrt{\lambda_i(A^\top A)}$, and explain how the SVD extends eigendecomposition to non-square and complex matrices. Check it against the browser lab: for $A=\begin{pmatrix}3&0\\4&5\end{pmatrix}$ the singular values are 6.708 and 2.236, Reconstructed A ≈ original: True, and $\sigma_1^2+\sigma_2^2 = 50$ equals the trace of $A^\top A$.

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.