Sylvester's Criterion for Positive Definiteness

Sylvester's criterion provides a practical test for positive definiteness using determinants of principal minors, avoiding eigenvalue computation.

TheoremSylvester's Criterion

A real symmetric $n \times n$ matrix $A$ is positive definite if and only if all leading principal minors are positive: $\det(A_1) > 0, \quad \det(A_2) > 0, \quad \ldots, \quad \det(A_n) > 0$

where $A_k$ is the upper-left $k \times k$ submatrix of $A$ .

For positive semi-definiteness, all principal minors (not just leading) must be non-negative.

ExampleTesting Positive Definiteness

Is $A = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}$ positive definite?

Check leading principal minors:

$\det(A_1) = 2 > 0$ ✓
$\det(A_2) = \det\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} = 3 > 0$ ✓
$\det(A_3) = \det(A) = 4 > 0$ ✓

Yes, $A$ is positive definite.

TheoremConsequences of Positive Definiteness

If $A$ is positive definite, then:

All eigenvalues are positive
All diagonal entries $a_{ii} > 0$
$\det(A) > 0$
$A$ is invertible
The quadratic form $Q(\mathbf{x}) = \mathbf{x}^TA\mathbf{x}$ has unique minimum at origin

TheoremCholesky Decomposition

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

This provides an efficient method for solving $A\mathbf{x} = \mathbf{b}$ : solve $L\mathbf{y} = \mathbf{b}$ then $L^T\mathbf{x} = \mathbf{y}$ by forward/back substitution.

Computational cost: $O(n^3/3)$ vs $O(n^3)$ for Gaussian elimination.

ExampleOptimization Application

In optimization, $f(\mathbf{x})$ has local minimum at critical point $\mathbf{x}^*$ if the Hessian $H = \nabla^2 f(\mathbf{x}^*)$ is positive definite.

Sylvester's criterion provides a direct test without computing eigenvalues, crucial for high-dimensional problems.

Remark

Sylvester's criterion is computationally efficient for small matrices but requires $n$ determinant calculations. For large matrices, checking eigenvalue positivity via Cholesky decomposition (which fails for non-PD matrices) is faster. The criterion's theoretical importance lies in connecting determinants (algebraic invariants) to positive definiteness (geometric property).