Woodbury Matrix Identity - Derivation From LDU Decomposition

Derivation From LDU Decomposition

We start by the matrix

By eliminating the entry under the A (given that A is invertible) we get

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

Likewise, eliminating the entry above C gives

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

Now combining the above two, we get

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

Moving to the right side gives

which is the LDU decomposition of the block matrix into an upper triangular, diagonal, and lower triangular matrices.

Now inverting both sides gives

$\begin{align} \begin{bmatrix} A & U \\ V & C \end{bmatrix}^{-1} & = \begin{bmatrix} I & A^{-1}U \\ 0 & I \end{bmatrix}^{-1} \begin{bmatrix} A & 0 \\ 0 & C-VA^{-1}U \end{bmatrix}^{-1} \begin{bmatrix} I & 0 \\ VA^{-1} & I \end{bmatrix}^{-1} \\ & = \begin{bmatrix} I & -A^{-1}U \\ 0 & I \end{bmatrix} \begin{bmatrix} A^{-1} & 0 \\ 0 & (C-VA^{-1}U)^{-1} \end{bmatrix} \begin{bmatrix} I & 0 \\ -VA^{-1} & I \end{bmatrix} \\ & = \begin{bmatrix} A^{-1}+A^{-1}U(C-VA^{-1}U)^{-1}VA^{-1} & -A^{-1}U(C-VA^{-1}U)^{-1} \\ -(C-VA^{-1}U)^{-1}VA^{-1} & (C-VA^{-1}U)^{-1} \end{bmatrix} \qquad\mathrm{(1)} \end{align}$

We could equally well have done it the other way (provided that C is invertible) i.e.

Now again inverting both sides,

$\begin{align} \begin{bmatrix} A & U \\ V & C \end{bmatrix}^{-1} & = \begin{bmatrix} I & 0 \\ C^{-1}V & I\end{bmatrix}^{-1} \begin{bmatrix} A-UC^{-1}V & 0 \\ 0 & C \end{bmatrix}^{-1} \begin{bmatrix} I & UC^{-1} \\ 0 & I \end{bmatrix}^{-1} \\ & = \begin{bmatrix} I & 0 \\ -C^{-1}V & I\end{bmatrix} \begin{bmatrix} (A-UC^{-1}V)^{-1} & 0 \\ 0 & C^{-1} \end{bmatrix} \begin{bmatrix} I & -UC^{-1} \\ 0 & I \end{bmatrix} \\ & = \begin{bmatrix} (A-UC^{-1}V)^{-1} & -(A-UC^{-1}V)^{-1}UC^{-1} \\ -C^{-1}V(A-UC^{-1}V)^{-1} & C^{-1}V(A-UC^{-1}V)^{-1}UC^{-1}+C^{-1} \end{bmatrix} \qquad\mathrm{(2)} \end{align}$

Now comparing elements (1,1) of the RHS of (1) and (2) above gives the Woodbury formula

Read more about this topic: Woodbury Matrix Identity