Schur complement

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

${\displaystyle L={\begin{bmatrix}I_{p}&0\\-D^{-1}C&I_{q}\end{bmatrix}}.}$

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

${\displaystyle {\begin{aligned}ML&={\begin{bmatrix}A&B\\C&D\end{bmatrix}}{\begin{bmatrix}I_{p}&0\\-D^{-1}C&I_{q}\end{bmatrix}}={\begin{bmatrix}A-BD^{-1}C&B\\0&D\end{bmatrix}}\\[4pt]&={\begin{bmatrix}I_{p}&BD^{-1}\\0&I_{q}\end{bmatrix}}{\begin{bmatrix}A-BD^{-1}C&0\\0&D\end{bmatrix}}.\end{aligned}}}$

This is analogous to an LDU decomposition. That is, we have shown that

${\displaystyle {\begin{aligned}{\begin{bmatrix}A&B\\C&D\end{bmatrix}}&={\begin{bmatrix}I_{p}&BD^{-1}\\0&I_{q}\end{bmatrix}}{\begin{bmatrix}A-BD^{-1}C&0\\0&D\end{bmatrix}}{\begin{bmatrix}I_{p}&0\\D^{-1}C&I_{q}\end{bmatrix}},\end{aligned}}}$

and inverse of M thus may be expressed involving D⁻¹ and the inverse of Schur's complement (if it exists) only as

${\displaystyle {\begin{aligned}&{\begin{bmatrix}A&B\\C&D\end{bmatrix}}^{-1}={\begin{bmatrix}I_{p}&0\\-D^{-1}C&I_{q}\end{bmatrix}}{\begin{bmatrix}\left(A-BD^{-1}C\right)^{-1}&0\\0&D^{-1}\end{bmatrix}}{\begin{bmatrix}I_{p}&-BD^{-1}\\0&I_{q}\end{bmatrix}}\\[4pt]={}&{\begin{bmatrix}\left(A-BD^{-1}C\right)^{-1}&-\left(A-BD^{-1}C\right)^{-1}BD^{-1}\\-D^{-1}C\left(A-BD^{-1}C\right)^{-1}&D^{-1}+D^{-1}C\left(A-BD^{-1}C\right)^{-1}BD^{-1}\end{bmatrix}}\\[4pt]={}&{\begin{bmatrix}\left(M/D\right)^{-1}&-\left(M/D\right)^{-1}BD^{-1}\\-D^{-1}C\left(M/D\right)^{-1}&D^{-1}+D^{-1}C\left(M/D\right)^{-1}BD^{-1}\end{bmatrix}}.\end{aligned}}}$

Cf. matrix inversion lemma which illustrates relationships between the above and the equivalent derivation with the roles of A and D interchanged.

• 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:

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

provided that AD − BC is non-zero.

• In general, if A is invertible, then

  ${\displaystyle {\begin{aligned}M&={\begin{bmatrix}I_{p}&0\\CA^{-1}&I_{q}\end{bmatrix}}{\begin{bmatrix}A&0\\0&D-CA^{-1}B\end{bmatrix}}{\begin{bmatrix}I_{p}&A^{-1}B\\0&I_{q}\end{bmatrix}},\\[4pt]M^{-1}&={\begin{bmatrix}A^{-1}+A^{-1}B(M/A)^{-1}CA^{-1}&-A^{-1}B(M/A)^{-1}\\-(M/A)^{-1}CA^{-1}&(M/A)^{-1}\end{bmatrix}}\end{aligned}}}$

whenever this inverse exists.

• When A, respectively D, is invertible, the determinant of M is also clearly seen to be given by

  ${\displaystyle \det(M)=\det(A)\det \left(D-CA^{-1}B\right)}$, respectively

  ${\displaystyle \det(M)=\det(D)\det \left(A-BD^{-1}C\right)}$,

which generalizes the determinant formula for 2 × 2 matrices.

• (Guttman rank additivity formula) If D is invertible, then the rank of M is given by

  ${\displaystyle \operatorname {rank} (M)=\operatorname {rank} (D)+\operatorname {rank} \left(A-BD^{-1}C\right)}$

• (Haynsworth inertia additivity formula) If A is invertible, then the inertia of the block matrix M is equal to the inertia of A plus the inertia of M/A.

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

