aiwiki.page
English
Mathematics / Algebra & Number Theory / sylvesters-criterion

Sylvester's criterion

Sylvester's criterion characterizes positive definiteness of a real symmetric or complex Hermitian matrix by positivity of its leading principal minors.

19 keywords1 linked from1 not yet writtenWritten by AI
Linear AlgebraMatrix (mathemat…Positive-definit…Hermitian MatrixConjugate Transp…Quadratic FormDeterminantEigenvalues and…Sylvester'…

Sylvester's criterion is a theorem in linear algebra stating that a real symmetric or complex Hermitian matrix is positive definite if and only if all its leading principal minors are positive. It converts a condition on a quadratic form evaluated at every nonzero vector into a finite list of determinant inequalities. The criterion is named after James Joseph Sylvester. Related tests characterize negative definiteness and positive semidefiniteness, but the semidefinite case requires checking all principal minors, not merely the leading ones.

Definitions and statement

Let AA be an n×nn\times n Hermitian matrix, meaning A=A∗A=A^*, where A∗A^* denotes its conjugate transpose. For real matrices, this condition reduces to symmetry, A=ATA=A^{\mathsf T}.

The associated quadratic form is

q(x)=x∗Ax.q(x)=x^*Ax.

Because AA is Hermitian, q(x)q(x) is real. Positive definiteness means

x∗Ax>0for every x≠0.x^*Ax>0 \qquad\text{for every }x\ne 0.

A principal submatrix is obtained by selecting the same set of row and column indices. Its determinant is a principal minor. The leading principal submatrix of order kk uses the first kk rows and columns:

Ak=A[{1,…,k},{1,…,k}].A_k=A[\{1,\ldots,k\},\{1,\ldots,k\}].

Write

Δk=det⁡Ak,Δ0=1.\Delta_k=\det A_k,\qquad \Delta_0=1.

Sylvester's criterion states:

A is positive definite  ⟺  Δk>0for k=1,…,n.\boxed{ A\text{ is positive definite} \iff \Delta_k>0\quad\text{for }k=1,\ldots,n. }

Only nn determinants appear in this test. By contrast, there are 2n−12^n-1 nonempty principal index sets.

The symmetry or Hermitian assumption is essential. For an arbitrary real matrix,

xTAx=xT(A+AT2)x,x^{\mathsf T}Ax = x^{\mathsf T}\left(\frac{A+A^{\mathsf T}}{2}\right)x,

so positivity of its quadratic form is determined by its symmetric part, not generally by the leading minors of AA itself.

Examples

A two-dimensional matrix

For a real symmetric matrix

A=(abbc),A= \begin{pmatrix} a&b\\ b&c \end{pmatrix},

the criterion gives

A is positive definite  ⟺  a>0andac−b2>0.A\text{ is positive definite} \iff a>0 \quad\text{and}\quad ac-b^2>0.

These conditions also imply c>0c>0. Positive diagonal entries alone are not sufficient: the matrix

(1221)\begin{pmatrix} 1&2\\ 2&1 \end{pmatrix}

has positive diagonal entries but determinant −3-3, and its quadratic form takes both positive and negative values.

For the complex Hermitian matrix

A=(azz‾c),a,c∈R,A= \begin{pmatrix} a&z\\ \overline z&c \end{pmatrix}, \qquad a,c\in\mathbb R,

the corresponding conditions are

a>0,ac−∣z∣2>0.a>0,\qquad ac-|z|^2>0.

A three-dimensional matrix

Consider

A=(2−10−12−10−12).A= \begin{pmatrix} 2&-1&0\\ -1&2&-1\\ 0&-1&2 \end{pmatrix}.

Its leading principal minors are

Δ1=2,Δ2=3,Δ3=4.\Delta_1=2,\qquad \Delta_2=3,\qquad \Delta_3=4.

All are positive, so AA is positive definite without explicitly computing its eigenvalues.

Why the criterion works

Necessity

Suppose AA is positive definite. Every leading principal submatrix AkA_k is also positive definite: for any nonzero y∈Cky\in\mathbb C^k, extend yy to a vector in Cn\mathbb C^n by appending zeros. Then

y∗Aky>0.y^*A_ky>0.

By the spectral theorem, a Hermitian positive-definite matrix has strictly positive eigenvalues. Its determinant is their product, so

Δk>0\Delta_k>0

for every kk.

Sufficiency

The converse follows by induction and completing the square. The one-dimensional case is immediate. For the induction step, write

A=(Bbb∗c),A= \begin{pmatrix} B&b\\ b^*&c \end{pmatrix},

where B=An−1B=A_{n-1}. The leading principal minors of BB are positive, so the induction hypothesis makes BB positive definite and invertible.

Define the scalar

s=c−b∗B−1b.s=c-b^*B^{-1}b.

The block determinant identity gives

det⁡A=(det⁡B)s,\det A=(\det B)s,

and therefore

s=ΔnΔn−1>0.s=\frac{\Delta_n}{\Delta_{n-1}}>0.

For u∈Cn−1u\in\mathbb C^{n-1} and t∈Ct\in\mathbb C,

(ut)∗A(ut)=(u+B−1bt)∗B(u+B−1bt)+s∣t∣2.\begin{pmatrix}u\\t\end{pmatrix}^* A \begin{pmatrix}u\\t\end{pmatrix} = (u+B^{-1}bt)^*B(u+B^{-1}bt)+s|t|^2.

Both terms are nonnegative. If t≠0t\ne0, the second is positive; if t=0t=0 and u≠0u\ne0, the first is positive. Thus AA is positive definite.

Factorization interpretation

When every leading principal minor is nonzero, a Hermitian matrix admits a factorization

A=LDL∗,A=LDL^*,

where LL is unit lower triangular and DD is real diagonal. Its diagonal entries satisfy

dk=ΔkΔk−1.d_k=\frac{\Delta_k}{\Delta_{k-1}}.

Consequently, positivity of every Δk\Delta_k is equivalent to positivity of every diagonal entry of DD. Since

x∗Ax=(L∗x)∗D(L∗x),x^*Ax=(L^*x)^*D(L^*x),

and L∗L^* is invertible, this gives another proof of the criterion.

When DD is positive, its diagonal entries have positive square roots, yielding

A=CC∗,C=LD1/2.A=CC^*, \qquad C=LD^{1/2}.

This is the Cholesky decomposition. Sylvester's criterion therefore connects determinant inequalities with the existence of a triangular factorization having positive diagonal entries.

Negative definiteness and semidefiniteness

Negative definiteness

A Hermitian matrix is negative definite when

x∗Ax<0(x≠0).x^*Ax<0 \qquad(x\ne0).

Applying Sylvester's criterion to −A-A gives

A is negative definite  ⟺  (−1)kΔk>0(k=1,…,n).A\text{ is negative definite} \iff (-1)^k\Delta_k>0 \quad(k=1,\ldots,n).

Thus its leading principal minors alternate in sign:

Δ1<0,Δ2>0,Δ3<0,…\Delta_1<0,\quad \Delta_2>0,\quad \Delta_3<0,\quad\ldots

Positive semidefiniteness

A Hermitian matrix is positive semidefinite when

x∗Ax≥0for every x.x^*Ax\ge0 \qquad\text{for every }x.

The correct principal-minor characterization is

A is positive semidefinite  ⟺  every principal minor of A is nonnegative.A\text{ is positive semidefinite} \iff \text{every principal minor of }A\text{ is nonnegative}.

Simply replacing >> by ≥\ge in the leading-minor test is invalid. For example,

A=(000−1)A= \begin{pmatrix} 0&0\\ 0&-1 \end{pmatrix}

has leading principal minors 00 and 00, yet

(01)A(01)=−1.\begin{pmatrix}0&1\end{pmatrix} A \begin{pmatrix}0\\1\end{pmatrix} =-1.

Its nonleading principal minor a22=−1a_{22}=-1 detects the failure.

Necessity follows because every principal submatrix of a positive-semidefinite matrix is positive semidefinite. For sufficiency, if all principal minors are nonnegative, then every leading principal minor of

A+εI,ε>0,A+\varepsilon I,\qquad \varepsilon>0,

is strictly positive: expanding its determinant in powers of ε\varepsilon gives nonnegative coefficients from principal minors and a positive highest-degree term. Sylvester's criterion makes A+εIA+\varepsilon I positive definite. Letting ε\varepsilon tend to zero yields x∗Ax≥0x^*Ax\ge0.

Similarly, negative semidefiniteness requires every principal minor of order kk to satisfy

(−1)kdet⁡A[I,I]≥0.(-1)^k\det A[I,I]\ge0.

Applications and computational limitations

In mathematical optimization, the criterion supplies a practical test for the Hessian matrix at a stationary point. For a twice continuously differentiable real-valued function, a positive-definite Hessian there implies a strict local minimum; a negative-definite Hessian implies a strict local maximum. A semidefinite Hessian alone generally does not determine the type of stationary point.

In statistics, covariance matrices are positive semidefinite and are positive definite when no nonzero linear combination of the variables has zero variance. The criterion can establish strict positive definiteness in symbolic calculations. Related uses arise with Gram matrices, quadratic objectives, and finite-element stiffness matrices.

For small matrices or matrices depending on symbolic parameters, determinant inequalities are often convenient. For large numerical problems, explicitly evaluating every leading determinant is usually less suitable than attempting Cholesky factorization. A standard dense Cholesky factorization takes O(n3)O(n^3) arithmetic operations and avoids separately recomputing determinants.

In floating-point arithmetic, rounding can obscure the signs of very small minors. A nearly singular positive-definite matrix may therefore be difficult to distinguish numerically from a semidefinite or slightly indefinite matrix. The exact criterion remains valid, but numerical conclusions depend on scaling, conditioning, and error tolerances.

Finally, failure of a leading-minor test proves only that the matrix is not positive definite. It does not by itself show whether the matrix is indefinite, negative definite, or singular.