Positive Definite Matrices

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. Definitions and Quadratic Forms
6. Equivalent Characterizations
7. The Cholesky Decomposition
8. The PSD Cone and Partial Order
9. Connection to Convexity
10. Covariance Matrices and Uncertainty
11. Kernel Matrices and Mercer's Theorem
12. Regularization and Ridge Regression
13. The Schur Complement
14. Common Pitfalls and Misconceptions
15. Research Perspective
16. Summary of Takeaways
17. Exercises

Learning Objectives

After reading this chapter, you should be able to:

1. Define positive definite (PD) and positive semidefinite (PSD) matrices via quadratic forms.
2. Prove equivalence of the five standard characterizations (quadratic form, eigenvalues, Sylvester, Cholesky, inverse).
3. Derive the Cholesky decomposition constructively and explain its role in Gaussian sampling.
4. Connect PSD Hessians to convexity of twice-differentiable functions.
5. Prove that covariance and kernel Gram matrices are PSD.
6. Apply the Schur complement to conditional covariances and block matrix inversion.

Prerequisites

• Eigenvalues & Eigenvectors: spectral theorem, Rayleigh quotient.
• Matrix Operations & Linear Transformations: symmetric matrices, determinants.

Notation

• $\mathbf{A} \succ 0$ — Symmetric positive definite matrix
• $\mathbf{A} \succeq 0$ — Symmetric positive semidefinite
• $\lambda_{\min}(\mathbf{A}), \lambda_{\max}(\mathbf{A})$ — Extreme eigenvalues
• $\kappa(\mathbf{A})$ — Condition number $\lambda_{\max}/\lambda_{\min}$
• $\mathbf{x}^T \mathbf{A} \mathbf{x}$ — Quadratic form

Core Intuition

A symmetric matrix $\mathbf{A}$ defines a quadratic form $q(\mathbf{x}) = \mathbf{x}^T \mathbf{A}\mathbf{x}$ — a generalization of the squared norm $\|\mathbf{x}\|^2 = \mathbf{x}^T \mathbf{I}\mathbf{x}$. When $\mathbf{A} \succ 0$ (positive definite), this form behaves like a true "squared length" in a curved geometry: it is always positive except at the origin, defines ellipsoidal level sets, and supports taking square roots (Cholesky).

PSD matrices appear wherever we need valid geometries for uncertainty (covariance), convex optimization landscapes (Hessians), or valid similarity measures (kernels). Adding $\lambda \mathbf{I}$ to a PSD matrix makes it PD — the mathematical basis for Ridge regularization.

Series context. This completes Chapter 1 (Linear Algebra) of Volume I. Next: Gradient Descent in Chapter 2 (Calculus & Optimization).

Definitions and Quadratic Forms

Definition 1 (Quadratic Form). For symmetric $\mathbf{A} \in \mathbb{R}^{n \times n}$, the function $q: \mathbb{R}^n \to \mathbb{R}$ given by

is a quadratic form.

Definition 2 (Positive Definite). $\mathbf{A}$ is positive definite, written $\mathbf{A} \succ 0$, if

Definition 3 (Positive Semidefinite). $\mathbf{A}$ is positive semidefinite, written $\mathbf{A} \succeq 0$, if

Definition 4 (Negative Definite / Indefinite). $\mathbf{A} \prec 0$ if $-\mathbf{A} \succ 0$. $\mathbf{A}$ is indefinite if it is neither PSD nor NSD — i.e., it has both positive and negative eigenvalues.

Example 1. $\mathbf{I}_n \succ 0$ since $\mathbf{x}^T \mathbf{I}\mathbf{x} = \|\mathbf{x}\|^2 > 0$ for $\mathbf{x} \neq \mathbf{0}$.

Example 2. $\mathbf{A} = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$ is PSD but not PD: $\mathbf{x}^T \mathbf{A}\mathbf{x} = (x_1 + x_2)^2 \geq 0$, with equality for $\mathbf{x} = (1, -1)^T$.

Equivalent Characterizations

Theorem 1. For symmetric $\mathbf{A} \in \mathbb{R}^{n \times n}$, the following are equivalent:

