Recursive use of the Woodbury identity to prove the Neumann series expansion.

While I was playing around with some matrices I had the need to expand the matrix inverse of $(I-T)$ . While doing so I came across two different tools, one known as the Woodbury identity and the other known as the Neumann series expansion. While messing with the aforementioned results I found out that there is an pretty cute and trivial way to prove the Neumann series expansion using the Woodbury inequality in a recursive way.

Theorem (Woodbury inequality)

Let’s consider $A\in\mathbb{R}^{n\times n}$ , $U,V^{T}\in\mathbb{R}^{n\times k}$ and $C\in\mathbb{R}^{k\times k}$ then we could write:

$(A+UCV)^{-1}=A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}$

Proof

We could easily prove this result just showing that the direct product of $(A+UCV)(A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1})$ yield the identity matrix.

I’ll now introduce what is called the Neumann series expansion, with this term we identify the following result: $(I-T)^{-1}=\sum_{k=0}^{\infty}T^k$ . Is possible to prove that the series mentioned above converges, and therefore the above identity make sense, if operator norm of $T$ is less or equal to $1$ . To prove what we mentioned above we usually use the following argument:

We first define $S_n=\sum_{k=0}^{n}T^k$ and then we could easily prove that:

$\displaystyle \lim_{n\to \infty}(I-T)S_n=\lim_{n\to\infty}\bigg(\sum_{k=0}^n T^k - \sum_{k=0}^n T^{k+1} \bigg)=lim_{n\to\infty}(I-T^{n+1})=I$

Cutey Proof For Neumann Series Expansion

Let’s decompose $T$ using the Arnoldi iterations $T=QHQ^T$ , once we write $\Lambda=-H$ , then we could easily write:

$(I-T)^{-1}=(I+Q\Lambda Q^T)^{-1}=I-IQ(\Lambda^{-1}+Q^TQ)^{-1}Q^TI=I-Q(\Lambda^{-1}+I)^{-1}Q^T$

We then expand using the Woodbury identity again:

$(\Lambda^{-1}+I)^{-1}=(\Lambda^{-1}+QIQ^T)=\Lambda - \Lambda Q^T(I+Q\Lambda Q^T)^{-1}Q\Lambda$

substituting this in the above equation we obtain:

$(I-T)^{-1}=I-Q(\Lambda^{-1}+I)^{-1}Q^T=I-Q\Lambda Q^T - Q\Lambda Q^T (I+Q\Lambda Q^T)^{-1}Q\Lambda Q^T$

therefore we have, $I+T+T(I+T)^{-1}T$ , once we apply recursively the Woodbury identity to expand $(I+T)^{-1}$ we obtain: $(I+T)^{-1}=\sum_{k=0}^\infty T^k$ .