1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ – ZFR Mar 5 '20 at 2:53
  • $\begingroup$ @ZFR:Yes, that is correct. $\endgroup$ – P. Lawrence Mar 5 '20 at 3:01
  • $\begingroup$ 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! $\endgroup$ – ZFR Mar 5 '20 at 13:47
  • $\begingroup$ I would be very grateful if you can give more details about RHS of $\det(tI+M)$, please. $\endgroup$ – ZFR Mar 5 '20 at 16:14
  • 1
    $\begingroup$ @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. $\endgroup$ – P. Lawrence Mar 7 '20 at 20:30
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – ZFR Mar 25 '20 at 19:42
  • $\begingroup$ @ZFR I updated the proof. $\endgroup$ – Arin Chaudhuri Mar 30 '20 at 19:11

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.