1. $\mathbf{A} \succ 0$
2. All eigenvalues satisfy $\lambda_i > 0$
3. All leading principal minors are positive (Sylvester's criterion)
4. There exists invertible lower triangular $\mathbf{L}$ with $\mathbf{A} = \mathbf{L}\mathbf{L}^T$ (Cholesky)
5. $\mathbf{A}$ is invertible and $\mathbf{A}^{-1} \succ 0$

Proof of (1) $\Leftrightarrow$ (2). By the spectral theorem, $\mathbf{A} = \mathbf{Q}\boldsymbol{\Lambda}\mathbf{Q}^T$ with $\mathbf{Q}$ orthogonal. Let $\mathbf{y} = \mathbf{Q}^T\mathbf{x}$:

This is positive for all $\mathbf{y} \neq \mathbf{0}$ iff all $\lambda_i > 0$. $\blacksquare$

Proof of (2) $\Rightarrow$ (4). Constructive Cholesky (Section below) produces $\mathbf{L}$ with positive diagonal when all leading minors are positive. $\blacksquare$

Proof of (4) $\Rightarrow$ (1). If $\mathbf{A} = \mathbf{L}\mathbf{L}^T$ with $\mathbf{L}$ invertible, then for $\mathbf{x} \neq \mathbf{0}$: $\mathbf{x}^T\mathbf{A}\mathbf{x} = \|\mathbf{L}^T\mathbf{x}\|^2 > 0$. $\blacksquare$

Proof of (1) $\Leftrightarrow$ (5). If $\mathbf{A} \succ 0$, eigenvalues of $\mathbf{A}^{-1}$ are $1/\lambda_i > 0$, so $\mathbf{A}^{-1} \succ 0$. Conversely, if $\mathbf{A}^{-1} \succ 0$, then $\mathbf{A} = (\mathbf{A}^{-1})^{-1} \succ 0$. $\blacksquare$

Important equation. Equation (4) diagonalizes the quadratic form in the eigenbasis. Level sets $\{\mathbf{x} : \mathbf{x}^T\mathbf{A}\mathbf{x} = c\}$ are ellipsoids with axis lengths $1/\sqrt{\lambda_i}$.

Theorem 2 (PSD characterizations). For symmetric $\mathbf{A}$, the following are equivalent:

1. $\mathbf{A} \succeq 0$
2. All eigenvalues satisfy $\lambda_i \geq 0$
3. $\mathbf{A} = \mathbf{B}^T\mathbf{B}$ for some $\mathbf{B}$ (existence of square root)

The Cholesky Decomposition

Theorem 3 (Cholesky). Every PD matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$ admits a unique factorization $\mathbf{A} = \mathbf{L}\mathbf{L}^T$ where $\mathbf{L}$ is lower triangular with positive diagonal entries.

Constructive algorithm (2×2 case). Let $\mathbf{A} = \begin{bmatrix} a & b \\ b & c \end{bmatrix}$ with $a > 0$ and $ac - b^2 > 0$. Seek $\mathbf{L} = \begin{bmatrix} l_{11} & 0 \\ l_{21} & l_{22} \end{bmatrix}$:

Matching entries:

Positivity of $l_{22}$ requires $ac > b^2$ — the PD condition via Sylvester.

General algorithm. For $i = 1, \ldots, n$:

Complexity. $O(n^3/3)$ — half the cost of general LU or inversion.

Application: Gaussian sampling. If $\boldsymbol{\epsilon} \sim \mathcal{N}(\mathbf{0}, \mathbf{I})$, then $\mathbf{x} = \boldsymbol{\mu} + \mathbf{L}\boldsymbol{\epsilon} \sim \mathcal{N}(\boldsymbol{\mu}, \mathbf{L}\mathbf{L}^T)$. This reparameterization enables gradient-based learning of covariance structure in variational inference.

The PSD Cone and Partial Order

Definition 5. The set $\mathbb{S}^n_+ = \{\mathbf{A} \in \mathbb{R}^{n \times n} : \mathbf{A} = \mathbf{A}^T, \mathbf{A} \succeq 0\}$ is a convex cone.

Proposition 1. If $\mathbf{A} \succeq 0$ and $\mathbf{B} \succeq 0$, then for any $\alpha, \beta \geq 0$:

Proof. $\mathbf{x}^T(\alpha\mathbf{A} + \beta\mathbf{B})\mathbf{x} = \alpha\mathbf{x}^T\mathbf{A}\mathbf{x} + \beta\mathbf{x}^T\mathbf{B}\mathbf{x} \geq 0$. $\blacksquare$

We write $\mathbf{A} \succeq \mathbf{B}$ iff $\mathbf{A} - \mathbf{B} \succeq 0$. This defines a partial order on symmetric matrices (Loewner order).

Proposition 2. If $\mathbf{A} \succeq 0$ and $\lambda > 0$, then $\mathbf{A} + \lambda \mathbf{I} \succ 0$.

This is the mathematical basis for regularization: perturbing a PSD matrix by a positive multiple of the identity makes it PD.

Connection to Convexity

Theorem 4 (Second-order convexity condition). A twice-differentiable function $f: \mathbb{R}^n \to \mathbb{R}$ is convex if and only if

Proof ($\Rightarrow$). Convexity implies $f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y} - \mathbf{x})$. Applying to $\mathbf{y} = \mathbf{x} + t\mathbf{v}$ and taking the second derivative at $t = 0$ gives $\mathbf{v}^T \nabla^2 f(\mathbf{x}) \mathbf{v} \geq 0$.

