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.

Proof[edit]

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[edit]

  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

References[edit]