24
Aug 19

Sylvester's criterion

category: Matrix algebra, MT2175 Further linear algebra No Comments

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.

Post Views: 26

Leave a Reply

You must be logged in to post a comment.