Woodbury identity and block-LDU decomposition

March 17, 2021

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}$$