GeezerVison

The Schur complement is a key tool in the fields of linear algebra, the theory of matrices, numerical analysis, and statistics.

It is defined for a block matrix. Suppose p, q are nonnegative integers such that p + q > 0, and suppose A, B, C, D are respectively p × p, p × q, q × p, and q × q matrices of complex numbers. Let $M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]$ so that M is a (p + q) × (p + q) matrix.

If D is invertible, then the Schur complement of the block D of the matrix M is the p × p matrix defined by $M/D:=A-B{D}^{-1}C.$ If A is invertible, the Schur complement of the block A of the matrix M is the q × q matrix defined by $M/A:=D-C{A}^{-1}B.$ In the case that A or D is singular, substituting a generalized inverse for the inverses on M/A and M/D yields the generalized Schur complement.

The Schur complement is named after Issai Schur^[1] who used it to prove Schur's lemma, although it had been used previously.^[2] Emilie Virginia Haynsworth was the first to call it the Schur complement.^[3] The Schur complement is sometimes referred to as the Feshbach map after a physicist Herman Feshbach.^[4]

The Schur complement arises when performing a block Gaussian elimination on the matrix M. In order to eliminate the elements below the block diagonal, one multiplies the matrix M by a block lower triangular matrix on the right as follows: $\begin{array}{cc}& M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]\to \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}$ where I_p denotes a p×p identity matrix. As a result, the Schur complement $M/D=A-B{D}^{-1}C$ appears in the upper-left p×p block.

Continuing the elimination process beyond this point (i.e., performing a block Gauss–Jordan elimination), $\begin{array}{cc}& \left[\begin{array}{cc}A-B{D}^{-1}C& B\\ 0& D\end{array}\right]\to \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}$ leads to an LDU decomposition of M, which reads $\begin{array}{cc}M& =\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}$ Thus, the inverse of M may be expressed involving D⁻¹ and the inverse of Schur's complement, assuming it exists, as $\begin{array}{cc}{M}^{-1}={\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]}^{-1}=& {\left(\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]\right)}^{-1}\\ =& \left[\begin{array}{cc}{I}_p& 0\\ -D^{-1}C& I_q\end{array}\right]\left[\begin{array}{cc}{(A-B{D}^{-1}C)}^{-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}{(A-B{D}^{-1}C)}^{-1}& -{(A-B{D}^{-1}C)}^{-1}B{D}^{-1}\\ -D^{-1}C{(A-B{D}^{-1}C)}^{-1}& D^{-1}+D^{-1}C{(A-B{D}^{-1}C)}^{-1}B{D}^{-1}\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 relationship comes from the elimination operations that involve D⁻¹ and M/D. An equivalent derivation can be done with the roles of A and D interchanged. By equating the expressions for M⁻¹ obtained in these two different ways, one can establish the matrix inversion lemma, which relates the two Schur complements of M: M/D and M/A (see "Derivation from LDU decomposition" in Woodbury matrix identity § Alternative proofs).

• 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{array}{cc}D& -B\\ -C& A\end{array}\right]$

provided that AD − BC is non-zero.

• In general, if A is invertible, then

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

whenever this inverse exists.

• (Schur's formula) When A, respectively D, is invertible, the determinant of M is also clearly seen to be given by

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

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

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

$\mathrm{rank}\left(M\right)=\mathrm{rank}\left(D\right)+\mathrm{rank}(A-B{D}^{-1}C)$

• (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.
• (Quotient identity) $A/B=\left(\right(A/C)/(B/C\left)\right)$.^[5]
• The Schur complement of a Laplacian matrix is also a Laplacian matrix.^[6]

The Schur complement arises naturally in solving a system of linear equations such as^[7]

$\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}u\\ v\end{array}\right]$.

Assuming that the submatrix $A$ is invertible, we can eliminate $x$ from the equations, as follows.

$x=A^{-1}(u-By).$

Substituting this expression into the second equation yields

$(D-C{A}^{-1}B)y=v-C{A}^{-1}u.$

We refer to this as the reduced equation obtained by eliminating $x$ from the original equation. The matrix appearing in the reduced equation is called the Schur complement of the first block $A$ in $M$:

$S\stackrel{def}{=}D-C{A}^{-1}B$.

Solving the reduced equation, we obtain

$y=S^{-1}(v-C{A}^{-1}u).$

Substituting this into the first equation yields

$x=(A^{-1}+A^{-1}B{S}^{-1}C{A}^{-1})u-A^{-1}B{S}^{-1}v.$

We can express the above two equation as:

$\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{cc}{A}^{-1}+A^{-1}B{S}^{-1}C{A}^{-1}& -A^{-1}B{S}^{-1}\\ -S^{-1}C{A}^{-1}& S^{-1}\end{array}\right]\left[\begin{array}{c}u\\ v\end{array}\right].$

Therefore, a formulation for the inverse of a block matrix is:

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

In particular, we see that the Schur complement is the inverse of the $2,2$ block entry of the inverse of $M$.

In practice, one needs $A$ to be well-conditioned in order for this algorithm to be numerically accurate.

This method is useful in electrical engineering to reduce the dimension of a network's equations. It is especially useful when element(s) of the output vector are zero. For example, when $u$ or $v$ is zero, we can eliminate the associated rows of the coefficient matrix without any changes to the rest of the output vector. If $v$ is null then the above equation for $x$ reduces to $x=(A^{-1}+A^{-1}B{S}^{-1}C{A}^{-1})u$, thus reducing the dimension of the coefficient matrix while leaving $u$ unmodified. This is used to advantage in electrical engineering where it is 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

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

where $A\in {ℝ}^{n\times n}$ is the covariance matrix of X, $C\in {ℝ}^{m\times m}$ is the covariance matrix of Y and $B\in {ℝ}^{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 $\Sigma$:^[8]

$\begin{array}{cc}\mathrm{Cov}(X\mid Y)& =A-B{C}^{-1}{B}^T\\ E(X\mid Y)& =E\left(X\right)+B{C}^{-1}(Y-E(Y\left)\right)\end{array}$

If we take the matrix $\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 $\Sigma$ also has a Wishart distribution.

Let X be a symmetric matrix of real numbers given by $X=\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right].$ Then by the Haynsworth inertia additivity formula, we find

• If A is invertible, then X is positive definite if and only if A and its complement X/A are both positive definite:^[2]: 34

$X\succ 0\iff A\succ 0,X/A=C-B^T{A}^{-1}B\succ 0.$

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

$X\succ 0\iff C\succ 0,X/C=A-B{C}^{-1}{B}^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:^[2]: 34

$\text{If }A\succ 0,\text{ then }X⪰0\iff X/A=C-B^T{A}^{-1}B⪰0.$

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

$\text{If }C\succ 0,\text{ then }X⪰0\iff X/C=A-B{C}^{-1}{B}^T⪰0.$

The first and third statements can also be derived^[7] by considering the minimizer of the quantity $u^{T}Au+2v^T{B}^{T}u+v^{T}Cv,$ as a function of v (for fixed u).

Furthermore, since $\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right]\succ 0⟺\left[\begin{array}{cc}C& B^T\\ B& A\end{array}\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.^[2] Precisely,

• $X⪰0\iff A⪰0,C-B^T{A}^{g}B⪰0,(I-A{A}^g)B=0$ and
• $X⪰0\iff C⪰0,A-B{C}^g{B}^T⪰0,(I-C{C}^g)B^T=0,$

where $A^g$ denotes a generalized inverse of $A$.

• Woodbury matrix identity
• Quasi-Newton method
• Haynsworth inertia additivity formula
• Gaussian process
• Total least squares
• Guyan reduction in computational mechanics