Woodbury's formula with block-diagonal matrix

Question

From Woodbury's formula, it is easy to show that \begin{align*} (a \mathbf{I}_n + b J_n)^{-1} = \frac{1}{a}\mathbf{I}_n - \frac{b}{a(a+bn)}J_n \end{align*} where $\mathbf{I}_n$ is the $n\times n$ identity matrix and $J_n$ is the $n\times n$ matrix of 1's. Is there a similarly nice form for \begin{align*} (a\mathbf{I}_n + b J_{n_1, \cdots, n_k} + c J_n)^{-1} \end{align*} where $J_{n_1, \cdots, n_k} = \text{BlockDiag}(J_{n_1}, \cdots, J_{n_k})$ so that $\sum_{i=1}^{k}n_i = n$?

Answer 1

Woodbury's matrix identity is a generalization of the Sherman–Morrison formula. The Sherman–Morrison formula tells you how to compute the inverse of $A$ plus a rank-$1$ matrix if you already have the inverse of $A$ computed. The Woodbury matrix identity tells you how to compute the inverse of $A$ plus a rank-$r$ matrix if you already have the inverse of $A$ computed.

Here, you can check that $J_{n_1,\ldots,n_k}$ is a rank-$k$ matrix and $J_n$ is a rank-$1$ matrix. So we are trying to compute the inverse of $aI_n$ plus a rank-$(k+1)$ matrix.

Let $A = aI_n$, $U = \begin{bmatrix}\vec{1}_{n_1}& & & & \vec{1}_{n_1} \\ & \vec{1}_{n_2} & & & \vec{1}_{n_2} \\ & & \ddots & & \vdots \\ & & & \vec{1}_{n_k} & \vec{1}_{n_k}\end{bmatrix}$, and $C = \text{diag}(\underbrace{b,\ldots,b}_{k \ b's},c)$.

You can check that $aI_n+bJ_{n_1,\ldots,n_k}+cJ_n = A+UCU^T$. Thus,

\begin{align*} (aI_n+bJ_{n_1,\ldots,n_k}+cJ_n)^{-1} &= (A+UCU^T)^{-1} \\ &= A^{-1}-A^{-1}U(C^{-1}+U^TA^{-1}U)^{-1}U^TA^{-1} \\ &= \dfrac{1}{a}I_n-\dfrac{1}{a}I_nU\left(C^{-1}+U^T\dfrac{1}{a}I_nU\right)^{-1}U^T\dfrac{1}{a}I_n \\ &= \dfrac{1}{a}I_n-\dfrac{1}{a^2}U\left(C^{-1}+\dfrac{1}{a}U^TU\right)^{-1}U^T \end{align*}

It is not hard to compute $U^TU = \begin{bmatrix}n_1 & & & & n_1\\ & n_2 & & & n_2 \\ & & \ddots & & \vdots \\ & & & n_k & n_k \\ n_1 & n_2 & \cdots & n_k & n\end{bmatrix}$, so $C^{-1}+\dfrac{1}{a}U^TU = \begin{bmatrix}\tfrac{n_1}{a}+\tfrac{1}{b} & & & & \tfrac{n_1}{a}\\ & \tfrac{n_2}{a}+\tfrac{1}{b} & & & \tfrac{n_2}{a} \\ & & \ddots & & \vdots \\ & & & \tfrac{n_k}{a}+\tfrac{1}{b} & \tfrac{n_k}{a} \\ \tfrac{n_1}{a} & \tfrac{n_2}{a} & \cdots & \tfrac{n_k}{a} & \tfrac{n}{a}+\tfrac{1}{c}\end{bmatrix}$.

Computing the inverse of $C^{-1}+\dfrac{1}{a}U^TU$ can be done using the Sherman-Morrison formula $$(D+vv^T)^{-1} = D^{-1} + \dfrac{D^{-1}vv^TD^{-1}}{1+v^TD^{-1}v}$$ where $D = \text{diag}(\tfrac{n_1}{a}+\tfrac{1}{b},\ldots,\tfrac{n_k}{a}+\tfrac{1}{b},\tfrac{n}{a}+\tfrac{1}{c})$ and $v = \begin{bmatrix}\tfrac{n_1}{a} & \tfrac{n_2}{a} & \cdots & \tfrac{n_k}{a} & 0\end{bmatrix}^T$.

After doing this tedious computation, computing $\dfrac{1}{a}I_n-\dfrac{1}{a^2}U\left(C^{-1}+\dfrac{1}{a}U^TU\right)^{-1}U^T$ shouldn't be too much harder.

Unfortunately, I'm too tired to do this right now, but hopefully this answer is helpful.