# Sylvester's criterion

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

Sylvester's criterion states that a 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$,
• ...
• $M$ itself.

In other words, all of the leading principal minors must be positive.

## Proof

The proof is only for nonsingular Hermitian matrix with coefficients in $\mathbb{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.[1]

 Proof: Forward implication: If A ∈ Rnxn is symmetric, then, by the Spectral theorem, there is an orthogonal matrix P such that A = PDPT , where D = diag (λ1, λ2, . . . , λn) is real diagonal matrix with entries - eigenvalues of A and P is such that its columns are the eigenvectors of A. If λi ≥ 0 for each i, then D1/2 exists, so A = PDPT = PD1/2D1/2PT = BTB for B = D1/2PT, and λi > 0 for each i if and only if B is nonsingular. Reverse implication: Conversely, if A can be factored as A = BTB, then all eigenvalues of A are nonnegative because for any eigenpair (λ, x): λ=${\frac{x^TAx}{x^Tx}}={\frac{x^TB^TBx}{x^Tx}}={\frac{||Bx||^2}{||x||^2}}$≥0.

Theorem II (The Cholesky decomposition): The symmetric matrix A possesses positive pivots if and only if A can be uniquely factored as A = RTR, 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.[2]

 Proof: Forward implication: If A possesses positive pivots (therefore A possesses an LU factorization: A=L.U' ), then, it has an LDU factorization A = LDU=LDLT in which D = diag (u11, u22, . . . , unn) is the diagonal matrix containing the pivots uii > 0. $\mathbf{A} =LU'= \begin{bmatrix} 1 & 0 & . & 0\\ l_{12} & 1 & . & 0 \\ . & . & . & . \\ l_{1n} & l_{2n} & . & 1 \end{bmatrix}$ x $\begin{bmatrix} u_{11} & u_{12} & . & u_{1n}\\ 0 & u_{22} & . & u_{2n} \\ . & . & . & . \\ 0 & 0 & . & u_{nn} \end{bmatrix} =LDU= \begin{bmatrix} 1 & 0 & . & 0\\ l_{12} & 1 & . & 0 \\ . & . & . & . \\ l_{1n} & l_{2n} & . & 1 \end{bmatrix}$ x $\begin{bmatrix} u_{11} & 0 & . & 0\\ 0 & u_{22} & . & 0 \\ . & . & . & . \\ 0 & 0 & . & u_{nn} \end{bmatrix}$ x $\begin{bmatrix} 1 & u_{12}/u_{11} & . & u_{1n}/u_{11}\\ 0 & 1 & . & u_{2n}/u_{22} \\ . & . & . & . \\ 0 & 0 & . & 1 \end{bmatrix}$ By a uniqueness property of the LDU decomposition, the symmetry of A yields: U=LT, consequently A=LDU=LDLT. Setting R = D1/2LT where D1/2 = diag($\scriptstyle\sqrt{u_{11}},\scriptstyle\sqrt{u_{22}},...,\scriptstyle\sqrt{u_{11}}$) yields the desired factorization, because A = LD1/2D1/2LT = RTR, and R is upper triangular with positive diagonal entries. Reverse implication: Conversely, if A = RRT , where R is lower triangular with a positive diagonal, then factoring the diagonal entries out of R is as follows: $\mathbf{R} =LD= \begin{bmatrix} 1 & 0 & . & 0\\ r_{12}/r_{11} & 1 & . & 0 \\ . & . & . & . \\ r_{1n}/r_{11} & r_{2n}/r_{22} & . & 1 \end{bmatrix}$ x $\begin{bmatrix} r_{11} & 0 & . & 0\\ 0 & r_{22} & . & 0 \\ . & . & . & . \\ 0 & 0 & . & r_{nn} \end{bmatrix}.$ R = LD, where L is lower triangular with a unit diagonal and D is the diagonal matrix whose diagonal entries are the rii ’s. Consequently, A = LD2LT is the LDU factorization for A, and thus the pivots must be positive because they are the diagonal entries in D2.

Theorem III: Let Ak be the k × k leading principal submatrix of An×n. If A has an LU factorization A = LU, then det(Ak) = u11u22 · · · ukk, and the k-th pivot is ukk =det(A1) = a11 for k = 1, ukk=det(Ak)/det(Ak−1) for k = 2, 3, . . . , n.[3]

Combining Theorem II with Theorem III yields:

Statement I: If the symmetric matrix A can be factored as A=RTR 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 symmetric matrix A can be factored as $A=B^TB$, then the QR decomposition (closely related to Gram-Schmidt process) of B (B=QR) yields: $A=B^TB=R^TQ^TQR=R^TR$, where Q is orthogonal matrix and R is upper triangular matrix.

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=BTB, where B is nonsingular (Theorem I), the expression A=BTB implies that A possess factorization of the form A=RTR 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 states:

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

The sufficiency and necessity conditions automatically hold because they were proven for each of the above theorems.

## Notes

1. ^ Carl D. Meyer, Matrix Analysis and Applied Linear Algebra. See chapter 7.6 Positive Definite Matrices, page 558
2. ^ Carl D. Meyer, Matrix Analysis and Applied Linear Algebra. See chapter 3.10 The LU Factorization, Example 3.10.7, page 154
3. ^ Carl D. Meyer, Matrix Analysis and Applied Linear Algebra. See chapter 6.1 Determinants, Exercise 6.1.16, page 474