Schur complement

From Wikipedia, the free encyclopedia

In linear algebra and the theory of matrices, the Schur complement (named after Issai Schur) of a block of a matrix within the larger matrix is defined as follows. Suppose A, B, C, D are respectively p×p, p×q, q×p and q×q matrices, and D is invertible. Let

$M=\left[\begin{matrix} A & B \\ C & D \end{matrix}\right]$

so that M is a (p+q)×(p+q) matrix.

Then the Schur complement of the block D of the matrix M is the p×p matrix

A - B D - 1 C .

The Schur complement arises as the result of performing a block Gaussian elimination by multiplying the matrix M from the right with the "lower triangular" block matrix

$L=\left[\begin{matrix} I_p & 0 \\ -D^{-1}C & D^{-1} \end{matrix}\right].$

Here I_p denotes a p×p unit matrix. After multiplication with the matrix L the Schur complement appears in the upper p×p block. The product matrix is

$M\cdot L=\left[\begin{matrix} A-BD^{-1}C & BD^{-1} \\ 0 & I_q \end{matrix}\right].$

The inverse of M thus may be expressed involving $D - 1$ and the inverse of Schur's complement (if it exists) only as

$\left[ \begin{matrix} A & B \\ C & D \end{matrix}\right]^{-1} = \left[ \begin{matrix} \left(A-B D^{-1} C \right)^{-1} & -\left(A-B D^{-1} C \right)^{-1} B D^{-1} \\ -D^{-1}C\left(A-B D^{-1} C \right)^{-1} & D^{-1}+ D^{-1} C \left(A-B D^{-1} C \right)^{-1} B D^{-1} \end{matrix} \right],$

or more simply put,

$\left[ \begin{matrix} A & B \\ C & D \end{matrix}\right]^{-1} = \left[ \begin{matrix} I & 0 \\ -D^{-1}C & I \end{matrix}\right] \left[ \begin{matrix} (A-BD^{-1}C)^{-1} & 0 \\ 0 & D^{-1} \end{matrix}\right] \left[ \begin{matrix} I & -BD^{-1} \\ 0 & I \end{matrix}\right].$

If M is a positive-definite symmetric matrix, then so is the Schur complement of D in M.

If p and q are both 1 (i.e. A, B, C and D are all scalars), we get the familiar formula for the inverse of a 2 by 2 matrix:

$M^{-1} = \frac{1}{AD-BC} \left[ \begin{matrix} D & -B \\ -C & A \end{matrix}\right]$

provided that the determinant $A D - B C$ is non-zero.

[edit] Application to solving linear equations

The Schur complement arises naturally in solving a system of linear equations such as

A x + B y = a

C x + D y = b

where x, a are p-dimensional column vectors, y, b are q-dimensional column vectors, and A, B, C, D are as above. Multiplying the bottom equation by $B D - 1$ and then subtracting from the top equation one obtains

$(A - BD^{-1} C) x = a - BD^{-1} b.\,$

Thus if one can invert D as well as the Schur complement of D, one can solve for x, and then by using the equation $C x + D y = b$ one can solve for y. This reduces the problem of inverting a $(p+q) \times (p+q)$ matrix to that of inverting a p×p matrix and a q×q matrix. In practice one needs D to be well-conditioned in order for this algorithm to be accurate.

[edit] Applications to probability theory and statistics

Suppose the random column vectors X, Y live in Rⁿ and R^m respectively, and the vector (X, Y) in R^n+m has a multivariate normal distribution whose variance is the symmetric positive-definite matrix

$V=\left[\begin{matrix} A & B \\ B^T & C \end{matrix}\right].$

Then the conditional variance of X given Y is the Schur complement of C in V:

$\operatorname{var}(X\mid Y)=A-BC^{-1}B^T.$

If we take the matrix V above to be, not a variance of a random vector, but a sample variance, then it may have a Wishart distribution. In that case, the Schur complement of C in V also has a Wishart distribution.