Sylvester's criterion

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

An analogous theorem holds for characterizing positive-semidefinite Hermitian matrices, except that it is no longer sufficient to consider only the leading principal minors: a Hermitian matrix M is positive-semidefinite if and only if all principal minors of M are nonnegative.[1]

Proof[edit]

The proof is only for nonsingular Hermitian matrix with coefficients in , 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 = BTB, and all eigenvalues are positive if and only if B is nonsingular.[2]

Proof:

Forward implication: If ARn×n 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 being 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):

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.[3]

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.

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() yields the desired factorization, because A = LD1/2D1/2LTRTR, 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:

R = LD, where L is a lower triangular matrix with a unit diagonal and D is the diagonal matrix whose diagonal entries are the rii ’s. Hence D has a positive diagonal and hence D is non-singular. Hence D2 is a non-singular diagonal matrix. Also, LT is an upper triangular matrix with a unit diagonal. Consequently, A = LD2LT is the LDU factorization for A, and thus the pivots must be positive because they are the diagonal entries in D2.

Uniqueness of the Cholesky decomposition: If we have another Cholesky decomposition A = R1R1T of A, where R1 is lower triangular with a positive diagonal, then similar to the above we may write R1 = L1D1, where L1 is a lower triangular matrix with a unit diagonal and D1 is a diagonal matrix whose diagonal entries are the same as the corresponding diagonal entries of R1. Consequently, A = L1D12L1T is an LDU factorization for A. By the uniqueness of the LDU factorization of A, we have L1 = L and D12 = D2. As both D1 and D are diagonal matrices with positive diagonal entries, we have D1 = D. Hence R1 = L1D1 = LD = R. Hence A has a unique Cholesky decomposition.

Theorem III: Let Ak be the k × k leading principal submatrix of An×n. If A has an LU factorization A = LU, where L is a lower triangular matrix with a unit diagonal, 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, where ujj is the (j, j)-th entry of U for all j = 1, 2, . . . , n.[4]

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

As A is non-singular and , it follows that all the diagonal entries of R are non-zero. Let rjj be the (j, j)-th entry of E for all j = 1, 2, . . . , n. Then rjj ≠ 0 for all j = 1, 2, . . . , n.

Let F be a diagonal matrix, and let fjj be the (j, j)-th entry of F for all j = 1, 2, . . . , n. For all j = 1, 2, . . . , n, we set fjj = 1 if rjj > 0, and we set fjj = -1 if rjj < 0. Then , the n × n identity matrix.

Let S=FR. Then S is an upper-triangular matrix with all diagonal entries being positive. Hence we have , 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 = 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 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.

Notes[edit]

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

References[edit]