Understanding Sylvester's Criterion determining positive definiteness

Question

on Wikipedia the theorem states that

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.

Now the definition of a principal minor is strange to me in this case, does this simply mean the entries along the diagonal must be positive for the matrix to be positive definite? is this definition the same for non negative elements along the diagonal meaning the matrix is positive semi-definite?

Answer 1

Yes, the diagonal entries of a positive definite matrix must be positive, and the diagonal entries of a positive semidefinite matrix must be nonnegative. But that's a necessary condition, not sufficient. You still need those determinants to be positive.

Answer 2

We wish to prove the following equivalence.

Proposition (Sylvester's criterion) Let $\mathbf{A} \in \mathbb{C}^{n \times n}$ be Hermitian. Then, $\mathbf{A}$ is positive definite if and only if all leading submatrices of $\mathbf{A}$ have a strictly positive determinant.

Proposition (Block LDU decomposition) A two by two block matrix $\mathbf{A}$ has the block LDU decomposition \begin{equation} \mathbf{A} = \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \end{bmatrix} = \begin{bmatrix} \mathbf{A}_{11} & \mathbf{0} \\ \mathbf{A}_{21} & \mathbf{I} \end{bmatrix} \begin{bmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{0} & \mathbf{A}_{22} - \mathbf{A}_{21} \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \end{bmatrix} \begin{bmatrix} \mathbf{I} & \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \\ \mathbf{0} & \mathbf{I} \end{bmatrix} = \mathbf{L}\mathbf{D}\mathbf{U}, \end{equation} assuming that $\mathbf{A}_{11}$ is invertible. Furthermore, \begin{equation} \det(\mathbf{A}) = \det(\mathbf{A}_{11}) \det(\mathbf{A}_{22} - \mathbf{A}_{21} \mathbf{A}_{11}^{-1} \mathbf{A}_{12}). \end{equation}

Motivation. Let's perform block Gauss-Jordan elimination on $\mathbf{A}$. First, perform a row operation $\mathbf{R}_1$ to set $\mathbf{A}_{11}$ to $\mathbf{I}$, \begin{equation} \mathbf{R}_1 \mathbf{A} = \begin{bmatrix} \mathbf{A}_{11}^{-1} & \mathbf{0} \\ \mathbf{0} & \mathbf{I} \end{bmatrix} \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \end{bmatrix} = \begin{bmatrix} \mathbf{I} & \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \end{bmatrix}. \end{equation} Then, perform a row operation $\mathbf{R}_2$ to set the entry below the pivot $\mathbf{I}$ to zero, \begin{equation} \mathbf{R} \mathbf{A} := \mathbf{R}_2 \mathbf{R}_1 \mathbf{A} = \begin{bmatrix} \mathbf{I} & \mathbf{0} \\ -\mathbf{A}_{21} & \mathbf{I} \end{bmatrix} \begin{bmatrix} \mathbf{I} & \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \end{bmatrix} = \begin{bmatrix} \mathbf{I} & \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \\ \mathbf{0} & \mathbf{A}_{22} - \mathbf{A}_{21} \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \end{bmatrix}. \end{equation} And finally, perform a column operation $\mathbf{C}$ to set the entry right of the pivot $\mathbf{I}$ to zero, \begin{equation} \mathbf{R} \mathbf{A} \mathbf{C} := \begin{bmatrix} \mathbf{I} & \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \\ \mathbf{0} & \mathbf{A}_{22} - \mathbf{A}_{21} \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \end{bmatrix} \begin{bmatrix} \mathbf{I} & - \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \\ \mathbf{0} & \mathbf{I} \end{bmatrix} = \begin{bmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{0} & \mathbf{A}_{22} - \mathbf{A}_{21} \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \end{bmatrix} =: \mathbf{D}. \end{equation} This yields the block reduced row echelon form $\mathbf{D}$. Notice that \begin{equation} \mathbf{A} = \mathbf{R}^{-1} \mathbf{R} \mathbf{A} \mathbf{C} \mathbf{C}^{-1} = \mathbf{R}^{-1} \mathbf{D} \mathbf{C}^{-1} = \mathbf{L} \mathbf{D} \mathbf{U}. \end{equation} Indeed, one can show that $\mathbf{L} = \mathbf{R}^{-1} = \mathbf{R}_1^{-1} \mathbf{R}_2^{-1}$ and $\mathbf{U} = \mathbf{C}^{-1}$ are the matrices of the proposition.

Proof. We check \begin{equation} \begin{aligned} \mathbf{L}\mathbf{D}\mathbf{U} &= \begin{bmatrix} \mathbf{A}_{11} & \mathbf{0} \\ \mathbf{A}_{21} & \mathbf{I} \end{bmatrix} \begin{bmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{0} & \mathbf{A}_{22} - \mathbf{A}_{21} \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \end{bmatrix} \begin{bmatrix} \mathbf{I} & \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \\ \mathbf{0} & \mathbf{I} \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{A}_{11} & \mathbf{0} \\ \mathbf{A}_{21} & \mathbf{A}_{22} - \mathbf{A}_{21} \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \end{bmatrix} \begin{bmatrix} \mathbf{I} & \mathbf{A}_{11}^{-1} \mathbf{A}_{12} \\ \mathbf{0} & \mathbf{I} \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \end{bmatrix} = \mathbf{A}. \end{aligned} \end{equation} The determinant \begin{equation} \det(\mathbf{A}) = \det(\mathbf{L}\mathbf{D}\mathbf{U}) = \det(\mathbf{L})\det(\mathbf{D})\det(\mathbf{U}) = \det(\mathbf{A}_{11}) \det(\mathbf{A}_{22} - \mathbf{A}_{21} \mathbf{A}_{11}^\mathrm{T} \mathbf{A}_{12}). \end{equation} This concludes our proof.

Proposition (Sylvester's criterion) Let $\mathbf{A} \in \mathbb{C}^{n \times n}$ be Hermitian. Then, $\mathbf{A}$ is positive definite if and only if all leading submatrices of $\mathbf{A}$ have a strictly positive determinant.

Proof. Consider a Hermitian matrix $\mathbf{A} \in \mathbb{C}^{n \times n}$.
( $\Longrightarrow$ ) Let $\mathbf{A}$ be positive definite. Then, for any leading submatrix $\mathbf{A}_k := \mathbf{A}_{1:k,1:k}$ of $\mathbf{A}$, for any non-zero vector $\mathbf{x}_k \in \mathbb{C}^{n} \setminus \{\mathbf{0}\}$, we have \begin{equation} 0 < \begin{bmatrix} \mathbf{x}_k^* & \mathbf{0} \end{bmatrix} \mathbf{A} \begin{bmatrix} \mathbf{x}_k \\ \mathbf{0} \end{bmatrix} = \mathbf{x}_k^* \mathbf{A}_k \mathbf{x}_k, \end{equation} so $\mathbf{A}_k$ is positive definite as well. As all eigenvalues of the positive definite matrix $\mathbf{A}_k$ are strictly positive (why?), and the determinant $\det(\mathbf{A}_k) := \prod_{i=1}^k \lambda_i$ is the product of the eigenvalues (why?), we have that $\det(\mathbf{A}_k) > 0$. Hence, all leading submatrices of $\mathbf{A}$ have a strictly positive determinant.
( $\Longleftarrow$ ) We proceed by induction on the size $n$ of a Hermitian matrix $\mathbf{A} \in \mathbb{C}^{n \times n}$.
( Base case ) Consider a matrix $[a_{11}] = \mathbf{A} \in \mathbb{C}^{1 \times 1}$ such that $\det(\mathbf{A}) > 0$. As $\mathbf{A}$ is Hermitian, $[a_{11}] = \mathbf{A} = \mathbf{A}^* = [\overline{a}_{11}]$ and $a_{11} \in \mathbb{R}$. And, as $a_{11} = \det(\mathbf{A}) > 0$, the matrix $\mathbf{A}$ is trivially positive definite.
( Induction hypothesis ) Suppose that the proposition holds for matrices of size $n = k-1$.
( Induction step ) Let $\mathbf{A} \in \mathbb{C}^{k \times k}$ be a matrix of size $n=k$ such that all leading submatrices of $\mathbf{A}$ have a strictly positive determinant. As $\mathbf{A}$ is Hermitian, we can partition $\mathbf{A}$ as (why?) \begin{equation} \mathbf{A} = \begin{bmatrix} \mathbf{A}_{k-1} & \mathbf{c} \\ \mathbf{c}^* & a_{kk} \end{bmatrix}, \end{equation} where $\mathbf{A}_{k-1} \in \mathbb{C}^{(k-1) \times (k-1)}$, $\mathbf{c} \in \mathbb{C}^{k-1}$ and $a_{kk} \in \mathbb{C}$. All leading submatrices of $\mathbf{A}_{k-1}$ have a strictly positive determinant, and by the induction hypothesis, $\mathbf{A}_{k-1}$ is positive definite. Furthermore, positive definite implies invertible (why?), so $\mathbf{A}_{k-1}$ is invertible, and by the block LDU decomposition, we have \begin{equation} \det(\mathbf{A}) = \det(\mathbf{A}_{k-1}) \det(a_{nn} - \mathbf{c}^* \mathbf{A}_{k-1}^{-1} \mathbf{c}) \end{equation} or \begin{equation} a_{nn} - \mathbf{c}^* \mathbf{A}_{k-1}^{-1} \mathbf{c} = \frac{\det(\mathbf{A})}{\det(\mathbf{A}_{k-1})} > 0. \end{equation} We use this fact in the following. For any $\mathbf{x} \in \mathbb{C}^n \setminus \{\mathbf{0}\}$, \begin{equation} \begin{aligned} \mathbf{x}^* \mathbf{A} \mathbf{x} &= \begin{bmatrix} \mathbf{x}_{k-1}^* & \overline{x}_{n} \end{bmatrix} \begin{bmatrix} \mathbf{A}_{k-1} & \mathbf{c} \\ \mathbf{c}^* & a_{kk} \end{bmatrix} \begin{bmatrix} \mathbf{x}_{k-1} \\ x_n \end{bmatrix} \\ &= \mathbf{x}_{k-1}^* \mathbf{A}_{k-1} \mathbf{x}_{k-1} + \mathbf{x}_{k-1}^* \mathbf{c} x_n + \overline{x}_n\mathbf{c}^* \mathbf{x}_{k-1} + \vert x_n \vert^2 a_{kk}. \end{aligned}. \end{equation} To employ positive definiteness of $\mathbf{A}_{k-1}$, we wish to write $\mathbf{x}^* \mathbf{A} \mathbf{x}$ in terms of \begin{equation} (\mathbf{x}_{k-1} + \mathbf{b})^* \mathbf{A}_{k-1} (\mathbf{x}_{k-1} + \mathbf{b}) = \mathbf{x}_{k-1}^* \mathbf{A} \mathbf{x}_{k-1} + \mathbf{x}_{k-1}^* \mathbf{A}_{k-1} \mathbf{b} + \mathbf{b}^* \mathbf{A}_{k-1} \mathbf{x}_{k-1} + \mathbf{b}^* \mathbf{A}_{k-1} \mathbf{b}^*, \end{equation} for the appropriate vector $\mathbf{b} \in \mathbb{C}^{(k-1)}$. It seems reasonable to take \begin{equation} \mathbf{x}_{k-1}^* \mathbf{A}_{k-1} \mathbf{b} = \mathbf{x}_{k-1}^* \mathbf{c} x_n \end{equation} or \begin{equation} \mathbf{b} = \mathbf{A}_{k-1}^{-1} \mathbf{c} x_n. \end{equation} Then, \begin{equation} \mathbf{b}^* \mathbf{A} \mathbf{b} = \overline{x}_n \mathbf{c}^* \mathbf{A}_{k-1}^{-*} \mathbf{A}_{k-1} \mathbf{A}_{k-1}^{-1} \mathbf{c} x_n = \vert x_n \vert^2 \mathbf{c}^* \mathbf{A}_{k-1}^{-1} \mathbf{c}, \end{equation} and we can write \begin{equation} \mathbf{x}^* \mathbf{A} \mathbf{x} = \underbrace{(\mathbf{x}_{k-1} + \mathbf{b})^* \mathbf{A}_{k-1} (\mathbf{x}_{k-1} + \mathbf{b})}_{>0} + \underbrace{\vert x_n \vert^2 (a_{kk} - \mathbf{c}^* \mathbf{A}_{k-1}^{-1} \mathbf{c})}_{\geq 0}, \end{equation} where the first term is strictly larger then zero as $\mathbf{A}_{k-1}$ is positive definite, and where the second term is positive by the argument above. Hence, we conclude that $\mathbf{A}$ is positive definite as well.
Finally, by induction, for any Hermitian matrix $\mathbf{A} \in \mathbb{C}^{n \times n}$ of any size, if all principal submatrices have a strictly positive determinant, then $\mathbf{A}$ is positive definite.