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

Question

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 ?

Answer 1

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 )

Answer 2

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.

Answer 3

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