Sylvester's Criterion - Proof

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 whose eigenvalues are positive (λ>0) is called positive definite, and when the eigenvalues are just nonnegative (λ≥0), is said to be positive semidefinite.

Theorem I: A real-symmetric matrix has nonnegative eigenvalues if and only if can be factored as, and all eigenvalues are positive if and only if is nonsingular.

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 it 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):

λ=≥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.

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 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.

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, 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.

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.

Read more about this topic:  Sylvester's Criterion

Famous quotes containing the word proof:

    “Right and proof are two crutches for everything bent and crooked that limps along.”
    —Franz Grillparzer (1791–1872)

    “If we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
    —Polly Berrien Berends (20th century)

    “War is a beastly business, it is true, but one proof we are human is our ability to learn, even from it, how better to exist.”
    —M.F.K. Fisher (1908–1992)