Positive (semi-)definite matrices

Summary

A symmetric matrix $A \in R^{n \times n}$ is positive semi-definite (PSD) if $x^{⊤} A x \geq 0$ for all $x \in R^{n}$ , and positive definite (PD) if $x^{⊤} A x > 0$ for all $x \neq = 0$ . Equivalently: all eigenvalues are non-negative (PSD) or strictly positive (PD).

PSD matrices are the matrices that can serve as covariance matrices, kernel matrices (Gram matrices), inner-product weight matrices, and Hessians at local minima. The PSD cone is the natural domain for many optimization problems (semidefinite programming, Gaussian processes, kernel methods).

Equivalent characterizations

For symmetric $A$ :

$x^{⊤} A x \geq 0$ for all $x$ (definition).
All eigenvalues $λ_{i} \geq 0$ .
$A = B^{⊤} B$ for some matrix $B$ (factorization, e.g., Cholesky $B = L^{⊤}$ with $L$ lower triangular).
$A$ is the covariance matrix of some random vector.
All principal minors are non-negative. For PD matrices, Sylvester’s criterion gives the simpler equivalent test that every leading (upper-left) principal minor is positive.

For PD: replace non-negative eigenvalues and quadratic forms with strictly positive ones, and require $B$ to be invertible in the factorization.

The Cholesky factorization

Every PD matrix has a unique decomposition $A = L L^{⊤}$ with $L$ lower triangular and positive diagonal. This is the standard way to:

Solve $A x = b$ when $A$ is PD ( $O (n^{3} /3)$ instead of $O (n^{3})$ for general LU).
Sample from a Gaussian: if $z \sim N (0, I)$ then $L z \sim N (0, A)$ .
Compute Gaussian log-likelihoods: $lo g det A = 2 \sum_{i} lo g L_{ii}$ .

PSD (not strictly PD) matrices admit Cholesky-like decompositions but with possible zero diagonal entries; use pivoted Cholesky or LDL.

The PSD cone

The set of $n \times n$ PSD matrices forms a convex cone (closed under non-negative combinations). This is why semidefinite programming generalizes linear programming. It optimizes over a different cone.

Operations preserving PSD:

$A + B$ is PSD if $A, B$ are PSD.
$c A$ is PSD for $c \geq 0$ .
$B^{⊤} A B$ is PSD for any compatible $B$ .
Element-wise (Hadamard) product (Schur product theorem).

Operations not preserving PSD:

General matrix product $A B$ (only if $A, B$ commute).
Inverse: PD matrices have PD inverses; PSD with zero eigenvalue is not invertible.

Geometric intuition

For $A$ PD, the set ${x : x^{⊤} A x \leq 1}$ is a closed ellipsoid centered at the origin. Eigenvectors of $A$ give the axes; eigenvalues give $1/ axis-length^{2}$ . If $A$ is PSD but singular, a zero eigenvalue leaves its eigenvector direction unpenalized, so the same sublevel set is an unbounded cylinder (a strip in 2D), not a flat ellipsoid. A singular covariance distribution is instead supported on a lower-dimensional subspace; that is the setting in which its probability contours collapse.

Learning objective

Predict whether a quadratic sublevel set is bounded by checking whether every eigenvalue penalizes its eigenvector direction.

Read it this way: diagonalize first, then inspect one eigendirection at a time. In the top panel, moving along either axis increases the quadratic form, so the threshold closes into an ellipse. In the bottom panel, moving along v adds nothing because its eigenvalue is zero; only u is bounded, and the strip continues forever.

Original coordinate construction checked against MIT OpenCourseWare 18.06 and Boyd and Vandenberghe's Convex Optimization.

Common pitfalls

Calling a non-symmetric matrix PSD. PSD is defined for symmetric matrices. For asymmetric $A$ , the relevant object is $\frac{1}{2} (A + A^{⊤})$ .
Trusting numerical eigenvalues at machine precision. A theoretically PSD covariance computed from data can have tiny negative eigenvalues from rounding. Use jitter ( $A + ε I$ ) before Cholesky.
Confusing PSD with diagonally dominant. Diagonally dominant with positive diagonal $\Rightarrow$ PSD, but the converse is false.
Inverting near-singular PSD matrices. Always check the smallest eigenvalue or condition number first; regularize if needed.