Suppose is an complex matrix. For , we define the *leading principal submatrix* of to be the matrix

We define the *leading **principal minor* of to be the determinant of .

I prefer to think of matrices as operators on or , so what is the operator interpretation of the principal submatrix? Let be the projection map of a vector onto its first coordinates with respect to the standard basis . More precisely,

We can write as a matrix with respect to the standard bases of and :

Then .

Why are leading principal minors useful? Well, suppose that you have located a critical point of a smooth function . You want to determine whether or not this critical point is a local minimum. So, you compute the Hessian matrix at the point . The second derivative test says that is a local minimum if and only if the matrix is positive definite:

Second-Derivative Test.Suppose is a function on an open set . If is a critical point of and is positive definite, then is a strict local minimizer of on .

*Proof. *Set . Since is positive definite, we have that the function , for all . Restricting the domain of to the compact unit sphere , we see from Weierstrass’ theorem that attains its minimum at some point , so . Normalizing an arbitrary nonzero vector , we see that

Of course, equality also holds if .

If is sufficiently small, then Taylor’s theorem tells us that

if .

This is where the leading principal minors come in.

Theorem 1.(Sylvester’s Criterion) A real, symmetric matrix is positive definite if and only if all principal minors are positive.

The proof presented below is adapted from George T. Gilbert’s *American Mathematical Monthly* article “Positive Definite Matrices and Sylvester’s Criterion.” The full citation can be found below.

For necessity, it suffices to show that the principal minor is positive definite, for . Using the decomposition of obtained above and the hypothesis that is a positive definite matrix, we see that

For sufficiency, we first prove two lemmas.

Lemma 2.Let be a basis of a finite-dimensional vector space . Suppose is a -dimensional subspace of . If , then there exists a nonzero vector in which belongs to the span of .

*Proof. *Let be a basis for . If the statement of the lemma is false, then is a basis of , which contradicts that .

Lemma 3.Let be an real, symmetric matrix. Suppose is a -dimensional subspace of such thatThen has at least (counting multiplicity) positive eigenvalues.

*Proof. *By the real spectral theorem, there is an orthonormal basis for consisting of eigenvectors of with corresponding eigenvalues . Let denote the number of positive eigenvalues of , where . Assume for the sake of a contradiction that

Applying our hypothesis that the quadratic form defined by is positive on , we obtain

However, we assumed that are all nonpositive, so that , which is a contradiction.

We prove the suffiiency of Sylvester’s criterion by induction on . For the base , there is nothing to prove. Suppose that the sufficiency of Sylvester’s criterion is true for all real, symmetric matrices. Let denote the subspace of consisting of all vectors with zero coordinate. Using above, let denote the projection of onto the subspace spanned by the first coordinates with respect to the standard basis. Then

by our induction hypothesis. By the preceding lemma, has at least positive eigenvalues (counting multiplicity). Therefore the eigenvalue is also positive, since otherwise, the principal minor , which is a contradiction.

I’m not sure if Sylvester’s criterion is useful for determining whether an $latex n\times n$ matrix is positive definite, if is large; I didn’t study much numerical analysis as an undergraduate student. To apply Sylvester’s criterion, we need to know the signs of determinants. As far as I know, there is no algorithm that computes the sign of the determinant faster than the value of the determinant. So, we would need to compute determinants. Laplace expansion, which has arithmetic complexity of , is infeasible when is large. So, we would probably use Gaussian elimination, which has arithmetic complexity of , to put the leading principal submatrices in upper-triangular form to obtain the determinant.

If we had additional information about the full matrix , then the aforementioned approaches would be unnecessary. For instance, if we could easily find a basis with respect to which is upper triangular, then we could check positive definiteness by examining the diagonal entries. Recall that a matrix is positive definite if and only if all its eigenvalues are positive, and the diagonal entries of a matrix of an upper triangular matrix are precisely its eigenvalues repeated with multiplicity. Therefore we only need to check whether the diagonal entries are all positive.

From a numerical perspective, won’t the power method help to determine if it is positive?

If my understanding is correct, the power method only gives you the eigenvalue with the largest magnitude; however, a matrix is positive definite if and only if all its eigenvalues are positive. So, I’m not sure how knowing just one eigenvalue will help.

There may be a multi-step adaptation of the power method, which perhaps is closer to what you have in mind, but I am not familiar with it. If you find out more, please do let me know.

Oh, I was thinking if you have a numerical technique to estimate the lowest eigenvalue (or its corresponding eigenvector), then that would certainly tell you if the matrix is positive or not. I though power method did that. Guess, I was wrong.

Pingback: Sylvester’s Criterion for Positive-Semidefinite Matrices I | Math by Matt

Pingback: URL

The spectral decomposition of a real symmetric matrix can be done relatively easily using the Jacobi iteration algorithm, at least for moderate (n x n) matrices. Non-linear optimization objective functions I have encountered are typically less than 20-30 variables, which are well withing the capability of the Jacobi algorithm.