Raising the bar

Sylvester's criterion

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

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

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

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

We can modify Exercise 1 by eliminating $latex a_{1j}$ immediately after eliminating $latex 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 $latex C=C_{m}...C_{1},$ then $latex C^{T}=C_{1}^{T}...C_{m}^{T},$ which means that premultiplication by $latex C_{i}$ should be followed by post-multiplication by $latex C_{i}^{T}.$ In this way we can make zero all off-diagonal elements. The resulting matrix $latex B=diag[d_{1},d_{2}/d_{1},$ $latex ...,d_{n}/d_{n-1}]$ is related to $latex A$ through $latex B=CAC^{T}.$

Theorem (Sylvester) Suppose that $latex A$ is a real symmetric matrix. Then $latex 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 $latex A=C^{-1}B(C^{-1})^{T}$ where $latex \det C=1.$ It remains to apply Exercise 1 above to see that $latex A$ is positive.

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

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

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

← Previous: Gaussian elimination method

Get the PDF book “Matrix Algebra” on Lulu