---
title: Shur complement
tags: Linear algebra
GA: G-77TT93X4N1
---

# Shur complement

## Derivation

We consider a square matrix with block structure

$$
\tag{1}
\begin{bmatrix}
A & B \\
C & D
\end{bmatrix}
\begin{bmatrix}
X\\
Y
\end{bmatrix}=
\begin{bmatrix}
U\\
V
\end{bmatrix}.
$$
If $A$ is invertible, we can apply one-step block Gaussian elimination to eliminate $C$. We mulplity both side by an elimination matrix as follows:
$$
\begin{bmatrix}
I & 0 \\
-CA^{-1} & I
\end{bmatrix}
\begin{bmatrix}
A & B \\
C & D
\end{bmatrix}
\begin{bmatrix}
X\\
Y
\end{bmatrix}=
\begin{bmatrix}
I & 0 \\
-CA^{-1} & I
\end{bmatrix}
\begin{bmatrix}
U\\
V
\end{bmatrix}.
$$
Direct calculation leads to
$$
\tag{2}
\begin{bmatrix}
A & B \\
0 & D-CA^{-1}B
\end{bmatrix}
\begin{bmatrix}
X\\
Y
\end{bmatrix}=
\begin{bmatrix}
U\\
V-CA^{-1}U
\end{bmatrix}.
$$

Therefore, to solve (1) is equivalent to solve (2), and we can split the procedure into two steps:
1. Solve the following system to find $Y$:
$$
\tag{3}
(D-CA^{-1}B) Y = V-CA^{-1}U.
$$
2. Solve the following system to find $X$:
$$
\tag{4}
AX = U-BY.
$$

---

## Example

Consider solving the linear system
$$
\tag{5}
\left[\begin{array}{@{}c|c@{}}
I_{10}
& B \\
\hline
C & D
\end{array}\right]
\begin{bmatrix}
x_1\\
\vdots\\
x_{12}
\end{bmatrix}=
\begin{bmatrix}
b_1\\
\vdots\\
b_{12}
\end{bmatrix},
$$

where $I_{10}$ is the $10\times 10$ identity matrix and
$$
B\in\mathbb{M}_{10\times 2}, \quad
C\in\mathbb{M}_{2\times 10}, \quad
D\in\mathbb{M}_{2\times 2}.
$$

Since $(I_{10})^{-1}x = x$ for any $x$. We can take advantages of the Schur complement to solve this system. We solve the system in 2 steps:
1. Solve a $2\times 2$ system:
$$
\tag{6}
(D-CB) \begin{bmatrix}
x_{11}\\
x_{12}
\end{bmatrix} = \begin{bmatrix}
b_{11}\\
b_{12}
\end{bmatrix}-C\begin{bmatrix}
b_{1}\\
\vdots\\
b_{10}
\end{bmatrix}.
$$
2. Calculate the remaining part of the solution directly:
$$
\tag{7}
\begin{bmatrix}
x_{1}\\
\vdots\\
x_{10}
\end{bmatrix} = \begin{bmatrix}
b_{1}\\
\vdots\\
b_{10}
\end{bmatrix}-B\begin{bmatrix}
x_{11}\\
x_{12}
\end{bmatrix}.
$$

---

## Remark

* Schur complement is useful when the linear system $Ax=b$ can be solved easily.
* (NOTE) Never compute $A^{-1}$. To evaluate $A^{-1}b$, we solve $Ax=b$.