Positive Semidefinite Matrices

Why This Matters

Positive semidefiniteness is the matrix analogue of non-negativity for scalars. It appears in three central places in ML:

Covariance matrices are always PSD. If $\Sigma$ is a covariance matrix, then $x^T \Sigma x = \text{Var}(x^T Z) \geq 0$ for any vector $x$.

Hessians of convex functions are PSD. A twice-differentiable function $f$ is convex if and only if $\nabla^2 f(x) \succeq 0$ everywhere. This connects PSD matrices to the theory of convex optimization.

Kernel matrices (Gram matrices) are PSD by construction. The entire theory of kernel methods rests on this fact.

Core Definitions

Definition

Positive Semidefinite Matrix

A symmetric matrix $A \in \mathbb{R}^{n \times n}$ is positive semidefinite (PSD) if:

$x^T A x \geq 0 \quad \text{for all } x \in \mathbb{R}^n$

If the inequality is strict for all $x \neq 0$, the matrix is positive definite (PD), written $A \succ 0$.

Definition

Loewner Ordering

For symmetric matrices $A$ and $B$, the Loewner ordering is:

$A \succeq B \iff A - B \succeq 0 \iff x^T(A - B)x \geq 0 \text{ for all } x$

This is a partial order on symmetric matrices. It is not a total order: most pairs of matrices are incomparable.

Main Theorems

Theorem

PSD Equivalence Theorem

Statement

The following are equivalent for a symmetric matrix $A \in \mathbb{R}^{n \times n}$:

1. $A \succeq 0$ (i.e., $x^T A x \geq 0$ for all $x$)
2. All eigenvalues of $A$ are non-negative
3. $A = B^T B$ for some matrix $B$
4. All principal minors of $A$ are non-negative
5. There exists a lower triangular $L$ with non-negative diagonal such that $A = LL^T$ (Cholesky decomposition, if $A \succ 0$)

Intuition

PSD means the quadratic form $x^T A x$ is a bowl that never dips below zero. Eigenvalues are the curvatures along the principal axes. Non-negative curvature in every direction means non-negative eigenvalues.

Proof Sketch

$(1 \Rightarrow 2)$: If $Av = \lambda v$ with $\|v\| = 1$, then $\lambda = v^T A v \geq 0$. $(2 \Rightarrow 3)$: By the spectral theorem, $A = Q \Lambda Q^T$ where $\Lambda$ has non-negative entries. Set $B = \Lambda^{1/2} Q^T$. $(3 \Rightarrow 1)$: $x^T A x = x^T B^T B x = \|Bx\|^2 \geq 0$.

Why It Matters

Different characterizations are useful in different contexts. Checking eigenvalues is $O(n^3)$. Checking the quadratic form definition is useful for proofs. The factorization $A = B^T B$ is used in sampling from Gaussians: if $Z \sim N(0, I)$ and $\Sigma = LL^T$, then $LZ \sim N(0, \Sigma)$.

Failure Mode

Symmetry is required. A non-symmetric matrix can satisfy $x^T A x \geq 0$ for all $x$ without having real eigenvalues. The standard convention in ML is that PSD refers to symmetric (or Hermitian) matrices only.

Cholesky Decomposition

Every positive definite matrix $A$ has a unique factorization $A = LL^T$ where $L$ is lower triangular with positive diagonal entries. This is the Cholesky decomposition.

Computational cost: $O(n^3/3)$, which is half the cost of a general LU decomposition. It is the preferred method for solving linear systems $Ax = b$ when $A$ is known to be PD: factor once, then solve $Ly = b$ and $L^T x = y$ by back-substitution.

For PSD (not PD) matrices, the Cholesky factorization exists but $L$ may have zeros on the diagonal.

Schur Complement

Definition

Schur Complement

Given a block matrix:

$M = \begin{pmatrix} A & B \\ B^T & C \end{pmatrix}$

where $A$ is invertible, the Schur complement of $A$ in $M$ is:

$S = C - B^T A^{-1} B$

The key fact: if $A \succ 0$, then $M \succeq 0$ if and only if $S \succeq 0$.

The Schur complement appears in conditional distributions: if $(X, Y) \sim N(0, M)$, then the conditional covariance of $Y$ given $X$ is the Schur complement of the $X$-block.

Properties of PSD Matrices

• Sum: if $A \succeq 0$ and $B \succeq 0$, then $A + B \succeq 0$
• Scaling: if $A \succeq 0$ and $\alpha \geq 0$, then $\alpha A \succeq 0$
• Congruence: if $A \succeq 0$, then $BAB^T \succeq 0$ for any matrix $B$
• Trace: if $A \succeq 0$, then $\text{tr}(A) \geq 0$ (sum of eigenvalues)
• Hadamard product: if $A \succeq 0$ and $B \succeq 0$, then $A \circ B \succeq 0$ (Schur product theorem)

The set of PSD matrices forms a convex cone: it is closed under addition and non-negative scalar multiplication.

Common Confusions

Watch Out

PSD is about the symmetric part

For a non-symmetric matrix $M$, the quadratic form $x^T M x = x^T \frac{M + M^T}{2} x$. So the sign of the quadratic form depends only on the symmetric part $(M + M^T)/2$. When someone says "the Hessian is PSD," this is only meaningful because Hessians of twice-differentiable functions are symmetric.

Watch Out

Positive entries do not imply PSD

The matrix $\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$ has all positive entries but eigenvalues $3$ and $-1$, so it is not PSD. Conversely, the identity matrix is PSD despite having zeros off the diagonal.

Exercises

ExerciseCore

Problem

Prove that every covariance matrix is PSD. That is, if $\Sigma = \mathbb{E}[(X - \mu)(X - \mu)^T]$, show $\Sigma \succeq 0$.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Let $A \succ 0$ be $n \times n$ positive definite. Prove that $A^{-1} \succ 0$.

Hint

Reveal Solution

References

Canonical:

• Horn & Johnson, Matrix Analysis (2013), Chapter 7
• Strang, Linear Algebra and Its Applications (2006), Section 6.5
• Bhatia, Positive Definite Matrices (2007), Chapters 1-2 (characterizations and Loewner ordering)

Current:

• Boyd & Vandenberghe, Convex Optimization (2004), Section 2.3 (PSD cone)
• Golub & Van Loan, Matrix Computations (2013), Chapter 4 (Cholesky decomposition)
• Deisenroth, Faisal, Ong, Mathematics for Machine Learning (2020), Section 4.3 (positive definite matrices and Cholesky)