Positive Definite Matrices

What is a Positive Definite Matrix?

A symmetric real $n \times n$ matrix $A$ is Positive Definite if the quadratic form:

x^T A x > 0 for all non-zero vectors x in R^n

If $x^T A x \ge 0$, the matrix is Positive Semi-Definite (PSD).

Intuition: A positive definite matrix acts like a positive number in matrix arithmetic. It never flips a vector into an opposing hemisphere ($x \cdot A x > 0$).

Four Equivalent Test Conditions

The following test conditions are 100% equivalent for a symmetric matrix A:

1. Quadratic Form: $x^T A x > 0$ for all non-zero $x$.
2. Eigenvalues: All eigenvalues are strictly positive ($\lambda_1, \lambda_2, \dots, \lambda_n > 0$).
3. Cholesky Factorization: $A$ can be uniquely factored as $A = L L^T$ where $L$ is lower triangular with positive diagonal elements.
4. Leading Principal Minors: All top-left sub-determinants are strictly positive (Sylvester's Criterion).

Why Positive Definiteness Matters in Machine Learning

1. Strict Convexity & Uniqueness: Quadratic loss function $f(w) = \frac{1}{2} w^T A w - b^T w$ has a Positive Definite matrix $A$ if and only if the loss surface forms a strictly convex bowl with a single unique global minimum.

2. Hessian Test for Minima: At a stationary point where $\nabla f(x^) = 0$: If Hessian $\nabla^2 f(x^)$ is Positive Definite -> Strict Local Minimum. If Hessian is Negative Definite -> Local Maximum. If Hessian has Both positive and negative eigenvalues -> Saddle Point.

3. Covariance Matrices: Sample covariance matrix $\Sigma = \frac{1}{N} X^T X$ is always Positive Semi-Definite. If features are linearly independent, $\Sigma$ is strictly Positive Definite.

4. SVM Kernel Trick: Mercer's Condition requires kernel matrices to be Positive Semi-Definite, guaranteeing convex optimization in Support Vector Machines.

Say this out loud

A symmetric matrix is Positive Definite if x^T A x > 0 for all non-zero vectors x, meaning all its eigenvalues are strictly positive. In machine learning, a positive definite matrix represents a strictly convex bowl-shaped loss surface with a single global minimum. Covariance matrices and valid SVM kernel matrices are always positive semi-definite.

Follow-ups to expect

• What is the difference between Positive Definite and Positive Semi-Definite? Positive Definite requires x^T A x > 0 (all eigenvalues > 0). Positive Semi-Definite allows x^T A x >= 0 (eigenvalues >= 0, meaning some eigenvalues can be 0).
• How do you turn a Positive Semi-Definite matrix into a strictly Positive Definite matrix? Add a small positive diagonal regularization term: A_new = A + epsilon * I. This shifts all eigenvalues up by epsilon, forcing them strictly > 0.