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


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: