Sylvester's criterion

In mathematics, Sylvester’s criterion is a necessary and sufficient criterion to determine whether a Hermitian matrix is positive-definite.

Sylvester's criterion states that a n × n Hermitian matrix M is positive-definite if and only if all the following matrices have a positive determinant:

• the upper left 1-by-1 corner of M,
• the upper left 2-by-2 corner of M,
• the upper left 3-by-3 corner of M,
• ${}\quad \vdots$
• M itself.

In other words, all of the leading principal minors must be positive. By using appropriate permutations of rows and columns of M, it can also be shown that the positivity of any nested sequence of n principal minors of M is equivalent to M being positive-definite.

An analogous theorem holds for characterizing positive-semidefinite Hermitian matrices, except that it is no longer sufficient to consider only the leading principal minors as illustrated by the Hermitian matrix

${\begin{pmatrix}0&0&-1\\0&-1&0\\-1&0&0\end{pmatrix}}\quad {\text{with eigenvectors}}\quad {\begin{pmatrix}0\\1\\0\end{pmatrix}},\quad {\begin{pmatrix}1\\0\\1\end{pmatrix}}\quad {\text{and}}\quad {\begin{pmatrix}1\\0\\-1\end{pmatrix}}.$

A Hermitian matrix M is positive-semidefinite if and only if all principal minors of M are nonnegative.

Proof for the case of positive definite matrices

Suppose $M_{n}$ is $n\times n$ Hermitian matrix $M_{n}^{\dagger }=M_{n}$. Let $M_{k},k=1,\ldots n$ be the leading principal minor matrices, i.e. the $k\times k$ upper left corner matrices. It will be shown that if $M_{n}$ is positive definite, then the principal minors are positive; that is, $\det M_{k}>0$ for all $k$.

$M_{k}$ is positive definite. Indeed, choosing

$x=\left({\begin{array}{c}x_{1}\\\vdots \\x_{k}\\0\\\vdots \\0\end{array}}\right)=\left({\begin{array}{c}{\vec {x}}\\0\\\vdots \\0\end{array}}\right)$

we can notice that $0<x^{\dagger }M_{n}x={\vec {x}}^{\dagger }M_{k}{\vec {x}}.$ Equivalently, the eigenvalues of $M_{k}$ are positive, and this implies that $\det M_{k}>0$ since the determinant is the product of the eigenvalues.

To prove the reverse implication, we use induction. The general form of an $(n+1)\times (n+1)$ Hermitian matrix is

$M_{n+1}=\left({\begin{array}{cc}M_{n}&{\vec {v}}\\{\vec {v}}^{\dagger }&d\end{array}}\right)\qquad (*)$,

where $M_{n}$ is an $n\times n$ Hermitian matrix, ${\vec {v}}$ is a vector and $d$ is a real constant.

Suppose the criterion holds for $M_{n}$. Assuming that all the principal minors of $M_{n+1}$ are positive implies that $\det M_{n+1}>0$, $\det M_{n}>0$, and that $M_{n}$ is positive definite by the inductive hypothesis. Denote

$x=\left({\begin{array}{c}{\vec {x}}\\x_{n+1}\end{array}}\right)$

then

$x^{\dagger }M_{n+1}x={\vec {x}}^{\dagger }M_{n}{\vec {x}}+x_{n+1}{\vec {x}}^{\dagger }{\vec {v}}+{\bar {x}}_{n+1}{\vec {v}}^{\dagger }{\vec {x}}+d|x_{n+1}|^{2}$

By completing the squares, this last expression is equal to

$({\vec {x}}^{\dagger }+{\vec {v}}^{\dagger }M_{n}^{-1}{\bar {x}}_{n+1})M_{n}({\vec {x}}+x_{n+1}M_{n}^{-1}{\vec {v}})-|x_{n+1}|^{2}{\vec {v}}^{\dagger }M_{n}^{-1}{\vec {v}}+d|x_{n+1}|^{2}$

$=({\vec {x}}+{\vec {c}})^{\dagger }M_{n}({\vec {x}}+{\vec {c}})+|x_{n+1}|^{2}(d-{\vec {v}}^{\dagger }M_{n}^{-1}{\vec {v}})$

where ${\vec {c}}=x_{n+1}M_{n}^{-1}{\vec {v}}$ (note that $M_{n}^{-1}$ exists because the eigenvalues of $M_{n}$ are all positive.) The first term is positive by the inductive hypothesis. We now examine the sign of the second term. By using the block matrix determinant formula

$\det \left({\begin{array}{cc}A&B\\C&D\end{array}}\right)=\det A\det(D-CA^{-1}B)$

on $(*)$ we obtain

$\det M_{n+1}=\det M_{n}(d-{\vec {v}}^{\dagger }M_{n}^{-1}{\vec {v}})>0$, which implies $d-{\vec {v}}^{\dagger }M_{n}^{-1}{\vec {v}}>0$.

Consequently, $x^{\dagger }M_{n+1}x>0.$

Proof for the case of positive semidefinite matrices

Let $M_{n}$ be an n x n Hermitian matrix. Suppose $M_{n}$ is semidefinite. Essentially the same proof as for the case that $M_{n}$ is strictly positive definite shows that all principal minors (not necessarily the leading principal minors) are non-negative.

For the reverse implication, it suffices to show that if $M_{n}$ has all non-negative principal minors, then for all t>0, all leading principal minors of the Hermitian matrix $M_{n}+tI_{n}$ are strictly positive, where $I_{n}$ is the nxn identity matrix. Indeed, from the positive definite case, we would know that the matrices $M_{n}+tI_{n}$ are strictly positive definite. Since the limit of positive definite matrices is always positive semidefinite, we can take $t\to 0$ to conclude.

To show this, let $M_{k}$ be the kth leading principal submatrix of $M_{n}.$ We know that $q_{k}(t)=\det(M_{k}+tI_{k})$ is a polynomial in t, related to the characteristic polynomial $p_{M_{k}}$ via $$q_{k}(t)=(-1)^{k}p_{M_{k}}(-t).$$ We use the identity in Characteristic polynomial#Properties to write $$q_{k}(t)=\sum _{j=0}^{k}t^{k-j}\operatorname {tr} \left(\textstyle \bigwedge ^{j}M_{k}\right),$$ where ${\textstyle \operatorname {tr} \left(\bigwedge ^{j}M_{k}\right)}$ is the trace of the jth exterior power of $M_{k}.$

From Minor_(linear_algebra)#Multilinear_algebra_approach, we know that the entries in the matrix expansion of $\bigwedge ^{j}M_{k}$ (for j > 0) are just the minors of $M_{k}.$ In particular, the diagonal entries are the principal minors of $M_{k}$, which of course are also principal minors of $M_{n}$, and are thus non-negative. Since the trace of a matrix is the sum of the diagonal entries, it follows that $$\operatorname {tr} \left(\textstyle \bigwedge ^{j}M_{k}\right)\geq 0.$$ Thus the coefficient of $t^{k-j}$ in $q_{k}(t)$ is non-negative for all j > 0. For j = 0, it is clear that the coefficient is 1. In particular, $q_{k}(t)>0$ for all t > 0, which is what was required to show.

References

• Gilbert, George T. (1991), "Positive definite matrices and Sylvester's criterion", The American Mathematical Monthly, 98 (1), Mathematical Association of America: 44–46, doi:10.2307/2324036, ISSN 0002-9890, JSTOR 2324036.
• Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 978-0-521-38632-6. Theorem 7.2.5.
• Carl D. Meyer (June 2000), Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 0-89871-454-0.