Let $f:V\to \mathbb{R}$ be a quadratic function and $V$ is a vector space with $\dim V=n$. We say that $f$ is positive semi-definite if for all $x \in V$ we have $f(x)\geq 0$.
I know Sylvester's law which states the following: $f$ is positive definite iff 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, where $M$ is a matrix of $f$. In other words, all of the leading principal minors must be positive.
I need to show that $f$ is positive semi-definite iff all the principal minors (we have only $2^n-1$ of them) are non-negative.
I was not able to find the proof of this in MSE.
So I would be very grateful if someone can give detailed proof of this fact.
Best Answer
Here's an outline of the proof that a real square symmetric matrix is positive semi-definite iff every principal minor $\ge 0.$ Whenever I write matrices and/or row/column matrices as being multiplied, there is an implicit assumption that the sizes are appropriate for multiplication. $$*$$ Lemma1: If $M$ is a real square symmetric matrix with negative determinant then $$w^TMw<0 \text { for some column-vector } w \ne 0 $$
Proof: For some invertible matrix $P$, $$P^TMP= \text {diag}(d_1,...,d_n).$$ Taking determinants, we see that at least one $d_i$ must be negative. Thus $$v^TP^TMPv<0$$ for some $v \ne 0.$ Let $w=Pv$ Q.E.D. $$*$$ Lemma 2: If $A$ is a real $n \times n$ symmetric matrix and $v^TAv \ge 0$ for all column vectors, then every principal minor of $A$ is non-negative. $$*$$ Proof: Suppose $M$ is an $s \times s$ principal sub-matrix of $A $ where $1 \le s \le n$ such that $\det M<0.$ Let $w \ne 0$ be such that $w^TMw<0 $ Let $w’$ be a column-vector of size $n$ obtained by by using the same entries as those in $w$ for indices that occur for $M$ and putting all other entries =0. Then $$w’^TAw’=w^TMw<0$$, a contradiction. Q.E.D. $$*$$ Lemma 3: If $A$ is a real $n \times n$ symmetric matrix and every principal minor of $A$ is non-negative, then $A$ is positive semi-definite. $$*$$ Proof: We assert that if $t>0$ then $tI+A$ is positive-definite. Consider the determinant of the upper left $s \times s$ corner of $tI+A$ where $1 \le s \le n$. It is $\det(tI+M)$ where $M $ is the upper left $s \times s $ corner of $A$. Note that every principal minor of $M$ is a principal minor of $A$. Then $$\det(tI+M)=t^s+\sum_{i=1}^s{}(\sum \text {principal minors of order $i$ of $M$ })t^{s-i}>0 $$ which proves our assertion. Suppose $$v^TAv=-c \text { where }c>0.$$ Then $v \ne 0 $ Let $$\xi=\frac{c}{v \bullet v} $$ which is the same as $$\xi v^TIv=c$$ Thus $$v^TAv=-\xi v^TIv$$ $$v^T(\xi I+A)v=0$$, a contradiction. Q.E.D.