Positive Definite Matrices: Convexity Guarantees

What is Positive Definite?

A symmetric matrix A is positive definite if for every nonzero vector x the quadratic form x^{T}Ax > 0 Intuitively, this means the matrix always "curves upward" and has a unique minimum at the origin.

Positive definite matrices are the "well behaved" matrices in optimization. They guarantee that gradient descent will find a unique global minimum. They appear everywhere: covariance matrices, Hessians of convex functions, and kernel matrices.

The Core Property

x^{T}Ax > 0 for all x \neq 0 This single condition has profound consequences for optimization, statistics, and numerical stability.

The Quadratic Form

The expression x^{T}Ax is called the quadratic form associated with A For a 2×2 symmetric matrix, it expands to:

x^{T}\begin{bmatrix} a & b \\ b & c \end{bmatrix}x = ax_{1}^{2} + 2bx_{1}x_{2} + cx_{2}^{2}xT[ab​bc​]x=ax12​+2bx1​x2​+cx22​

This is a paraboloid in 3D. Its shape depends on the matrix entries.

Positive Definite

Bowl shape. Unique minimum at origin. All level curves are ellipses.

Indefinite

Saddle shape. Neither max nor min at origin. Level curves are hyperbolas.

Negative Definite

Inverted bowl. Unique maximum at origin. All level curves are ellipses.

Interactive Visualization

Adjust the symmetric matrix entries and watch the level curve of the quadratic form change. The arrows show gradient directions. Notice how positive definite matrices create elliptical level curves that all point inward.

Energy Surface

Plotting z = xᵀAx in 3D

Auto-rotating view

Shape Control

λ₁ (Curvature 1)1.0

λ₂ (Curvature 2)0.5

Rotation (Principal Axes)0°

Positive Definite

Bowl shape (Convex). Unique global minimum.

Tests for Definiteness

There are several equivalent ways to check if a symmetric matrix is positive definite:

1. Eigenvalue Test: All eigenvalues are strictly positive.
2. Sylvester's Criterion: All leading principal minors (upper-left determinants) are positive.
3. Cholesky Test: The Cholesky decomposition A = LL^{T} exists with positive diagonal entries.
4. Pivot Test: In LU decomposition, all pivots are positive.

For 2×2

A = \begin{bmatrix} a & b \\ b & c \end{bmatrix}A=[ab​bc​] is PD if $ > 0$a>0 and $ - b^{2} > 0$ac−b2>0.

Computational

In practice, attempt Cholesky factorization. If it succeeds, the matrix is PD.

Cholesky Decomposition

A positive definite matrix A can be uniquely factored as A = LL^{T} where L is a lower triangular matrix with positive diagonal entries. This is the "square root" of a matrix.

A = LL^{T}

L is lower triangular, L^{T} is the transpose (upper triangular)

Why Cholesky?

• Speed: 2× faster than LU because we exploit symmetry.
• Stability: No pivoting needed (guaranteed stable for PD).
• Sampling: To sample from \mathcal{N}(0,\Sigma) compute L from \Sigma = LL^{T} then x = Lz where z \sim \mathcal{N}(0,I)

The Definiteness Spectrum

The classification of a symmetric matrix depends on the signs of its eigenvalues:

ML Applications

Covariance Matrices

Sample covariance matrices are always positive semidefinite. In Gaussians, we need PD covariance for the density to be well defined.

Convex Optimization

A function is convex if its Hessian is PSD everywhere. This guarantees gradient descent converges to the global minimum.

Kernel Matrices

A valid kernel function must produce PSD Gram matrices. This is Mercer's condition, ensuring the implicit feature space is well defined.

Gaussian Processes

GP priors require PD covariance matrices for sampling. Cholesky is used to generate correlated samples from a GP posterior.