Sylvester's criterion

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

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

${\displaystyle 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 ${\displaystyle 0<x^{\dagger }M_{n}x={\vec {x}}^{\dagger }M_{k}{\vec {x}}.}$ Equivalently, the eigenvalues of ${\displaystyle M_{k}}$ are positive, and this implies that ${\displaystyle \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 ${\displaystyle (n+1)\times (n+1)}$ Hermitian matrix is

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

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

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

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

then

${\displaystyle 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

${\displaystyle ({\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}}$

${\displaystyle =({\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 ${\displaystyle {\vec {c}}=x_{n+1}M_{n}^{-1}{\vec {v}}}$ (note that ${\displaystyle M_{n}^{-1}}$ exists because the eigenvalues of ${\displaystyle 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

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

on ${\displaystyle (*)}$ we obtain

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

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

The previous proof is only for nonsingular Hermitian matrix with coefficients in ${\displaystyle \mathbb {R} }$, and therefore only for nonsingular real-symmetric matrices.

Theorem I: A real-symmetric matrix A has nonnegative eigenvalues if and only if A can be factored as A = B^TB, and all eigenvalues are positive if and only if B is nonsingular.[4]

Theorem II (The Cholesky decomposition): The symmetric matrix A possesses positive pivots if and only if A can be uniquely factored as A = R^TR, where R is an upper-triangular matrix with positive diagonal entries. This is known as the Cholesky decomposition of A, and R is called the Cholesky factor of A.[5]

Theorem III: Let A_k be the k × k leading principal submatrix of A_n×n. If A has an LU factorization A = LU, where L is a lower triangular matrix with a unit diagonal, then det(A_k) = u₁₁u₂₂ · · · u_kk, and the k-th pivot is u_kk = det(A₁) = a₁₁ for k = 1, u_kk = det(A_k)/det(A_k−1) for k = 2, 3, . . . , n, where u_kk is the (k, k)-th entry of U for all k = 1, 2, . . . , n.[6]

Combining Theorem II with Theorem III yields:

Statement I: If the symmetric matrix A can be factored as A=R^TR where R is an upper-triangular matrix with positive diagonal entries, then all the pivots of A are positive (by Theorem II), therefore all the leading principal minors of A are positive (by Theorem III).

Statement II: If the nonsingular n × n symmetric matrix A can be factored as ${\displaystyle A=B^{T}B}$, then the QR decomposition (closely related to Gram-Schmidt process) of B (B = QR) yields: ${\displaystyle A=B^{T}B=R^{T}Q^{T}QR=R^{T}R}$, where Q is orthogonal matrix and R is upper triangular matrix.

As A is non-singular and ${\displaystyle A=R^{T}R}$, it follows that all the diagonal entries of R are non-zero. Let r_jj be the (j, j)-th entry of R for all j = 1, 2, . . . , n. Then r_jj ≠ 0 for all j = 1, 2, . . . , n.

Let F be a diagonal matrix, and let f_jj be the (j, j)-th entry of F for all j = 1, 2, . . . , n. For all j = 1, 2, . . . , n, we set f_jj = 1 if r_jj > 0, and we set f_jj = -1 if r_jj < 0. Then ${\displaystyle F^{T}F=I_{n}}$, the n × n identity matrix.

Let S=FR. Then S is an upper-triangular matrix with all diagonal entries being positive. Hence we have ${\displaystyle A=R^{T}R=R^{T}F^{T}FR=S^{T}S}$, for some upper-triangular matrix S with all diagonal entries being positive.

Namely Statement II requires the non-singularity of the symmetric matrix A.

Combining Theorem I with Statement I and Statement II yields:

Statement III: If the real-symmetric matrix A is positive definite then A possess factorization of the form A = B^TB, where B is nonsingular (Theorem I), the expression A = B^TB implies that A possess factorization of the form A = R^TR where R is an upper-triangular matrix with positive diagonal entries (Statement II), therefore all the leading principal minors of A are positive (Statement I).

In other words, Statement III proves the "only if" part of Sylvester's Criterion for non-singular real-symmetric matrices.

Sylvester's Criterion: The real-symmetric matrix A is positive definite if and only if all the leading principal minors of A are positive.

Let ${\displaystyle M_{n}}$ be an n x n Hermitian matrix. Suppose ${\displaystyle M_{n}}$ is semidefinite. Essentially the same proof as for the case that ${\displaystyle 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 ${\displaystyle M_{n}}$ then for all t>0, all leading principal minors of the Hermitian matrix ${\displaystyle M_{n}+tI_{n}}$ are strictly positive, where ${\displaystyle I_{n}}$ is the nxn identity matrix. Indeed, from the positive definite case, we would know that the matrices ${\displaystyle M_{n}+tI_{n}}$ are strictly positive definite. Since the limit of positive definite matrices is always positive semidefinite, we can take ${\displaystyle t\to 0}$ to conclude.

To show this, let ${\displaystyle M_{k}}$ be the kth leading principal submatrix of ${\displaystyle M_{n}.}$ We know that ${\displaystyle q_{k}(t)=\det(M_{k}+tI_{k})}$ is a polynomial in t, related to the characteristic polynomial ${\displaystyle p_{M_{k}}}$ via

$${\displaystyle q_{k}(t)=(-1)^{k}p_{M_{k}}(-t).}$$

We use the identity in Characteristic polynomial#Properties to write

$${\displaystyle 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 ${\displaystyle M_{k}.}$

From Minor_(linear_algebra)#Multilinear_algebra_approach, we know that the entries in the matrix expansion of ${\displaystyle \bigwedge ^{j}M_{k}}$ (for j > 0) are just the minors of ${\displaystyle M_{k}.}$ In particular, the diagonal entries are the principal minors of ${\displaystyle M_{k}}$, which of course are also principal minors of ${\displaystyle M_{n}}$, and are thus non-negative. Since the trace of a matrix is the sum of the diagonal entries, it follows that

$${\displaystyle \operatorname {tr} \left(\textstyle \bigwedge ^{j}M_{k}\right)\geq 0.}$$

Thus the coefficient of ${\displaystyle t^{k-j}}$ in ${\displaystyle q_{k}(t)}$ is non-negative for all j > 0. For j = 0, it is clear that the coefficient is 1. In particular, ${\displaystyle q_{k}(t)>0}$ for all t > 0, which is what was required to show.

• Gilbert, George T. (1991), "Positive definite matrices and Sylvester's criterion", The American Mathematical Monthly, Mathematical Association of America, 98 (1): 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.