# Inverting a Block-Toeplitz matrix with the Sherman-Morrison formula

Suppose we are given the following Block-Toeplitz matrix: $$\begin{eqnarray} T=\left(\begin{matrix} A & 0 & ... & 0\\ B & A & ... & \vdots\\ \vdots & \ddots & \ddots &\vdots\\ 0 & ... & B & A \end{matrix}\right) \end{eqnarray}$$ where each $$B,A$$ are matrices of dimension $$N\times N$$. Note that we only have blocks $$A$$ in the diagonal, as well as blocks $$B$$ on the lower-diagonal; the rest of blocks are $$N\times N$$ matrices with zero entries. Our aim is to calculate the inverse of such matrix $$T^{-1}$$. One can decompose this matrix as a sum of a circulant matrix and a matrix with a single block in the upper-right corner, so that: $$\begin{eqnarray} T=\left(\begin{matrix} A & 0 & ... & B\\ B & A & ... & \vdots\\ \vdots & \ddots & \ddots &\vdots\\ 0 & ... & B & A \end{matrix}\right) + \left(\begin{matrix} 0 & 0 & ... & -B\\ 0 & 0 & ... & \vdots\\ \vdots & \ddots & \ddots &\vdots\\ 0 & ... & 0 & 0 \end{matrix}\right)=C + D \end{eqnarray}$$ Now, my question is if one can, in this very concrete case, apply the Shermann and Morrison lemma (https://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula ) here, so that we can make: $$\begin{eqnarray} (C+D)^{-1} = C^{-1} - \frac{1}{1+\text{Tr}(DC^{-1})}C^{-1}.D.C^{-1} \end{eqnarray}$$ since the inverse of $$C^{-1}$$ has a closed form because $$C$$ is block-circulant matrix. Is the above statement correct? Note that $$D$$ is not invertible, but if I understood correctly, this is not a requirement for the formula to be correct.

• You can't apply the Shermann Morrison formula unless $B$ happens to have rank $1$. However, you can apply the Woodbury matrix identity. Commented Apr 14, 2021 at 14:55

The Shermann Morrison formula only applies if the update matrix (which you refer to as $$D$$) has rank $$1$$.
However, we can do what you're trying to do using the Woodbury matrix identity. In particular, we can write $$D = \pmatrix{-B\\0\\ \vdots \\ 0} I_N \pmatrix{0 & \cdots & 0 & I_N} = UIV,$$ where $$I$$ denotes the identity matrix. With that, we have $$(C + D)^{-1} = (C + UI_NV)^{-1}= C^{-1} - C^{-1}U \left(I_N + VC^{-1}U \right)^{-1} VC^{-1}.$$
• Thanks for the reply; is this supposed to work when $D$ is a singular matrix? Since $D^{-1}$ is not defined. This reference "Henderson, H. V.; Searle, S. R. (1981). "On deriving the inverse of a sum of matrices"" seems to apply for cases when $D$ is singular. Commented Apr 14, 2021 at 15:08
• Yes, this works when $D$ is singular. In fact, this formula is only helpful if $D$ is singular. Commented Apr 14, 2021 at 15:10
• @Zarathustra I realize now that I had a typo. The first $D^{-1}$ should have been $C^{-1}$ Commented Apr 14, 2021 at 15:12
• Also, shouldn't $V=(0 0 ...I_{N})$ instead? Or am I just confused on the $V$ definition. Commented Apr 14, 2021 at 15:29