the singular value decomposition
The singular value decomposition is, by wide agreement, the single most useful factorization in all of numerical linear algebra. It says that ANY matrix A — square or rectangular, full or rank-deficient, symmetric or not — can be written as A = U Sigma V^T, where U and V are orthogonal matrices and Sigma is diagonal with non-negative entries. In plain geometric terms: every linear map, no matter how messy it looks, is really just a rotation, followed by a stretch along perpendicular axes, followed by another rotation. The SVD finds those axes and stretch factors.
Unpack the pieces. The columns of V (the right singular vectors) are a special orthonormal set of input directions; the columns of U (the left singular vectors) are a matching orthonormal set of output directions; and the diagonal entries of Sigma, the singular values sigma_1 >= sigma_2 >= ... >= 0, are how much A stretches each input direction into its output direction. Read as an action: A v_i = sigma_i u_i — A sends the i-th right singular vector to sigma_i times the i-th left singular vector. The SVD is intimately tied to the symmetric eigenproblem: A^T A = V Sigma^2 V^T, so the right singular vectors are eigenvectors of A^T A and the singular values are the square roots of its eigenvalues; likewise A A^T = U Sigma^2 U^T. This is why the SVD always exists and the singular values are always real and non-negative, even when A has no eigenvalues worth speaking of.
It is computed NOT by forming A^T A (that would square the condition number and lose accuracy) but by Golub-Kahan bidiagonalization followed by an implicit symmetric-QR-like sweep. The reach of the SVD is vast: it reveals the numerical rank (count the singular values above the noise level), gives the best low-rank approximation (Eckart-Young), defines the Moore-Penrose pseudoinverse for least-squares, computes the 2-norm (sigma_1) and condition number (sigma_1/sigma_n) of a matrix, and is the engine behind PCA, latent semantic analysis, image compression, recommender systems, and model order reduction. If you learn one matrix factorization deeply, learn this one.
Take the 2x2 matrix A with rows (1, 0) and (0, 0) — it projects onto the x-axis. Its SVD has sigma_1 = 1, sigma_2 = 0; the right singular vectors are (1,0) and (0,1), the left singular vectors likewise. The single nonzero singular value tells you the matrix has rank 1: it maps the whole plane onto a line. A near-singular matrix would have a tiny but nonzero sigma_2, and the ratio sigma_1/sigma_2 is its condition number — small singular values flag near-rank-deficiency.
Every matrix is a rotation, an axis-aligned stretch by the singular values, then another rotation: A = U Sigma V^T.
Do NOT compute the SVD by forming A^T A and eigendecomposing it: squaring the matrix squares its condition number, so tiny singular values are computed with half the digits or lost entirely. Good SVD software (LAPACK) uses bidiagonalization that works on A directly. Also, the SVD always exists, but the singular vectors are only unique up to sign and (for repeated singular values) rotation within a subspace.