Stuff I find slightly meaningful and close to achievable

Woodbury identity and block-LDU decomposition

Following up a previous post on block-LDU decompositions, we now have enough knowledge to derive the famous Woodbury identity.

Block-LDU decomposition

Recall the block-LDU decomposition of a matrix \(M\) :

$$
\begin{bmatrix}
A & B\\
C & D
\end{bmatrix}
=
\begin{bmatrix}
\mathrm{I}_{n} & 0 \\
CA^{-1} & \mathrm{I}_{m}
\end{bmatrix}
\begin{bmatrix}
A & 0 \\
0 & D – CA^{-1}B
\end{bmatrix}
\begin{bmatrix}
\mathrm{I}_{n} & \, A^{-1}B\\
0 & \mathrm{I}_{m}
\end{bmatrix}
$$

If \(D\) is invertible, we can also decompose \(M\) into \(\tilde{U}\tilde{D}\tilde{L}\) blocks:

$$
\begin{bmatrix}
A & B\\
C & D
\end{bmatrix}
=
\begin{bmatrix}
\mathrm{I}_{n} & BD^{-1} \\
0 & \mathrm{I}_{m}
\end{bmatrix}
\begin{bmatrix}
A – BD^{-1}C & 0 \\
0 & D
\end{bmatrix}
\begin{bmatrix}
\mathrm{I}_{n} & 0 \\
D^{-1}C & \mathrm{I}_{m}
\end{bmatrix}
$$

These two block factorizations can be inverted, and comparing their entries yields the formula.

A tale of two inverses

Let's compute the inverse \(M^{-1}\) in terms of \(M=LDU\) and \(M = \tilde{U}\tilde{D}\tilde{L}\). Computing the inverses of block triangular matrices is easy. The first block-LDU decomposition yields the inverse

$$
M^{-1} =
\begin{bmatrix}
\mathrm{I}_{n} & \, -A^{-1}B\\
0 & \mathrm{I}_{m}
\end{bmatrix}
\begin{bmatrix}
A^{-1} & 0 \\
0 & \left(D – CA^{-1}B\right)^{-1}
\end{bmatrix}
\begin{bmatrix}
\mathrm{I}_{n} & 0 \\
– CA^{-1} & \mathrm{I}_{m}
\end{bmatrix}
$$

which finally yields the blocks

$$ M^{-1} =
\begin{bmatrix}
A^{-1} +A^{-1}B \left(D – CA^{-1}B\right)^{-1}CA^{-1} & \, -A^{-1}B \left(D – CA^{-1}B\right)^{-1}\\
– \left(D – CA^{-1}B\right)^{-1}CA^{-1} &
\left(D – CA^{-1}B\right)^{-1}
\end{bmatrix}
$$

The second (block-UDL) decomposition implies that

$$
M^{-1} = \begin{bmatrix}
\mathrm{I}_{n} & 0 \\
-D^{-1}C & \mathrm{I}_{m}
\end{bmatrix}
\begin{bmatrix}
\left(A – BD^{-1}C\right)^{-1} & 0 \\
0 & D^{-1}
\end{bmatrix}
\begin{bmatrix} \mathrm{I}_{n} & -BD^{-1} \\
0 & \mathrm{I}_{m}
\end{bmatrix}
$$

block-multplying the three matrices yields the expression

$$ M^{-1} =
\begin{bmatrix}
\left(A – BD^{-1}C\right)^{-1} &
-\left(A – BD^{-1}C\right)^{-1}BD^{-1} \\
-D^{-1}C\left(A – BD^{-1}C\right)^{-1} & D^{-1} + D^{-1}C\left(A – BD^{-1}C\right)^{-1}BD^{-1}
\end{bmatrix}
$$

The final result

By identifying the two expressions for \(M^{-1}\) we obtain that, in particular, the upper-left blocks are equal. This means that

$$ \left(A – BD^{-1}C\right)^{-1} = A^{-1} +A^{-1}B \left(D – CA^{-1}B\right)^{-1}CA^{-1} $$
which is the final result ! The result is often written differently, e.g.

$$ \left(A + UWV\right)^{-1} = A^{-1} – A^{-1}U \left(W^{-1} + VA^{-1}U\right)^{-1}VA^{-1} $$

Corollaries

As the Woodbury lemma holds for any comformable matrices (that is \(A, U, W, V\) are respectively \(n\times n, n\times k, k \times k, k \times n\)), we can obtain several special cases.

Inverse of a sum

By setting \(U \triangleq V \triangleq \mathrm{I}_n\) (and \( W \triangleq B\)) we obtain that

$$ \left(A + B\right)^{-1} = A^{-1} – A^{-1}\left(A^{-1} + B^{-1}\right)^{-1}A^{-1}$$

Inverse of a sum of products

By setting \(W \triangleq \mathrm{I}\) we obtain that

$$ \left(A + BC\right)^{-1} = A^{-1} – A^{-1}B\left(\mathrm{I} + CA^{-1}B\right)^{-1}CA^{-1}$$

If \(A\) itself is the product of invertible matrices, we have that

$$ \left(AB + CD\right)^{-1} = B^{-1}A^{-1} – B^{-1}A^{-1}C\left(\mathrm{I} + DB^{-1}A^{-1}C\right)^{-1}DB^{-1}A^{-1}$$