Let $A\in\mathbb C^{n\times n}$ be a Hermitian matrix such that all its principal minors are non-negative (i.e. for $B=\left(a_{l_il_j}\right)_{1≤i,j≤k}$ with $1≤l_1<…<l_k≤n$ we have $\det(B)≥0$). Then how to show that $A$ is positive semi-definite?
I thought maybe we could use induction since the condition is also satisfied for every submatrix, but I couldn't find an easy way. Can prove it elegantly?
Best Answer
Here is one way to prove the statement by mathematical induction. The base case $n=1$ is trivial. In the inductive step, let $B$ be any principal submatrix of $A$ and define $f(t)=\det(B+tI)$. By Jacobi's formula, $f'(t)=\operatorname{tr}\left(\operatorname{adj}(B+tI)\right)$. Since the diagonal entries of $\operatorname{adj}(B+tI)$ are some proper principal minors of $A+tI$, and by induction assumption, all proper principal submatrices of $A$ are positive semidefinite, $f'(t)$ must be positive whenever $t>0$. It follows that $f$ is strictly increasing on $[0,\infty)$. Consequently, $f(t)>f(0)=\det(B)\ge0$ for all $t>0$.
Hence all principal minors of $A+tI$ are positive when $t>0$. By the original Sylvester's criterion for positive definite matrices, $A+tI$ is positive definite. Taking $t\to0^+$, we conclude that $A$ is positive semidefinite.
Edit. The statement can be proved easily without using mathematical induction.
Let $B$ be any $m\times m$ principal submatrix of $A$ (this includes the case where $m=n$ and $B=A$) and $t>0$. Then $\det(B+tI)=t^m+\sum_{k=1}^m s_k(B)t^{m-k}$ where $s_k(B)$ is the sum of all $k\times k$ principal minors of $B$. Since each principal minor of $B$ is a principal minor of $A$, $s_k(B)$ is nonnegative. Therefore $\det(B+tI)\ge t^m>0$. In other words, all principal minors of $A+tI$ are positive. Hence $A+tI$ is positive definite, by Sylvester's criterion for positive definite matrices. Consequently, $A=\lim_{t\to0^+}(A+tI)$ is positive semidefinite.