2
$\begingroup$

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 ?

$\endgroup$
7
  • $\begingroup$ There is a proof on Wikipedia: en.m.wikipedia.org/wiki/Sylvester%27s_criterion $\endgroup$ – sss89 May 20 at 16:43
  • 1
    $\begingroup$ @sss89 That only addresses the case of (strictly) positive definite matrices $\endgroup$ – Ben Grossmann May 20 at 16:45
  • 1
    $\begingroup$ @sss89 Also, there seems to be an issue with the "only if" direction of the proof given. $\endgroup$ – Ben Grossmann May 20 at 16:48
  • $\begingroup$ This post is relevant (but does not answer the question) $\endgroup$ – Ben Grossmann May 20 at 16:57
  • $\begingroup$ 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? $\endgroup$ – sss89 May 20 at 17:01
4
$\begingroup$

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

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-3}\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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – daw May 21 at 7:14
  • $\begingroup$ @daw: I don't see an easier one than using the coefficients of the char poly. $\endgroup$ – orangeskid May 21 at 7:21
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ There's another nice proof of this result using the existence of a decomposition $A = M^TM$ $\endgroup$ – Ben Grossmann May 20 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.