# $A$ is positive semidefinite $\iff \text{det} (B_K) \geq 0$

Let $$A \in \mathbb R^{n \times n}$$ a symmetric matrix. Show that $$A$$ is positive semidefinite $$\iff$$ all its symmetric minors are $$\geq 0$$, that means $$\det(B_K) \geq 0$$ for all $$K \subseteq \{1,\cdots,n\}$$.

(Let $$K = \{ l_1, \cdots, l_k \} \subseteq \{1,\cdots,n\}$$ where $$1 \leq l_1 < l_2 < \cdots < l_k \leq n$$. The matrix $$B_K \in \mathbb R^{k \times k}$$ is the matrix with $$(B_K)_{ij}=A_{l_il_j}$$, $$1\leq i,j \leq k$$).

$$\Longrightarrow$$ $$A$$ is symmetric matrix so by the spectral theorem, we have that $$A=U\begin{pmatrix} \lambda_1 & & \\ & \ddots \\ & & \lambda_n \end{pmatrix}U^T$$ with $$U$$ an orthogonal matrix and $$\lambda_i \geq 0$$ $$\forall i$$ because A is positive semidefinite.

We have that $$(B_K)=\begin{bmatrix} u_{l_1} \\ \cdots \\ u_{l_k} \end{bmatrix}$$ $$\begin{pmatrix} \lambda_1 & & \\ & \ddots \\ & & \lambda_n \end{pmatrix}$$ $$\begin{bmatrix} u_{l_1}^T & \cdots & u_{l_k}^T \end{bmatrix}$$, where $$u_{l_i}$$ is the $$l_i^\text{ th}$$ line of $$U$$. Since $$\begin{bmatrix} u_{l_1} \\ \cdots \\ u_{l_k} \end{bmatrix} \cdot \begin{bmatrix} u_{l_1}^T & \cdots & u_{l_k}^T \end{bmatrix}=I_k$$ then $$\det(B_K)=\det\begin{pmatrix} \lambda_1 & & \\ & \ddots \\ & & \lambda_n \end{pmatrix} = \Pi_{i=1}^n \lambda_i \geq 0$$.

Can someone help me for the $$\Longleftarrow$$ way ?

• There is a proof on Wikipedia: en.m.wikipedia.org/wiki/Sylvester%27s_criterion May 20, 2021 at 16:43
• @sss89 That only addresses the case of (strictly) positive definite matrices May 20, 2021 at 16:45
• @sss89 Also, there seems to be an issue with the "only if" direction of the proof given. May 20, 2021 at 16:48
• This post is relevant (but does not answer the question) May 20, 2021 at 16:57
• You're probably right, I'll have to think about it. BTW, I am not sure I understand the last part of your proof, how did you deduce that the determinant of the symmetric minor is the product of all eigenvalues? May 20, 2021 at 17:01

Direction 1: $$A\succeq \mathbf 0 \implies \det\big(Z_k\big)\geq 0$$
(where $$Z_k$$ refers to an arbitrary $$k\times k$$ principal submatrix).
proof:
Let the eigenvalues of $$A$$ be given as $$0\leq \lambda_n\leq \lambda_{n-1}\leq ....\leq \lambda_1$$

$$Z_k := S^T A S$$
where
$$S:= \bigg[\begin{array}{c|c|c|c|c|c|c} \mathbf e_{\sigma_{(1)}} & \cdots & \mathbf e_{\sigma_{(k)}} \end{array}\bigg]$$
(i.e. use appropriate standard basis vectors to 'grab' the desired principal submatrix)

The eigenvalues of $$Z_k$$ (Cauchy) interlace those of $$A$$ thus for all $$j\in \{1,2,...,k\}$$

$$0\leq\lambda_n\leq \lambda_j^{(Z_k)}\implies Z_k\succeq \mathbf 0$$
hence $$0\leq \prod_{j=1}^k\lambda_j^{(Z_k)}=\det\big(Z_k\big)$$