Proof ($\Leftarrow$). Taylor's theorem: for some $\mathbf{z}$ on the segment between $\mathbf{x}$ and $\mathbf{y}$,

If $\nabla^2 f \succeq 0$, the quadratic term is nonnegative, giving first-order convexity. $\blacksquare$

Corollary 4. At a local minimum $\mathbf{x}^*$, $\nabla^2 f(\mathbf{x}^*) \succeq 0$. If $\nabla^2 f(\mathbf{x}^*) \succ 0$, the minimum is strict.

ML interpretation. Hessian eigenvalues are curvatures. Negative eigenvalues indicate saddle points. The condition number of the Hessian at a minimum governs local optimization difficulty — connecting to Eigenvalues & Eigenvectors and Gradient Descent.

Covariance Matrices and Uncertainty

Definition 6 (Covariance). For random vector $\mathbf{x}$ with mean $\boldsymbol{\mu}$:

Theorem 5. Every covariance matrix is PSD.

Proof. For any $\mathbf{v} \in \mathbb{R}^n$:

Interpretation. $\boldsymbol{\Sigma}$ is PSD but may be singular. $\text{rank}(\boldsymbol{\Sigma}) = r < n$ means the random vector lies in an $r$-dimensional affine subspace — there are $n - r$ directions of zero variance.

Sample covariance. For data $\mathbf{x}_1, \ldots, \mathbf{x}_N$:

(centered $\mathbf{X}$). This is PSD by construction ($\hat{\boldsymbol{\Sigma}} = \mathbf{B}^T\mathbf{B}$ with $\mathbf{B} = \mathbf{X}/\sqrt{N-1}$).

Multivariate Gaussian. $\mathbf{x} \sim \mathcal{N}(\boldsymbol{\mu}, \boldsymbol{\Sigma})$ requires $\boldsymbol{\Sigma} \succ 0$ for a valid density:

The quadratic form in the exponent uses $\boldsymbol{\Sigma}^{-1} \succ 0$ when $\boldsymbol{\Sigma} \succ 0$.

Kernel Matrices and Mercer's Theorem

Definition 7 (Kernel). A function $K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ is a valid kernel if for any finite set $\{x_1, \ldots, x_N\}$, the Gram matrix $K_{ij} = K(x_i, x_j)$ is PSD.

Theorem 6 (Mercer's Theorem — statement). A continuous symmetric kernel on a compact domain is valid if and only if it admits an expansion

where $\{\phi_i\}$ are orthonormal eigenfunctions.

Consequence. Valid kernels define inner products in feature spaces (possibly infinite-dimensional). Kernel ridge regression, SVMs, and Gaussian processes all require PSD Gram matrices.

Example 3 (RBF kernel). $K(x, x') = \exp(-\gamma\|x - x'\|^2)$ is PSD for all $\gamma > 0$.

Regularization and Ridge Regression

Problem. Least squares with $\mathbf{X}^T\mathbf{X}$ singular or ill-conditioned.

Ridge solution:

Theorem 7. If $\mathbf{X}^T\mathbf{X} \succeq 0$ and $\lambda > 0$, then $\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I} \succ 0$.

