Raising the bar Sylvester's criterion follows from Gaussian diagonalization

Aug 19

Sylvester's criterion

Sylvester's criterion

Exercise 1. Suppose $A=CBC^{T},$ where $B=diag[d_{1},...,d_{n}]$ and $\det C\neq 0$ . Then $A$ is positive if and only if all $d_{i}$ are positive.

Proof. For any $x\neq 0$ we have $x^{T}Ax=x^{T}CBC^{T}x=(C^{T}x)^{T}B(C^{T}x).$ Let $y=C^{T}x\neq 0.$ Then $x^{T}Ax=y^{T}By=\sum_{j}d_{j}y_{j}^{2}.$ This is positive for all $y\neq 0$ if and only if $\min_{j}d_{j}>0.$

Exercise 2 (modified Gaussian elimination). Suppose that $A$ is a real symmetric matrix with nonzero leading principal minors $d_{1},...,d_{n}$ . Then $B=CAC^{T},$ where $B=diag[d_{1},d_{2}/d_{1},...,d_{n}/d_{n-1}]$ and $\det C=1$ .

Proof. Review the transformation applied in Exercise 1 to obtain a triangular form. In that exercise, we eliminated element $a_{21}$ below $a_{11}$ by premultiplying $A$ by the matrix $C=I-\frac{a_{21}}{a_{11}} e_{2}^{T}e_{1}.$ Now after this we can post-multiply $A$ by the matrix $C^{T}=I-\frac{a_{21}}{a_{11}}e_{1}^{T}e_{2}.$ Because of the assumed symmetry of $A,$ we have $C^{T}=I-\frac{a_{12}}{a_{11}}e_{1}^{T}e_{2},$ so this will eliminate element $a_{12}$ to the right of $a_{11}$ , see Exercise 2. Since in the first column $a_{21}$ is already $0$ , the diagonal element $a_{22}$ will not change.

We can modify Exercise 1 by eliminating $a_{1j}$ immediately after eliminating $a_{j1}.$ The right sequencing of transformations is necessary to be able to apply Exercise 1: the matrix used for post-multiplication should be the transpose of the matrix used for premultiplication. If $C=C_{m}...C_{1},$ then $C^{T}=C_{1}^{T}...C_{m}^{T},$ which means that premultiplication by $C_{i}$ should be followed by post-multiplication by $C_{i}^{T}.$ In this way we can make zero all off-diagonal elements. The resulting matrix $B=diag[d_{1},d_{2}/d_{1},$ $...,d_{n}/d_{n-1}]$ is related to $A$ through $B=CAC^{T}.$

Theorem (Sylvester) Suppose that $A$ is a real symmetric matrix. Then $A$ is positive if and only if all its leading principal minors are positive.

Proof. Let's assume that all leading principal minors are positive. By Exercise 2, we have $A=C^{-1}B(C^{-1})^{T}$ where $\det C=1.$ It remains to apply Exercise 1 above to see that $A$ is positive.

Now suppose that $A$ is positive, that is $x^{T}Ax=\sum_{i,j=1}^{n}a_{ij}x_{i}x_{j}>0$ for any $x\neq 0.$ Consider cut-off matrices $A_{k}=\left( a_{ij}\right) _{i,j=1}^{k}.$ The corresponding cut-off quadratic forms $x^{T}A_{k}x=\sum_{i,j=1}^{k}a_{ij}x_{i}x_{j},$ $k=1,...,n,$ are positive for nonzero $x\in R^{k}.$ It follows that $A_{k}$ are non-singular because if $x\in N(A_{k}),$ then $x^{T}A_{k}x=0.$ Hence their determinants $d_{k}=\det A_{k},$ $k=1,...,n,$ are nonzero . This allows us to apply the modified Gaussian elimination (Exercise 2) and then Exercise 1 with $B=diag[d_{1},...,d_{n}/d_{n-1}].$ By Exercise 1 consecutively $d_{1}>0,$ $d_{2}>0,...,$ $d_{n}>0.$

Exercise 3. $A$ is negative if and only if the leading principal minors change signs, starting with minus: $d_{1}<0,$ $d_{2}>0,$ $d_{3}<0,...$

Proof. By definition, $A$ is negative if $-A$ is positive. Because of homogeneity of determinants, when we pass from $A$ to $-A,$ the minor of order $k$ gets multiplied by $(-1)^{k}.$ Thus, by Sylvester's criterion $A$ is negative if and only if $(-1)^{k}d_{k}>0,$ as required.