Sylvester's criterion

Proof

The proof is only for nonsingular Hermitian matrix with coefficients in R , therefore only for nonsingular real-symmetric matrices.

Positive definite or semidefinite matrix: A symmetric matrix A whose eigenvalues are positive (λ > 0) is called positive definite, and when the eigenvalues are just nonnegative (λ ≥ 0), A is said to be positive semidefinite.

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.

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.

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_jj is the (j, j)-th entry of U for all j = 1, 2, . . . , n.

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 A = B T B , then the QR decomposition (closely related to Gram-Schmidt process) of B (B = QR) yields: A = B T B = R T Q T Q R = R T R , where Q is orthogonal matrix and R is upper triangular matrix.

As A is non-singular and 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 E 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 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 A = R T R = R T F T F R = 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.