${\displaystyle {\begin{aligned}Ax+By&=a\\Cx+Dy&=b\end{aligned}}}$

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

${\displaystyle \left(A-BD^{-1}C\right)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 ${\textstyle Cx+Dy=b}$ one can solve for y. This reduces the problem of inverting a ${\textstyle (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 numerically accurate.

In electrical engineering this is often referred to as node elimination or Kron reduction.

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 covariance is the symmetric positive-definite matrix

${\displaystyle \Sigma =\left[{\begin{matrix}A&B\\B^{\mathsf {T}}&C\end{matrix}}\right],}$

where ${\textstyle A\in \mathbb {R} ^{n\times n}}$ is the covariance matrix of X, ${\textstyle C\in \mathbb {R} ^{m\times m}}$ is the covariance matrix of Y and ${\textstyle B\in \mathbb {R} ^{n\times m}}$ is the covariance matrix between X and Y.

Then the conditional covariance of X given Y is the Schur complement of C in ${\textstyle \Sigma }$:[3]

${\displaystyle {\begin{aligned}\operatorname {Cov} (X\mid Y)&=A-BC^{-1}B^{\mathsf {T}}\\\operatorname {E} (X\mid Y)&=\operatorname {E} (X)+BC^{-1}(Y-\operatorname {E} (Y))\end{aligned}}}$

If we take the matrix ${\displaystyle \Sigma }$ above to be, not a covariance of a random vector, but a sample covariance, then it may have a Wishart distribution. In that case, the Schur complement of C in ${\displaystyle \Sigma }$ also has a Wishart distribution.

Let X be a symmetric matrix of real numbers given by

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

Then

• If A is invertible, then X is positive definite if and only if A and its complement X/A are both positive definite:

  ${\displaystyle X\succ 0\Leftrightarrow A\succ 0,X/A=C-B^{\mathsf {T}}A^{-1}B\succ 0.}$[4]

• If C is invertible, then X is positive definite if and only if C and its complement X/C are both positive definite:

  ${\displaystyle X\succ 0\Leftrightarrow C\succ 0,X/C=A-BC^{-1}B^{\mathsf {T}}\succ 0.}$

• If A is positive definite, then X is positive semi-definite if and only if the complement X/A is positive semi-definite:

  ${\displaystyle {\text{If }}A\succ 0,{\text{ then }}X\succeq 0\Leftrightarrow X/A=C-B^{\mathsf {T}}A^{-1}B\succeq 0.}$[4]

• If C is positive definite, then X is positive semi-definite if and only if the complement X/C is positive semi-definite:

  ${\displaystyle {\text{If }}C\succ 0,{\text{ then }}X\succeq 0\Leftrightarrow X/C=A-BC^{-1}B^{\mathsf {T}}\succeq 0.}$

The first and third statements can be derived[5] by considering the minimizer of the quantity

${\displaystyle u^{\mathsf {T}}Au+2v^{\mathsf {T}}B^{\mathsf {T}}u+v^{\mathsf {T}}Cv,\,}$

as a function of v (for fixed u).

Furthermore, since

${\displaystyle \left[{\begin{matrix}A&B\\B^{\mathsf {T}}&C\end{matrix}}\right]\succ 0\Longleftrightarrow \left[{\begin{matrix}C&B^{\mathsf {T}}\\B&A\end{matrix}}\right]\succ 0}$

and similarly for positive semi-definite matrices, the second (respectively fourth) statement is immediate from the first (resp. third) statement.

There is also a sufficient and necessary condition for the positive semi-definiteness of X in terms of a generalized Schur complement.[1] Precisely,

• ${\displaystyle X\succeq 0\Leftrightarrow A\succeq 0,C-B^{\mathsf {T}}A^{g}B\succeq 0,\left(I-AA^{g}\right)B=0\,}$ and
• ${\displaystyle X\succeq 0\Leftrightarrow C\succeq 0,A-BC^{g}B^{\mathsf {T}}\succeq 0,\left(I-CC^{g}\right)B^{\mathsf {T}}=0,}$

where ${\displaystyle A^{g}}$ denotes the generalized inverse of ${\displaystyle A}$.

• Woodbury matrix identity
• Quasi-Newton method
• Haynsworth inertia additivity formula
• Gaussian process
• Total least squares