3 Sylvester’s Criterion
Sylvester’s criterion provides an operational test for deciding whether a real symmetric matrix is positive definite.
Theorem 3.1 (Sylvester’s Criterion) Let \bm{A}\in\mathbb{R}^{n\times n} be symmetric, and let
\bm{A}_k := \bm{A}_{1:k,1:k}, \qquad k=1,\ldots,n,
be its leading principal submatrices. Then
\boxed{ \bm{A}\succ 0 \quad\Longleftrightarrow\quad \det(\bm{A}_k)>0,\qquad k=1,\ldots,n. }
In other words, a real symmetric matrix is positive definite if and only if all its leading principal minors are strictly positive.
Negative Definite Matrices
For completeness, applying Sylvester’s criterion to -\bm{A} gives the corresponding test for negative definiteness:
\boxed{ \bm{A}\prec0 \quad\Longleftrightarrow\quad (-1)^k\det(\bm{A}_k)>0, \qquad k=1,\ldots,n. }
Equivalently, the leading principal minors alternate in sign:
\det(\bm{A}_1)<0, \quad \det(\bm{A}_2)>0, \quad \det(\bm{A}_3)<0, \quad\ldots
3.1 Why use Sylvester’s criterion
For an equality-constrained minimization problem, let
\bm{A} := \nabla_{\bm{x}}^2\mathcal{L}(\bm{x}^\star,\bm{\lambda}^\star)
and
\bm{B} := D\bm{h}(\bm{x}^\star).
The second-order necessary condition requires
\bm{z}^\top\bm{A}\bm{z}\ge0 \qquad \forall\bm{z}\in\ker(\bm{B}).
The second-order sufficient condition requires the stronger inequality
\bm{z}^\top\bm{A}\bm{z}>0 \qquad \forall\bm{z}\in\ker(\bm{B})\setminus\{\bm{0}\}.
Let
p:=\dim\ker(\bm{B})=n-\operatorname{rank}(\bm{B}),
and let the columns of
\bm{K}\in\mathbb{R}^{n\times p}
form a basis of \ker(\bm{B}). Then every vector in the tangent space can be written uniquely as
\bm{z}=\bm{K}\bm{\alpha}, \qquad \bm{\alpha}\in\mathbb{R}^p.
Therefore
\bm{z}^\top\bm{A}\bm{z} = \bm{\alpha}^\top\bm{K}^\top\bm{A}\bm{K}\bm{\alpha}.
Define the reduced Hessian
\boxed{ \bm{C}:=\bm{K}^\top\bm{A}\bm{K}\in\mathbb{R}^{p\times p}. }
The definiteness of \bm C does not depend on the particular basis \bm K chosen for the tangent space. If \widetilde{K}=KR with R nonsingular, then \widetilde K^TA\widetilde K=R^T(K^TAK)R, so Sylvester’s law of inertia preserves the numbers of positive, negative, and zero eigenvalues. For numerical work, an orthonormal basis K (for example from a QR or SVD factorization) is usually preferable.
Then
\bm{z}^\top\bm{A}\bm{z}\ge0 \quad\forall\bm{z}\in\ker(\bm{B})
is equivalent to
\bm{C}\succeq0,
while
\bm{z}^\top\bm{A}\bm{z}>0 \quad\forall\bm{z}\in\ker(\bm{B})\setminus\{\bm{0}\}
is equivalent to
\bm{C}\succ0.
If the constraints satisfy LICQ and there are m independent equality constraints, then
\operatorname{rank}(\bm{B})=m, \qquad p=n-m.
Thus Sylvester’s criterion can be applied directly to the reduced Hessian \bm{C} when one wants to verify the strict second-order sufficient condition. If p=0, the tangent space contains only the zero vector and the positivity condition on nonzero tangent directions is vacuous.
Example 3.1 (Example: reduced Hessian on the kernel) Consider
\bm{A}= \begin{bmatrix} 1&2&3\\ 2&0&1\\ 3&1&0 \end{bmatrix}, \qquad \bm{B}= \begin{bmatrix} 1&0&0 \end{bmatrix}.
The kernel of \bm{B} is
\ker(\bm{B}) = \left\{ \begin{bmatrix} 0\\\alpha\\\beta \end{bmatrix}: \alpha,\beta\in\mathbb{R} \right\}.
A convenient basis matrix is therefore
\bm{K} = \begin{bmatrix} 0&0\\ 1&0\\ 0&1 \end{bmatrix},
so that
\bm{z}=\bm{K} \begin{bmatrix} \alpha\\\beta \end{bmatrix}.
The reduced Hessian is
\begin{aligned} \bm{C} &= \bm{K}^\top\bm{A}\bm{K}\\ &= \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}. \end{aligned}
Its eigenvalues are +1 and -1, hence \bm{C} is indefinite. Therefore the second-order necessary condition fails: there are tangent directions \bm{z}\in\ker(\bm{B}) for which
\bm{z}^\top\bm{A}\bm{z}<0.
There are two standard ways to test the reduced Hessian \bm{C}.
Since \bm{C} is symmetric, it admits an orthogonal diagonalization
\bm{C}=\bm{Q}\bm{\Lambda}\bm{Q}^\top.
Hence
\bm{C}\succeq0 \quad\Longleftrightarrow\quad \lambda_i(\bm{C})\ge0 \quad\forall i,
and
\bm{C}\succ0 \quad\Longleftrightarrow\quad \lambda_i(\bm{C})>0 \quad\forall i.
For positive definiteness, Sylvester’s criterion gives
\bm{C}\succ0 \quad\Longleftrightarrow\quad \det(\bm{C}_k)>0, \qquad k=1,\ldots,p,
where \bm{C}_k are the leading principal submatrices of \bm{C}.
Example 3.2 (Application of Sylvester’s criterion) Consider
\bm{A}= \begin{bmatrix} 1&2\\ 2&5 \end{bmatrix}.
The leading principal minors are
\Delta_1=1>0,
and
\Delta_2 = \det \begin{bmatrix} 1&2\\ 2&5 \end{bmatrix} =5-4=1>0.
Therefore, by Sylvester’s criterion,
\bm{A}\succ0.
The same result follows from the eigenvalues. The characteristic polynomial is
\begin{aligned} p(\lambda) &= \det(\bm{A}-\lambda\bm{I})\\ &= (1-\lambda)(5-\lambda)-4\\ &= \lambda^2-6\lambda+1. \end{aligned}
Thus
\lambda_{1,2} =3\pm2\sqrt{2}.
Both eigenvalues are strictly positive, in agreement with Sylvester’s criterion.
3.2 Positive semidefinite matrices
A crucial distinction must be made between positive definite and positive semidefinite matrices.
For a symmetric matrix, nonnegativity of only the leading principal minors is not sufficient to conclude positive semidefiniteness.
The correct characterization is
Theorem 3.2 (Principal-minor criterion for positive semidefiniteness) A real symmetric matrix \bm{A} is positive semidefinite if and only if all principal minors of \bm{A} are nonnegative:
\boxed{ \bm{A}\succeq0 \quad\Longleftrightarrow\quad \det(\bm{A}[I,I])\ge0 \quad \text{for every index set }I\subseteq\{1,\ldots,n\}. }
Here \bm{A}[I,I] denotes the principal submatrix obtained by selecting the same index set I for rows and columns.
This criterion involves, in general, more minors than Sylvester’s criterion for positive definiteness. For numerical work, checking the eigenvalues of a symmetric reduced Hessian is often simpler when semidefiniteness rather than definiteness is required.
Equivalent Perturbation Characterization
There is also a useful exact perturbation characterization:
\boxed{ \bm{A}\succeq0 \quad\Longleftrightarrow\quad \bm{A}+\varepsilon\bm{I}\succ0 \quad\forall\varepsilon>0. }
Indeed, the eigenvalues of \bm{A}+\varepsilon\bm{I} are
\lambda_i(\bm{A})+\varepsilon.
Consequently, for a symmetric matrix,
\bm{A}\succeq0 \quad\Longleftrightarrow\quad \det\big((\bm{A}+\varepsilon\bm{I})_k\big)>0 \quad \forall k=1,\ldots,n, \quad\forall\varepsilon>0.
The quantifier for every \varepsilon>0 is essential. Merely checking the sign of a derivative at \varepsilon=0 is not a valid general criterion.
Example 3.3 (Example: a positive semidefinite matrix) Consider
\bm{A}= \begin{bmatrix} 1&2\\ 2&4 \end{bmatrix}.
Its eigenvalues are 0 and 5, hence
\bm{A}\succeq0.
The principal minors are
1\ge0, \qquad 4\ge0, \qquad \det(\bm{A})=0,
which also verifies the principal-minor criterion.
Using the perturbation characterization,
\bm{A}+\varepsilon\bm{I} = \begin{bmatrix} 1+\varepsilon&2\\ 2&4+\varepsilon \end{bmatrix},
and its leading principal minors are
1+\varepsilon>0
and
\begin{aligned} \det(\bm{A}+\varepsilon\bm{I}) &=(1+\varepsilon)(4+\varepsilon)-4\\ &=5\varepsilon+\varepsilon^2>0 \qquad\forall\varepsilon>0. \end{aligned}
Therefore \bm{A}+\varepsilon\bm{I}\succ0 for every \varepsilon>0, consistently with \bm{A}\succeq0.
Example 3.4 (Counterexample: nonnegative leading minors do not imply semidefiniteness) Consider
\bm{A}= \begin{bmatrix} 1&1&1\\ 1&1&1\\ 1&1&0 \end{bmatrix}.
Its leading principal minors are
\Delta_1=1, \qquad \Delta_2=0, \qquad \Delta_3=0.
Thus all leading principal minors are nonnegative. Nevertheless, \bm{A} is not positive semidefinite.
For example, the principal 2\times2 submatrix obtained from rows and columns \{1,3\} is
\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix},
whose determinant is
-1<0.
Hence the principal-minor criterion immediately shows that
\bm{A}\not\succeq0.
The eigenvalues give the same conclusion:
\lambda_1=0, \qquad \lambda_{2,3}=1\pm\sqrt{3},
and
1-\sqrt{3}<0.
The perturbation test is also consistent. In fact,
\det(\bm{A}+\varepsilon\bm{I}) = \varepsilon\big(\varepsilon^2+2\varepsilon-2\big),
which is negative for sufficiently small positive \varepsilon. Therefore \bm{A}+\varepsilon\bm{I} is not positive definite for all \varepsilon>0.
3.3 Summary
For a real symmetric matrix \bm{A}:
\boxed{ \begin{aligned} \bm{A}\succ0 &\iff \text{all leading principal minors are positive},\\[1mm] \bm{A}\prec0 &\iff (-1)^k\det(\bm{A}_k)>0 \quad\forall k,\\[1mm] \bm{A}\succeq0 &\iff \text{all principal minors are nonnegative},\\[1mm] \bm{A}\succeq0 &\iff \bm{A}+\varepsilon\bm{I}\succ0 \quad\forall\varepsilon>0. \end{aligned} }
For equality-constrained optimization, these tests should be applied to the reduced Hessian
\bm{C}=\bm{K}^\top \nabla_{\bm{x}}^2\mathcal{L}(\bm{x}^\star,\bm{\lambda}^\star) \bm{K},
where the columns of \bm{K} form a basis of the tangent space
\ker D\bm{h}(\bm{x}^\star).