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]}
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 = B^{T}B, and all eigenvalues are positive if and only if B is nonsingular.^{[2]}
Proof: |
Forward implication: If A ∈ R^{n×n} is symmetric, then, by the spectral theorem, there is an orthogonal matrix P such that A = PDP^{T} , 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 D^{1/2} exists, so A = PDP^{T} = PD^{1/2}D^{1/2}P^{T} = B^{T}B for B = D^{1/2}P^{T}, and λ_{i} > 0 for each i if and only if B is nonsingular. Reverse implication: Conversely, if A can be factored as A = B^{T}B, 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 = R^{T}R, 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 = LDL^{T} in which D = diag(u_{11}, u_{22}, . . . , u_{nn}) is the diagonal matrix containing the pivots u_{ii} > 0. By a uniqueness property of the LDU decomposition, the symmetry of A yields: U = L^{T}, consequently A = LDU = LDL^{T}. Setting R = D^{1/2}L^{T} where D^{1/2} = diag() yields the desired factorization, because A = LD^{1/2}D^{1/2}L^{T} = R^{T}R, and R is upper triangular with positive diagonal entries. Reverse implication: Conversely, if A = RR^{T}, 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 r_{ii} ’s. Hence D has a positive diagonal and hence D is non-singular. Hence D^{2} is a non-singular diagonal matrix. Also, L^{T} is an upper triangular matrix with a unit diagonal. Consequently, A = LD^{2}L^{T} is the LDU factorization for A, and thus the pivots must be positive because they are the diagonal entries in D^{2}. Uniqueness of the Cholesky decomposition: If we have another Cholesky decomposition A = R_{1}R_{1}^{T} of A, where R_{1} is lower triangular with a positive diagonal, then similar to the above we may write R_{1} = L_{1}D_{1}, where L_{1} is a lower triangular matrix with a unit diagonal and D_{1} is a diagonal matrix whose diagonal entries are the same as the corresponding diagonal entries of R_{1}. Consequently, A = L_{1}D_{1}^{2}L_{1}^{T} is an LDU factorization for A. By the uniqueness of the LDU factorization of A, we have L_{1} = L and D_{1}^{2} = D^{2}. As both D_{1} and D are diagonal matrices with positive diagonal entries, we have D_{1} = D. Hence R_{1} = L_{1}D_{1} = LD = R. Hence A has a unique Cholesky decomposition. |
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_{11}u_{22} · · · u_{kk}, and the k-th pivot is u_{kk} = det(A_{1}) = a_{11} 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.^{[4]}
Combining Theorem II with Theorem III yields:
Statement I: If the symmetric matrix A can be factored as A=R^{T}R 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 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 , 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 = B^{T}B, where B is nonsingular (Theorem I), the expression A = B^{T}B implies that A possess factorization of the form A = R^{T}R 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
- ↑ 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, 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. See Theorem 7.2.5.
- Carl D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 0-89871-454-0.