## Matrix Inversion Lemma

In this article we’ll derive the matrix inversion lemma, also known as the Sherman-Morrisson-Woodbury formula. At first it might seem like a very boring piece of linear algebra, but it has a few nifty uses, as we’ll see in one of the followup articles.

$$M = \begin{bmatrix} A & U \\\ V & B \end{bmatrix}$$

We’ll do an LDU decomposition in two different ways, which basically direclty gives us the end formula. Eliminating the bototm left element we get the following:

$$\begin{bmatrix} I & 0 \\\ -V A^{-1} & I \end{bmatrix} \begin{bmatrix} A & U \\\ V & B \end{bmatrix} = \begin{bmatrix} A & U \\\ 0 & B - V A^{-1} U \end{bmatrix}$$

The $B - V A^{-1} U$ is called a Schur complement and is generally defined as follows:

$$M/A := V A^{-1} U$$

We’ll use this notation later to make things easier to read. Moving on with the decomposition, we’ll now eliminate $U$.

$$\begin{bmatrix} A & U \\\ 0 & B - V A^{-1} U \end{bmatrix} \begin{bmatrix} I & -A^{-1} U \\\ 0 & I \end{bmatrix} = \begin{bmatrix} A & 0 \\\ 0 & B - V A^{-1} U \end{bmatrix}$$

Putting the two equations above together we get the following:

$$\underbrace{\begin{bmatrix} I & 0 \\\ -V A^{-1} & I \end{bmatrix}}_{X} \underbrace{\begin{bmatrix} A & U \\\ V & B \end{bmatrix}}_{M} \underbrace{\begin{bmatrix} I & -A^{-1} U \\\ 0 & I \end{bmatrix}}_{Z} = \underbrace{\begin{bmatrix} A & 0 \\\ 0 & B - V A^{-1} U \end{bmatrix}}_{W}$$

We could also write the matrix $W$ using the Schur complement notation: $$W = \begin{bmatrix} A & 0 \\\ 0 & B - V A^{-1} U \end{bmatrix} = \begin{bmatrix} A & 0 \\\ 0 & M/A \end{bmatrix}$$

Now we just express $M$ in terms of $X, Z, W$ and take the inverse to get $M^{-1}$.

\begin{align} X M Z &= W \\\ M Z &= X^{-1} W \\\ M &= X^{-1} W Z^{-1} \\\ M^{-1} &= (X^{-1} W Z^{-1})^{-1} \\\ M^{-1} &= Z W^{-1} X \end{align}

Substituting our matrices back in, we get:

$$\begin{bmatrix} A & U \\\ V & B \end{bmatrix}^{-1} = \begin{bmatrix} I & -A^{-1} U \\\ 0 & I \end{bmatrix} \begin{bmatrix} A^{-1} & 0 \\\ 0 & (M/A)^{-1} \end{bmatrix} \begin{bmatrix} I & 0 \\\ -V A^{-1} & I \end{bmatrix}$$

Now comes the fun part, we’ll multiply out the right side of the equation:

\begin{align} \begin{bmatrix} A & U \\\ V & B \end{bmatrix}^{-1} &= \begin{bmatrix} I & -A^{-1} U \\\ 0 & I \end{bmatrix} \begin{bmatrix} A^{-1} & 0 \\\ 0 & (M/A)^{-1} \end{bmatrix} \begin{bmatrix} I & 0 \\\ -V A^{-1} & I \end{bmatrix} \\\ &= \begin{bmatrix} A^{-1} & -A^{-1} U (M/A)^{-1} \\\ 0 & (M/A)^{-1} \end{bmatrix} \begin{bmatrix} I & 0 \\\ -V A^{-1} & I \end{bmatrix} \\\ &= \begin{bmatrix} A^{-1} + A^{-1} U (M/A)^{-1} V A^{-1} & -A^{-1} U (M/A)^{-1} \\\ -(M/A)^{-1} VA^{-1} & (M/A)^{-1} \end{bmatrix} \\\ &= \begin{bmatrix} A^{-1} + A^{-1} U (B - V A^{-1} U)^{-1} V A^{-1} & -A^{-1} U (B - V A^{-1} U)^{-1} \\\ -(B - V A^{-1} U)^{-1} VA^{-1} & (B - V A^{-1} U)^{-1} \end{bmatrix} \end{align}

