Jakub Arnold Blog

Matrix Inversion Lemma

5 min read • Published: May 16, 2018

This article is a draft and as such there might be typos and other inaccuracies.

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.

Let’s start with the following block matrix:

M=[AUVB]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:

[I0−VA−1I][AUVB]=[AU0B−VA−1U]\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:=VA−1UM/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 UU.

[AU0B−VA−1U][I−A−1U0I]=[A00B−VA−1U]\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:

[I0−VA−1I]⏟X[AUVB]⏟M[I−A−1U0I]⏟Z=[A00B−VA−1U]⏟W\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 WW using the Schur complement notation:

W=[A00B−VA−1U]=[A00M/A]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 MM in terms of X,Z,WX, Z, W and take the inverse to get M−1M^{-1}.

XMZ=WMZ=X−1WM=X−1WZ−1M−1=(X−1WZ−1)−1M−1=ZW−1X\begin{aligned} 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{aligned}

Substituting our matrices back in, we get:

[AUVB]−1=[I−A−1U0I][A−100(M/A)−1][I0−VA−1I]\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:

[AUVB]−1=[I−A−1U0I][A−100(M/A)−1][I0−VA−1I]=[A−1−A−1U(M/A)−10(M/A)−1][I0−VA−1I]=[A−1+A−1U(M/A)−1VA−1−A−1U(M/A)−1−(M/A)−1VA−1(M/A)−1]=[A−1+A−1U(B−VA−1U)−1VA−1−A−1U(B−VA−1U)−1−(B−VA−1U)−1VA−1(B−VA−1U)−1]\begin{aligned} \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{aligned}

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

[I−UB−10I][AUVB]=[A−UB−1V0VB]\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−1VM/B = A - UB^{-1}V. We can substitute it in straight away this time.

[M/B0VB][I0−B−1VI]=[M/B00B]\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:

[I−UB−10I][AUVB][I0−B−1VI]=[M/B00B]\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 MM in terms of the other two (notice the newly added inverse signs):

[AUVB]=[I−UB−10I]−1[M/B00B][I0−B−1VI]−1\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:

[AUVB]−1=([I−UB−10I]−1[M/B00B][I0−B−1VI]−1)−1=[I0−B−1VI][M/B00B]−1[I−UB−10I]notice the inverses cancelling out=[I0−B−1VI][(M/B)−100B−1][I−UB−10I]=[(M/B)−10−B−1V(M/B)−1B−1][I−UB−10I]=[(M/B)−1−(M/B)−1UB−1−B−1V(M/B)−1B−1V(M/B)−1UB−1+B−1]=[(A−UB−1V)−1−(A−UB−1V)−1UB−1−B−1V(A−UB−1V)−1B−1V(A−UB−1V)−1UB−1+B−1]\begin{aligned} \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{aligned}

Share on Twitter and Facebook

Discussion of "Matrix Inversion Lemma"

If you have any questions, feedback, or suggestions, please do share them in the comments! I'll try to answer each and every one. If something in the article wasn't clear don't be afraid to mention it. The goal of these articles is to be as informative as possible.

If you'd prefer to reach out to me via email, my address is loading ..