Proof. For $\mathbf{v} \neq \mathbf{0}$: $\mathbf{v}^T(\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})\mathbf{v} = \mathbf{v}^T\mathbf{X}^T\mathbf{X}\mathbf{v} + \lambda\|\mathbf{v}\|^2 \geq \lambda\|\mathbf{v}\|^2 > 0$. $\blacksquare$

Bayesian interpretation. Ridge regression corresponds to MAP estimation with Gaussian prior $\mathbf{w} \sim \mathcal{N}(\mathbf{0}, \sigma_p^2 \mathbf{I})$, developed in Bayesian Linear Regression.

Effect on spectrum. If $\mathbf{X}^T\mathbf{X}$ has eigenvalues $\mu_i$, then the regularized matrix has eigenvalues $\mu_i + \lambda$, improving condition number from $\mu_{\max}/\mu_{\min}$ to $(\mu_{\max}+\lambda)/(\mu_{\min}+\lambda)$.

The Schur Complement

Definition 8. For block matrix

the Schur complement of block $\mathbf{C}$ is

Theorem 8. If $\mathbf{C} \succ 0$, then $\mathbf{M} \succ 0$ if and only if $\mathbf{M}/\mathbf{C} \succ 0$.

Application: Conditional covariance. For joint Gaussian $\begin{bmatrix} \mathbf{x}_a \\ \mathbf{x}_b \end{bmatrix} \sim \mathcal{N}(\boldsymbol{\mu}, \boldsymbol{\Sigma})$ with

the conditional distribution $\mathbf{x}_a | \mathbf{x}_b$ has covariance

Theorem 9. $\boldsymbol{\Sigma}_{a|b} \preceq \boldsymbol{\Sigma}_{aa}$ (conditioning reduces or preserves uncertainty).

Proof. By Theorem 8 applied to PSD $\boldsymbol{\Sigma}$, the Schur complement is PSD. $\blacksquare$

The Schur complement also appears in the Woodbury matrix identity and Gaussian process predictive variance.

Common Pitfalls and Misconceptions

Pitfall 1: Checking only diagonal entries for PD. All diagonal entries positive is necessary but not sufficient (except for diagonal matrices). Use eigenvalues or Cholesky.

Pitfall 2: Confusing PSD with PD. Covariance matrices are often singular (PSD but not PD) when data lies in a lower-dimensional subspace.

Pitfall 3: Assuming Hessian PD at all critical points. Saddle points have indefinite Hessians (both positive and negative eigenvalues).

Pitfall 4: Using Cholesky on near-singular matrices. When $\mathbf{A}$ is nearly PSD, Cholesky may fail numerically. Add jitter: $\mathbf{A} + \epsilon \mathbf{I}$.

Pitfall 5: Treating kernel PD as optional. An invalid (non-PSD) Gram matrix breaks the interpretation as an inner product and can cause negative "variances" in GP predictions.

Research Perspective

The study of quadratic forms and definiteness connects to Hilbert's work on invariant theory and the development of convex analysis in the twentieth century. Loewner (1934) introduced the matrix partial order $\succeq$.

In machine learning, PD matrices underpin:

• Gaussian processes (Rasmussen & Williams, 2006): kernel matrices must be PSD
• Natural gradient (Amari, 1998): uses the Fisher information matrix (PSD)
• Second-order optimization (Newton, L-BFGS): requires or approximates PD curvature
• Diffusion models (Volume III): noise covariances and score matching Hessians

Recent work on sharpness and flat minima analyzes the Hessian spectrum at solutions, connecting PD geometry to generalization.

Summary of Takeaways

