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.
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][2]
Proof
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.[3]
Proof: |
Forward implication: If A ∈ Rn×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.[4]
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/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: 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 ukk is the (k, k)-th entry of U for all k = 1, 2, . . . , n.[5]
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
- ^ Carl D. Meyer, Matrix Analysis and Applied Linear Algebra. See chapter 7.6 Positive Definite Matrices, page 566
- ^ Prussing, John E. (1986), "The Principal Minor Test for Semidefinite Matrices" (PDF), Journal of Guidance, Control, and Dynamics, 9 (1): 121–122, archived from the original (PDF) on 2017-01-07, retrieved 2017-09-28
- ^ Carl D. Meyer, Matrix Analysis and Applied Linear Algebra. See chapter 7.6 Positive Definite Matrices, page 558
- ^ Carl D. Meyer, Matrix Analysis and Applied Linear Algebra. See chapter 3.10 The LU Factorization, Example 3.10.7, page 154
- ^ Carl D. Meyer, Matrix Analysis and Applied Linear Algebra. See chapter 6.1 Determinants, Exercise 6.1.16, page 474
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. See Theorem 7.2.5.
- Carl D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 0-89871-454-0.