Schur Complement

Overview

In this note I would review the idea of Schur complement and its application in calculating the matrix inverse lemma and some properties.

Schur Complement

Schur complement naturally comes out when we do Gaussian elimination for an invertible square matrix $M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]$, where $A,B,C,D$ are $p\times p$, $p\times q$, $q\times p$, $q\times q$. First we do column multiplication, which is the left multiplication to get the upper triangular form.

$$\begin{array}{r}\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]\left[\begin{array}{cc}{I}_p& 0\\ -D^{-1}C& I_q\end{array}\right]=\left[\begin{array}{cc}A-B{D}^{-1}C& B\\ 0& D\end{array}\right]\end{array}$$

The first entry of the upper triangular form is Schur complement. Continue the Gaussian elimination, we have

$$\begin{array}{rl}\left[\begin{array}{cc}{I}_p& -B{D}^{-1}\\ 0& I_q\end{array}\right]\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]\left[\begin{array}{cc}{I}_p& 0\\ -D^{-1}C& I_q\end{array}\right]& =\left[\begin{array}{cc}{I}_p& -B{D}^{-1}\\ 0& I_q\end{array}\right]\left[\begin{array}{cc}A-B{D}^{-1}C& B\\ 0& D\end{array}\right]\\ & =\left[\begin{array}{cc}A-B{D}^{-1}C& 0\\ 0& D\end{array}\right]\end{array}$$

Rearrange we have a UDL decomposition

$$\begin{array}{r}\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]=\left[\begin{array}{cc}{I}_p& B{D}^{-1}\\ 0& I_q\end{array}\right]\left[\begin{array}{cc}A-B{D}^{-1}C& 0\\ 0& D\end{array}\right]\left[\begin{array}{cc}{I}_p& 0\\ D^{-1}C& I_q\end{array}\right]\end{array}$$

Usually, we write $M/D=A-B{D}^{-1}C$ as the symbol for Schur complement.

Application of Schur Complement

The common application of Schur Complement is to calculate the matrix inverse:

$$\begin{array}{rl}{\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]}^{-1}& =\left[\begin{array}{cc}{I}_p& 0\\ -D^{-1}C& I_q\end{array}\right]\left[\begin{array}{cc}(M/D{)}^{-1}& 0\\ 0& D^{-1}\end{array}\right]\left[\begin{array}{cc}{I}_p& -B{D}^{-1}\\ 0& I_q\end{array}\right]\\ & =\left[\begin{array}{cc}(M/D{)}^{-1}& 0\\ -D^{-1}C(M/D{)}^{-1}& D^{-1}\end{array}\right]\left[\begin{array}{cc}{I}_p& -B{D}^{-1}\\ 0& I_q\end{array}\right]\\ & =\left[\begin{array}{cc}(M/D{)}^{-1}& -(M/D{)}^{-1}B{D}^{-1}\\ -D^{-1}C(M/D{)}^{-1}& D^{-1}+D^{-1}C(M/D{)}^{-1}B{D}^{-1}\end{array}\right]\end{array}$$

The above formula is called matrix inversion lemma, it has a lot of application in calculating the conditional and marginal distribution of the Gaussian distribution.

Another application of the Schur complement lemma is in matrix inequality, it’s an useful tool to construct a linear matrix inequality for conic programming. Consider the case when $M$ is a symmetric and real matrix, given by

$$\begin{array}{r}M=\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right]\end{array}$$

Then

• If $M\succ 0$ and $C$ is invertible, then $M/C\succ 0$ and $C\succ 0$ And if we use the following identity

$$\begin{array}{r}\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right]\succ 0\iff \left[\begin{array}{cc}C& B^T\\ B& A\end{array}\right]\succ 0\end{array}$$

This can be easily verified by taking the UDL decomposition of the matrix

$$\begin{array}{r}\left[\begin{array}{cc}C-B^T{A}^{-1}B& 0\\ 0& A\end{array}\right]\end{array}$$

Then

• If $M\succ 0$ and $A$ is invertible, then $M/A\succ 0$ and $A\succ 0$.

One can check the paper LMI for Physically Consistent Parameter Identification, the authors use the Schur complement to construct a conic programming problem.

Reference

• Schur Complement Wiki