That’s it for the first part, now we’ll do the same, but eliminating the top-right element from the left first.

$$\begin{bmatrix} I & -U B^{-1} \\\ 0 & I \end{bmatrix} \begin{bmatrix} A & U \\\ V & B \end{bmatrix} = \begin{bmatrix} A - UB^{-1}V & 0 \\\ V & B \end{bmatrix}$$

Here we get the other Schur complement, which we’ll note as $M/B = A - UB^{-1}V$. We can substitute it in straight away this time.

$$\begin{bmatrix} M/B & 0 \\\ V & B \end{bmatrix} \begin{bmatrix} I & 0 \\\ -B^{-1}V & I \end{bmatrix} = \begin{bmatrix} M/B & 0 \\\ 0 & B \end{bmatrix}$$

As before, we’ll write it out as a single equation:

$$\begin{bmatrix} I & -U B^{-1} \\\ 0 & I \end{bmatrix} \begin{bmatrix} A & U \\\ V & B \end{bmatrix} \begin{bmatrix} I & 0 \\\ -B^{-1}V & I \end{bmatrix} = \begin{bmatrix} M/B & 0 \\\ 0 & B \end{bmatrix}$$

Now we express the matrix $M$ in terms of the other two (notice the newly added inverse signs):

$$\begin{bmatrix} A & U \\\ V & B \end{bmatrix} = \begin{bmatrix} I & -U B^{-1} \\\ 0 & I \end{bmatrix}^{-1} \begin{bmatrix} M/B & 0 \\\ 0 & B \end{bmatrix} \begin{bmatrix} I & 0 \\\ -B^{-1}V & I \end{bmatrix}^{-1}$$

Lastly, we just take the inverse of both sides:

\begin{align} \begin{bmatrix} A & U \\\ V & B \end{bmatrix}^{-1} &= \left( \begin{bmatrix} I & -U B^{-1} \\\ 0 & I \end{bmatrix}^{-1} \begin{bmatrix} M/B & 0 \\\ 0 & B \end{bmatrix} \begin{bmatrix} I & 0 \\\ -B^{-1}V & I \end{bmatrix}^{-1} \right)^{-1} \\\ &= \begin{bmatrix} I & 0 \\\ -B^{-1}V & I \end{bmatrix} \begin{bmatrix} M/B & 0 \\\ 0 & B \end{bmatrix}^{-1} \begin{bmatrix} I & -U B^{-1} \\\ 0 & I \end{bmatrix} & \text{notice the inverses cancelling out} \\\ &= \begin{bmatrix} I & 0 \\\ -B^{-1}V & I \end{bmatrix} \begin{bmatrix} (M/B)^{-1} & 0 \\\ 0 & B^{-1} \end{bmatrix} \begin{bmatrix} I & -U B^{-1} \\\ 0 & I \end{bmatrix} \\\ &= \begin{bmatrix} (M/B)^{-1} & 0 \\\ -B^{-1} V (M/B)^{-1} & B^{-1} \end{bmatrix} \begin{bmatrix} I & -U B^{-1} \\\ 0 & I \end{bmatrix} \\\ &= \begin{bmatrix} (M/B)^{-1} & -(M/B)^{-1} UB^{-1} \\\ -B^{-1} V (M/B)^{-1} & B^{-1} V (M/B)^{-1} UB^{-1} + B^{-1} \end{bmatrix} \\\ &= \begin{bmatrix} (A - UB^{-1}V)^{-1} & -(A - UB^{-1}V)^{-1} UB^{-1} \\\ -B^{-1} V (A - UB^{-1}V)^{-1} & B^{-1} V (A - UB^{-1}V)^{-1} UB^{-1} + B^{-1} \end{bmatrix} \end{align}