# Why is this step in a proof of the Woodbury matrix identity valid?

I'm reading over a proof for the Woodbury matrix identity. However, there is a part of the proof that I'm not sure of (highlighted in red below).

The Woodbury matrix identity states that, given the complex matrices $$A \in \mathbb C^{n \times n},B \in \mathbb C^{n \times m},C \in \mathbb C^{m \times m},$$ and $$D \in \mathbb C^{m \times n}$$, and given that $$A,C,$$ and $$A + BCD$$ are invertible, then $$(A + BCD)^{-1} = A^{-1} - A^{-1}B\left(C^{-1} + DA^{-1}B\right)^{-1}DA^{-1}$$ To prove this identity, let $$M = \begin{bmatrix} A & B \\ D & -C^{-1}\end{bmatrix}$$ and $$M^{-1} = \begin{bmatrix} X & W \\ Y & Z\end{bmatrix}$$, where $$X,W,Y,$$ and $$Z$$ are complex block matrices with appropriate dimensions, such that \begin{align} MM^{-1} = \begin{bmatrix} I & 0 \\ 0 & I\end{bmatrix} &= \begin{bmatrix} A & B \\ D & -C^{-1}\end{bmatrix} \begin{bmatrix} X & W \\ Y & Z\end{bmatrix} \\ &= \begin{bmatrix} AX + BY & AW + BZ \\ DX - C^{-1}Y & DW - C^{-1}Z\end{bmatrix} \end{align} Therefore, \begin{align} AX + BY &= I \tag{1}\label{eq:1a_1st} \\ DX - C^{-1}Y &= 0 \tag{2}\label{eq:1a_2nd} \end{align} From \eqref{eq:1a_1st}, $$X = A^{-1}(I - BY)$$. Substituting this into \eqref{eq:1a_2nd} yields \begin{align} DX - C^{-1}Y &= 0 \\ DA^{-1}(I - BY) &= C^{-1}Y \\ DA^{-1} - DA^{-1}BY &= C^{-1}Y \\ DA^{-1} &= DA^{-1}BY + C^{-1}Y \\ \color{red}{DA^{-1}} &\begingroup\color{red}=\endgroup \color{red}{(DA^{-1}B + C^{-1})Y} \\ \color{red}{(DA^{-1}B + C^{-1})^{-1}DA^{-1}} &\begingroup\color{red}=\endgroup \color{red}{Y} \end{align} This is the part of the proof that I don't understand. How do we know that the inverse of $$(DA^{-1}B + C^{-1})$$ exists to proceed as shown above? We are given that $$A + BCD$$ is invertible, but I'm not sure how this is relevant.

The proof you have mentioned is poorly written and is overly complicated. Put $$X=A^{-1}B$$ and $$Y=CD$$. Then $$A+BCD=A(I+XY)$$ and $$DA^{-1}B + C^{-1}=C^{-1}(YX+I)$$. The identity can be rewritten as $$(I + XY)^{-1} = I - X\left(I + YX\right)^{-1}Y.\tag{1}$$ You are essentially asking why $$I+YX$$ is invertible when $$I+XY$$ is invertible. Suppose the contrary that $$I+YX$$ is singular. Then $$YXu=-u$$ for some nonzero vector $$u$$. Hence $$v=Xu\ne0$$ and $$XYv=X(YXu)=X(-u)=-v$$, but this is a contradiction because $$I+XY$$ is nonsingular.
The result also follows from one of the two determinant theorems of Sylvester, which states that when $$X$$ is $$m\times n$$ and $$Y$$ is $$n\times m$$, we have $$\det(I_m+XY)=\det(I_n+YX)$$. More generally, the characteristic polynomial of $$XY$$ is $$x^{m-n}$$ times the characteristic polynomial of $$YX$$. That is, $$\det(xI_m-XY)=x^{m-n}\det(xI_n-YX)$$. You may see this answer for more details.
Once we know that $$I+YX$$ is invertible, the identity $$(1)$$ can be easily proved by showing that $$(I + XY)\left[I - X\left(I + YX\right)^{-1}Y\right]=I$$. But how can one foresee that the inverse of $$I+XY$$ is in the form of the RHS of $$(1)$$? See this MO question for a more in-depth discussion.
• Why does the vector $u$ being in the null space of $I + YX$ imply that $v=Xu \ne 0$? Sep 12, 2022 at 19:22
• @mhdadk If $Xu=0$, then $YXu=-u=0$. Sep 12, 2022 at 19:23
• Doesn’t this mean that $X$ must be invertible? If so, how do we know it is? Sep 12, 2022 at 19:24
• @mhdadk I don't understand your question. $X$ is not necessarily a square matrix. Sep 12, 2022 at 19:25
• Nevermind, I realized that $Xu = 0 \implies YXu \neq 0$ is the contrapositive of $YXu = 0 \implies Xu \neq 0$. Thanks for the explanation. I just found out that that if $M = \begin{bmatrix} A & B \\ D & -C^{-1}\end{bmatrix}$ and both $A$ and $C$ are invertible, then $A + BCD$, which is the Schur complement of $-C^{-1}$, is invertible iff $-C^{-1} - DA^{-1}B$, which is the Schur complement of $A$, is invertible. This helped my understanding. Proof here. Sep 12, 2022 at 19:54