# Criterion for positive semi-definite quadratic function in terms of $2^n-1$ principal minors

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.

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.

• Regarding Lemma 1 since some $d_i$ is negative then I can take $v$ to be the vector with $i$th coordinate 1 and other are zero, right? – ZFR Mar 5 '20 at 2:53
• @ZFR:Yes, that is correct. – P. Lawrence Mar 5 '20 at 3:01
• Let me ask you one more question: could you clarify the formula for $\det(tI+M)$? I didn't get how you derived the RHS of it? Seems unclear to me. Thanks! – ZFR Mar 5 '20 at 13:47
• I would be very grateful if you can give more details about RHS of $\det(tI+M)$, please. – ZFR Mar 5 '20 at 16:14
• @ZFR: I wish I could say I came up with the proof by personal brilliance but in fact I took it from ALGEBRA A Text-Book of Determinants, Matrices, and Algebraic Forms by W. L. Ferrar, an old book that has aged very well. I treasure my copy, which was the first mathematics book I ever bought, other than a course text, in 1961. – P. Lawrence Mar 7 '20 at 20:30

Claim: If all principal minors of $$A$$ are non-negative then $$A$$ is positive semidefinite.

Proof: Let $$S_k$$ denote the sum of all the k principal minors of $$A$$ and let $$\lambda_1,\dots,\lambda_n$$ denote the eigenvalues of $$A$$ which are real as $$A$$ is symmetric.

Define the polynomial $$p$$ as $$p(t)= \det(tI + A)$$.

$$p$$ is monic and $$(-1)^np(-t)$$ is the characteristic polynomial of $$A$$ from which it follows $$p(t) = (t+ \lambda_1)\dots(t+\lambda_n).$$

Let $$e_i$$ denote the vector with $$1$$ at the ith position and zero elsewhere. Let $$a_i$$ denote the ith column of $$A$$, then

$$tI + A = \begin{bmatrix} te_1 + a_1 & te_2 + a_2 & \dots & te_n + a_n \end{bmatrix}.$$

By multilinearity of the determinant $$p(t) = \sum_{r=0}^n t^r S_{n-r}$$ where $$S_k$$ denotes the sum of all principal minors of $$A$$ of order $$k$$.

Suppose all principal minors are non-negative, then $$S_k \geq 0$$ for all $$k$$.

Consequently the polynomial $$p(x) = (x+\lambda_1)(x+\lambda_2)\dots (x+\lambda_n) = x^n + S_{1}x^{n-1} + \dots + S_{n-1}x + S_n$$ has only non-negative coefficients. This means $$p(x) > 0$$ for $$x >0$$ so no real root of $$p(x)$$ can be larger than $$0$$. But all the roots of $$p(x)$$ are real, and equal the $$-\lambda_i$$'s, so we must have$$-\lambda_i \leq 0$$ or $$\lambda_i \geq 0$$ for all $$i$$. (This is from here.) Hence $$A$$ is positive semi-definite as all its eigenvalues are zero or larger.

Conversely let $$A$$ be positive semi-definite. And let $$B$$ be any principal submatrix of $$A$$, then $$B$$ is positive semi-definite as $$x^TBx \geq 0$$ for all $$x$$, and hence its eigenvalues are non-negative, and hence $$\det(B) \geq 0.$$

• You know there is one moment in your proof which seems very unclear to me. By $S_r$ you denoted the sum of all principal minors of the size $r$. Then somehow you got the different expression for $S_r$ through eigenvalues. You really need to clarify this moment. It is not so obvious. – ZFR Mar 25 '20 at 19:42
• @ZFR I updated the proof. – Arin Chaudhuri Mar 30 '20 at 19:11