Ngô Quốc Anh

July 26, 2009

On the positive definite property of the Schur complement

Filed under: Các Bài Tập Nhỏ, Linh Tinh, Nghiên Cứu Khoa Học — Tags: — Ngô Quốc Anh @ 0:48

The following question was proposed in the NUS Q.E. in 2009: Given matrices $A \in \mathbb R^{n \times n}$, $B \in \mathbb R^{n \times m}$ and $C \in \mathbb R^{m \times m}$. Suppose $A$ and $C$ are symmetric. Consider the following matrices $\displaystyle H = \left( {\begin{array}{*{20}{c}} A&B \\ {{B^T}}&C \end{array}} \right), \qquad S = C - {B^T}{A^{ - 1}}B.$

Show that $H$ is positive definite if and only if $A$ and $S$ are positive definite.

In the literature, the matric $S$ is called the Schur complement, usually, it is denoted by $H|A$ with respect to $A$. In other word, $H|C$ is of the form $A-B^TC^{-1}B$. It is worth noting that the letter $H$ used in the above notation indicates the full matrix $H$, roughly speaking, by $H|A$ we mean the Schur complement of $H$ with respect to $A$.

Throughout this entry, by $A >0$ (resp. $A \geq 0$) we mean that $A$ is positive definite (resp. positive semi-definite). In order to solve the above problem, one needs the following matrix identity, the Aitken block-diagonalization formula, $\displaystyle\left( {\begin{array}{*{20}{c}} I&0 \\ { - {B^T}{A^{ - 1}}}&I \end{array}} \right)\left( {\begin{array}{*{20}{c}} A&B \\ {{B^T}}&C \end{array}} \right)\left( {\begin{array}{*{20}{c}} I&{ - {A^{ - 1}}B} \\ 0&I \end{array}} \right) = \left( {\begin{array}{*{20}{c}} A&0 \\ 0&{H|A} \end{array}} \right).$

Now we assume $A >0$ and $H|A >0$. Then the following property $\displaystyle \left( {\begin{array}{*{20}{c}} A & 0 \\ 0 & {C - {B^T}{A^{ - 1}}B} \\ \end{array} } \right) > 0$

holds true. Indeed, since $\displaystyle\left( {\begin{array}{*{20}{c}} {{A^{n \times n}}}&0 \\ 0&{{C^{m \times m}} - {B^T}{A^{ - 1}}B} \end{array}} \right) \in \text{Mat}(n + m)$

then for every $\displaystyle\left( {\begin{array}{*{20}{c}} x&y \end{array}} \right) \in \text{Mat}(n + m)$

one has $\displaystyle\left( {\begin{array}{*{20}{c}} {{x^T}}&{{y^T}} \end{array}} \right)\left( {\begin{array}{*{20}{c}} A&0 \\ 0&{M|A} \end{array}} \right)\left( {\begin{array}{*{20}{c}} x&y \end{array}} \right) = {x^T}Ax + {y^T}(M|A)y.$

Note that at least $x$ or $y$ is not a zero vector so that $\displaystyle {x^T}Ax + {y^T}\left( {C - {B^T}{A^{ - 1}}B} \right)y > 0$

which proves the positive definite property of $\displaystyle \left( {\begin{array}{*{20}{c}} A & 0 \\ 0 & {C - {B^T}{A^{ - 1}}B} \\ \end{array} } \right).$

Now by means of the above matrix identity we claims that $H>0$.

Conversely, for every $x \in \mathbb R^n$, one has $\displaystyle 0 < \left( {\begin{array}{*{20}{c}} {{x^T}}&0 \end{array}} \right)H\left( {\begin{array}{*{20}{c}} x&0 \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {{x^T}}&0 \end{array}} \right)\left( {\begin{array}{*{20}{c}} A&B \\ {{B^T}}&C \end{array}} \right)\left( {\begin{array}{*{20}{c}} x&0 \end{array}} \right) = {x^T}Ax$

whenever $x \ne 0$. Thus, this and the fact that $A$ is symmetric implies that $A >0$. As a consequence, $A^{-1}$ exists which helps us to say that $S$ is well-defined.

Now with the help of the matrix identity, one gets $\displaystyle\left( {\begin{array}{*{20}{c}} 0&{{y^T}} \end{array}} \right)\left( {\begin{array}{*{20}{c}} I&0 \\ { - {B^T}{A^{ - 1}}}&I \end{array}} \right)\left( {\begin{array}{*{20}{c}} A&B \\ {{B^T}}&C \end{array}} \right)\left( {\begin{array}{*{20}{c}} I&{ - {A^{ - 1}}B} \\ 0&I \end{array}} \right)\left( {\begin{array}{*{20}{c}} 0&y \end{array}} \right) = \left( {\begin{array}{*{20}{c}} 0&{{y^T}} \end{array}} \right)\left( {\begin{array}{*{20}{c}} A&0 \\ 0&{H|A} \end{array}} \right)\left( {\begin{array}{*{20}{c}} 0&y \end{array}} \right).$

Note that, the left left side of the above identity is nothing but $\displaystyle\underbrace {\left( {\begin{array}{*{20}{c}} 0&{{y^T}} \end{array}} \right)\left( {\begin{array}{*{20}{c}} I&0 \\ { - {B^T}{A^{ - 1}}}&I \end{array}} \right)}_D\left( {\begin{array}{*{20}{c}} A&B \\ {{B^T}}&C \end{array}} \right){D^T}$

which is positive by the assumption provided $y \ne 0$. Hence, if $y \ne 0$ is arbitrary, the right hand side equals to $\displaystyle {{y^T}\left( {C - {B^T}{A^{ - 1}}B} \right)y}$

which proves that $S>0$. The proof is complete.

If I have time, I will provide another proof using the Sylvester’s Law of Inertia. For your convenience regarding to the Schur complement, I prefer you to the book entitled THE SCHUR COMPLEMENT AND ITS APPLICATIONS due to Fuzhen Zhang (edt.) for details.

1 Comment »

1. Render your god damned LaTeX. This is the fucking 21st century.

Comment by Damned — January 31, 2011 @ 16:15

This site uses Akismet to reduce spam. Learn how your comment data is processed.