(Alternative proof not using Interlacing: consider that any principal submatrix of a symmetric PSD matrix must be symmetric PSD, by a direct quadratic form argument, and thus the principal submatrix can't have negative eigenvalues and hence $$\det\big(Z_k\big) \geq 0$$.)

Direction 2: all $$\det\big(Z_k\big) \geq 0 \implies A \succeq \mathbf 0$$

proof: use strong induction on $$n$$

Base case:
The criterion is obvious for $$n=1$$.

Inductive case:
For $$m\in \big\{1,2,...,n-1\big\}$$: we know this is true for all $$m \times m$$ real symmetric matrices but need to show it is true for $$n\times n$$ real symmetric matrices .
Let $$\text{rank}\big(A\big) = r\lt n$$
Then $$A$$ is congruent to a particularly nice matrix. I.e.
$$W^T A W = \begin{bmatrix} C_{r\times r} &\mathbf {0}\\ \mathbf {0}& \mathbf {0}_{n-r \times n-r} \end{bmatrix}$$
where $$C_{r\times r}$$ is a principal submatrix of $$A$$ and $$C_{r\times r}\succeq \mathbf 0$$ by application of induction hypothesis
$$\implies W^TA W\succeq \mathbf 0$$.
Ref: Prove the existence of a principal submatrix of order $r$ in $M\in\Bbb F^{n\times n}, M=-M^T,\ \operatorname{rank}(M)=r$

Since $$A$$ and $$W^T AW$$ have the same signature, we know that $$A\succeq \mathbf 0$$.

= = = =
Finally, consider $$\text{rank}\big(A\big) = n$$
We have $$\det\big(A\big)\geq 0$$ and since A is non-singular this means $$\det\big(A\big)\gt 0$$

Consider the leading $$n-1\times n-1$$ submatrix, i.e. $$Z:=S^T A S$$ with
$$S:= \bigg[\begin{array}{c|c|c|c|c|c|c} \mathbf e_{1} & \cdots & \mathbf e_{n-1} \end{array}\bigg]$$

Applying Cauchy Interlacing we have
$$\lambda_{n}\leq \lambda_{n-1}^{(Z)}\leq \lambda_{n-1}\leq \lambda_{n-2}^{(Z)} \leq \lambda_{n-2}\leq ... \leq \lambda_{1}^{(Z)}\leq \lambda_1$$
By induction hypothesis we know $$Z\succeq \mathbf 0\implies \lambda_i\geq \lambda_{n-1}^{(Z)}\geq 0$$ for $$i\in \{1,2,..,n-1\}$$. And since $$0\lt \det\big(A\big)=\lambda_1\cdot ...\cdot \lambda_{n-1}\cdot \lambda_{n}$$ we know $$\lambda_n\gt 0\implies A\succeq \mathbf 0$$

(Alternative finish for $$\text{rank}\big(A\big) = n$$ case without using Interlacing. The leading $$n-1 \times n-1$$ principal submatrix $$Z \succeq \mathbf 0$$ by induction hypothesis and $$\det\big(A\big)\gt 0$$. Thus $$A$$ has an even number of negative eigenvalues; and if that number is non-zero we contradict the fact that $$Z\succeq \mathbf 0$$; this is mechanically the same as the standard proof for Sylvester's Criterion for PD matrices, see e.g. here: Characterization of positive definite matrix with principal minors )

The characteristic polynomial of the matrix $$A$$ has coefficients expressed in terms of the symmetric (or principal) minors. If all the symmetric minors are $$\ge 0$$, then the characteristic polynomial has alternating coefficients. This implies that all of its roots are $$\ge 0$$, and this in turns implies that $$A$$ is positive semidefinite.

Alternate solution: check that for all $$\epsilon > 0$$ all the leading minors of $$A + \epsilon I$$ are $$> 0$$. This implies $$A+ \epsilon I$$ is positive definite. Now take $$\epsilon \to 0$$.

The latter approach also works to show that if $$A$$ is positive semi-definite then $$\det A$$ ( and so all the principal minors) are $$\ge 0$$.

• Do you have an easy proof that $\det (A+\epsilon I)>0$ for $\epsilon>0$ small? I thought of this as well, and I have the impression that one has to discuss all coefficients of the characteristic polynomial, much like in the first paragraph of your answer.
– daw
May 21, 2021 at 7:14
• @daw: I don't see an easier one than using the coefficients of the char poly. May 21, 2021 at 7:21

Here is a proof of the implication: positive semidefinite implies all symmetric minors have non-negative determinant.

In fact, I proof that $$B_K$$ is positive semidefinite as well. Let $$K=\{l_1\dots l_k\}$$ be an index set, $$x$$ a vector in $$\mathbb R^k$$. Define a new vector $$y\in \mathbb R^n$$ by: $$y_{l_i}=x_i$$ for $$i=1\dots k$$, all other entries of $$y$$ are set to zero. Then $$0 \le y^TAy = x^TB_Kx.$$ As $$x$$ was arbitrary, it follows $$B_K$$ is positive semidefinite and thus has non-negative determinant.

I do not know how to prove the other direction.

• There's another nice proof of this result using the existence of a decomposition $A = M^TM$ May 20, 2021 at 17:41