# Shae's Ramblings

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