• Quadratic form — $\mathbf{x}^T\mathbf{A}\mathbf{x}$ — $\mathbf{A} \succ 0$ — Valid norm geometry
• Spectrum — Eigenvalues $\lambda_i$ — $\lambda_i > 0$ — Ellipsoid axis lengths
• Cholesky — $\mathbf{A} = \mathbf{L}\mathbf{L}^T$ — $\mathbf{L}$ invertible — Sampling, solving
• Convexity — Hessian $\nabla^2 f$ — $\succeq 0$ — Global/local min structure
• Statistics — Covariance $\boldsymbol{\Sigma}$ — $\succeq 0$ — Valid uncertainty
• Regularization — $\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I}$ — $\succ 0$ — Invertibility
• Kernels — Gram matrix $\mathbf{K}$ — $\succeq 0$ — Valid similarity
• Conditioning — Schur complement — $\preceq$ block — Reduced uncertainty

Next article: Gradient Descent → — Chapter 2: optimization from first-order Taylor expansions.

Exercises

Exercise 1. Determine whether $\mathbf{A} = \begin{bmatrix} 2 & 3 \\ 3 & 5 \end{bmatrix}$ is PD using (a) eigenvalues, (b) Sylvester's criterion, (c) Cholesky.

Exercise 2. Prove that if $\mathbf{A} \succ 0$, then $\log\det(\mathbf{A}) > -\infty$ and $\det(\mathbf{A}) > 0$.

Exercise 3. Show that the function $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T\mathbf{A}\mathbf{x} - \mathbf{b}^T\mathbf{x}$ with $\mathbf{A} \succ 0$ is strictly convex and find its unique minimizer.

Exercise 4 (Covariance). For $\mathbf{x} = (X_1, X_2)^T$ with $X_2 = X_1 + \epsilon$, $\epsilon \perp X_1$, compute $\boldsymbol{\Sigma}$ and show $\det(\boldsymbol{\Sigma}) = 0$.

Exercise 5 (Ridge). If $\mathbf{X}^T\mathbf{X}$ has eigenvalues $(100, 10, 0.1)$, compute eigenvalues of $\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I}$ for $\lambda = 1$ and compare condition numbers.

Exercise 6 (Schur complement). For $\boldsymbol{\Sigma}$ as in (19) with invertible $\boldsymbol{\Sigma}_{bb}$, derive (20) by completing the square in the joint Gaussian density.

Exercise 7 (Conceptual). Explain why the reparameterization $\mathbf{x} = \boldsymbol{\mu} + \mathbf{L}\boldsymbol{\epsilon}$ with $\boldsymbol{\epsilon} \sim \mathcal{N}(\mathbf{0}, \mathbf{I})$ requires $\mathbf{L}\mathbf{L}^T = \boldsymbol{\Sigma}$ to be PD, not merely PSD, for a proper density over all of $\mathbb{R}^n$.

Appendix: The Matrix Square Root

Definition 9 (Matrix Square Root). For PSD $\mathbf{A} \succeq 0$, the unique PSD matrix $\mathbf{A}^{1/2}$ satisfying $(\mathbf{A}^{1/2})^2 = \mathbf{A}$ is given by the spectral theorem:

Theorem 10. If $\mathbf{A} = \mathbf{B}^T\mathbf{B}$, then $\mathbf{A}^{1/2}$ exists and can be computed via SVD of $\mathbf{B}$.

Proof. From $\mathbf{B} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$, we have $\mathbf{A} = \mathbf{V}\boldsymbol{\Sigma}^2\mathbf{V}^T$, so $\mathbf{A}^{1/2} = \mathbf{V}\boldsymbol{\Sigma}\mathbf{V}^T$. $\blacksquare$

Application: Whitening. Given data with covariance $\boldsymbol{\Sigma}$, the transformation $\mathbf{z} = \boldsymbol{\Sigma}^{-1/2}(\mathbf{x} - \boldsymbol{\mu})$ produces unit-variance, uncorrelated coordinates. Whitening is a standard preprocessing step before algorithms sensitive to scale (e.g., k-means, some clustering methods).

Application: Distance in Mahalanobis metric. The quadratic form $(\mathbf{x}-\boldsymbol{\mu})^T\boldsymbol{\Sigma}^{-1}(\mathbf{x}-\boldsymbol{\mu})$ defines a distance that accounts for correlation structure — equivalent to Euclidean distance after whitening.