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 :
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
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 that
Then 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.