# Block Matrix Inversion

Here are some formula for matrix inversion.

Lemma 1: For a block matrix $M=\begin{pmatrix}A & B \\C &D\end{pmatrix}$,
$M^{-1}=\begin{pmatrix}(A-B D^{-1} C)^{-1}& -A^{-1}B(D-CA^{-1}B)^{-1}\\-(D-CA^{-1}B)^{-1}CA^{-1}&(D-CA^{-1}B)^{-1}\end{pmatrix}$

$=\begin{pmatrix}A^{-1}+A^{-1}BS^{-1}CA^{-1}& -A^{-1}BS^{-1}\\-S^{-1}CA^{-1}&S^{-1}\end{pmatrix}$,
where $S=D-CA^{-1}B$ is basically the Schur's
complement of block $A$.

Proof: Let $M^{-1}=\begin{pmatrix}E&F\\G&H\end{pmatrix}$, $M M^{-1}=1$ gives us

$AE+BG=I$
$AF+BH=0$
$CE+DG=0$
$CF+DH=I$

From the four equations, we have
$E=(A-BD^{-1}C)^{-1}$
$F=-A^{-1}B(D-CA^{-1}B)$
$G=-D^{-1}C(A-BD^{-1}C)^{-1}$
$H=(D-CA^{-1}B)^{-1}$

And similarly from $M^{-1}M=I$, we have

$E=(A-BD^{-1}C)^{-1}$
$F=-(A-BD^{-1}C)^{-1}BD^{-1}$
$G=-(D-CA^{-1}B)^{-1}CA^{-1}$
$H=(D-CA^{-1}B)^{-1}$

Together, they show the first inequality. Also note that $AE+BG=I$ and thus $E=A^{-1}-A^{-1}BG$. Substituting $G$ into above shows the second equality. $\Box$.

Lemma 2 (Matrix Inversion Formula/Woodbury Matrix Identity):
$(A+BDC)^{-1}=A^{-1}-A^{-1}B(D^{-1}+CA^{-1}B)^{-1}CA^{-1}$

Proof: From the previous proof, we have $E=(A-BD^{-1}C)^{-1}=A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1}$. We get the identity immediately as we flip the sign of $B$.  $\Box$