Editing Woodbury matrix identity (section)

== Derivations ==

=== Direct proof ===
The formula can be proven by checking that <math>(A + UCV)</math> times its alleged inverse on the right side of the Woodbury identity gives the identity matrix:
<math display="block">\begin{align}
      & \left(A + UCV \right) \left[ A^{-1} - A^{-1}U \left(C^{-1} + VA^{-1}U \right)^{-1} VA^{-1} \right] \\
  ={} & \left\{ I - U\left(C^{-1} + VA^{-1}U \right)^{-1}VA^{-1} \right\} + \left\{ UCVA^{-1} - UCVA^{-1}U \left(C^{-1} + VA^{-1}U \right)^{-1} VA^{-1} \right\} \\
  ={} & \left\{ I + UCVA^{-1} \right\} - \left\{ U\left(C^{-1} + VA^{-1}U \right)^{-1}VA^{-1} + UCVA^{-1}U \left(C^{-1} + VA^{-1}U \right)^{-1} VA^{-1} \right\} \\
  ={} & I + UCVA^{-1} - \left(U + UCVA^{-1}U\right) \left(C^{-1} + VA^{-1}U\right)^{-1}VA^{-1} \\
  ={} & I + UCVA^{-1} - UC \left(C^{-1} + VA^{-1}U\right) \left(C^{-1} + VA^{-1}U\right)^{-1}VA^{-1} \\
  ={} & I + UCVA^{-1} - UCVA^{-1} \\
  ={} & I.
\end{align}</math>

=== Alternative proofs ===

{{collapse top|title=Algebraic proof }}
First consider these useful identities,
<math display="block">\begin{align}
               U + UCV A^{-1} U &= 
               UC \left(C^{-1} + V A^{-1} U\right) = \left(A + UCV\right) A^{-1} U \\
  \left(A + UCV\right)^{-1} U C &= A^{-1}U \left(C^{-1} + VA^{-1} U\right) ^{-1}
\end{align}
</math>

Now, 
<math display="block">\begin{align}
  A^{-1} &= \left(A + UCV\right)^{-1}\left(A + UCV\right) A^{-1}\\
         &= \left(A + UCV\right)^{-1}\left(I + UCVA^{-1}\right) \\
         &= \left(A + UCV\right)^{-1} + \left(A + UCV\right)^{-1} UCVA^{-1} \\ 
         &= \left(A + UCV\right)^{-1} + A^{-1} U \left(C^{-1} + VA^{-1}U \right)^{-1} VA^{-1}.
\end{align}</math>
{{collapse bottom}}

{{collapse top|title=Derivation via blockwise elimination}}
Deriving the Woodbury matrix identity is easily done by solving the following block matrix inversion problem
<math display="block">
  \begin{bmatrix} A & U \\ V & -C^{-1} \end{bmatrix}\begin{bmatrix} X \\ Y \end{bmatrix} = \begin{bmatrix} I \\ 0 \end{bmatrix}.
</math>

Expanding, we can see that the above reduces to
<math display="block">\begin{cases} AX + UY = I \\ VX - C^{-1}Y = 0\end{cases}</math>
which is equivalent to <math>(A + UCV)X = I</math>. Eliminating the first equation, we find that <math>X = A^{-1}(I - UY)</math>, which can be substituted into the second to find <math>VA^{-1}(I - UY) = C^{-1}Y</math>. Expanding and rearranging, we have <math>VA^{-1} = \left(C^{-1} + VA^{-1}U\right)Y</math>, or <math>\left(C^{-1} + VA^{-1}U\right)^{-1}VA^{-1} = Y</math>. Finally, we substitute into our <math>AX + UY = I</math>, and we have <math>AX + U\left(C^{-1} + VA^{-1}U\right)^{-1}VA^{-1} = I</math>. Thus,
:<math>(A + UCV)^{-1} = X = A^{-1} - A^{-1}U\left(C^{-1} + VA^{-1}U\right)^{-1}VA^{-1}.</math>

We have derived the Woodbury matrix identity.
{{collapse bottom}}

{{collapse top|title=Derivation from LDU decomposition}}
We start by the matrix
<math display="block">\begin{bmatrix} A & U \\ V & C \end{bmatrix}</math>
By eliminating the entry under the ''A'' (given that ''A'' is invertible) we get
<math display="block">\begin{bmatrix} I & 0 \\ -VA^{-1} & I \end{bmatrix} 
\begin{bmatrix} A & U \\ V & C \end{bmatrix} = \begin{bmatrix} A & U \\ 0 & C - VA^{-1}U \end{bmatrix}
</math>

Likewise, eliminating the entry above ''C'' gives
<math display="block">\begin{bmatrix} A & U \\ V & C \end{bmatrix} \begin{bmatrix} I & -A^{-1}U \\ 0 & I \end{bmatrix} 
= \begin{bmatrix} A & 0 \\ V & C-VA^{-1}U \end{bmatrix}
</math>

Now combining the above two, we get
<math display="block">
  \begin{bmatrix} I & 0 \\ -VA^{-1} & I \end{bmatrix} \begin{bmatrix} A & U \\ V & C \end{bmatrix}\begin{bmatrix} I & -A^{-1}U \\ 0 & I \end{bmatrix} =
  \begin{bmatrix} A & 0 \\ 0 & C - VA^{-1}U \end{bmatrix}
</math>

Moving to the right side gives
<math display="block">\begin{bmatrix} A & U \\ V & C \end{bmatrix} = \begin{bmatrix} I & 0 \\ VA^{-1} & I \end{bmatrix} \begin{bmatrix} A & 0 \\ 0 & C - VA^{-1}U \end{bmatrix} \begin{bmatrix} I & A^{-1}U \\ 0 & I \end{bmatrix}</math>
which is the LDU decomposition of the block matrix into an upper triangular, diagonal, and lower triangular matrices.

Now inverting both sides gives
<math display="block">\begin{align}
  \begin{bmatrix} A & U \\ V & C \end{bmatrix}^{-1} 
    &= \begin{bmatrix} I & A^{-1}U \\ 0 & I \end{bmatrix}^{-1} \begin{bmatrix} A & 0 \\ 0 & C - VA^{-1}U \end{bmatrix}^{-1} \begin{bmatrix} I & 0 \\ VA^{-1} & I \end{bmatrix}^{-1} \\[8pt]
    &= \begin{bmatrix} I & -A^{-1}U \\ 0 & I \end{bmatrix} \begin{bmatrix} A^{-1} & 0 \\ 0 & \left(C - VA^{-1}U\right)^{-1} \end{bmatrix} \begin{bmatrix} I & 0 \\ -VA^{-1} & I \end{bmatrix} \\[8pt]
    &= \begin{bmatrix} A^{-1} + A^{-1}U\left(C - VA^{-1}U\right)^{-1}VA^{-1} & -A^{-1}U\left(C - VA^{-1}U\right)^{-1} \\ -\left(C - VA^{-1}U\right)^{-1}VA^{-1} & \left(C - VA^{-1}U\right)^{-1} \end{bmatrix}  \qquad\mathrm{(1)}
\end{align}</math>

We could equally well have done it the other way (provided that ''C'' is invertible) i.e.
<math display="block">\begin{bmatrix} A & U \\ V & C \end{bmatrix} = \begin{bmatrix} I & UC^{-1} \\ 0 & I \end{bmatrix} \begin{bmatrix} A - UC^{-1}V & 0 \\ 0 & C \end{bmatrix} \begin{bmatrix} I & 0 \\ C^{-1}V  & I\end{bmatrix}</math>

Now again inverting both sides,
<math display="block">\begin{align}
  \begin{bmatrix} A & U \\ V & C \end{bmatrix}^{-1}
    &= \begin{bmatrix} I & 0 \\ C^{-1}V  & I\end{bmatrix}^{-1} \begin{bmatrix} A - UC^{-1}V & 0 \\ 0 & C \end{bmatrix}^{-1} \begin{bmatrix} I & UC^{-1} \\ 0 & I \end{bmatrix}^{-1} \\[8pt]
    &= \begin{bmatrix} I & 0 \\ -C^{-1}V  & I\end{bmatrix} \begin{bmatrix} \left(A - UC^{-1}V\right)^{-1} & 0 \\ 0 & C^{-1} \end{bmatrix} \begin{bmatrix} I & -UC^{-1} \\ 0 & I \end{bmatrix} \\[8pt]
    &= \begin{bmatrix} \left(A - UC^{-1}V\right)^{-1} & -\left(A - UC^{-1}V\right)^{-1}UC^{-1} \\ -C^{-1}V\left(A - UC^{-1}V\right)^{-1} & C^{-1} + C^{-1}V\left(A - UC^{-1}V\right)^{-1}UC^{-1} \end{bmatrix} \qquad\mathrm{(2)}
\end{align}</math>

Now comparing elements (1, 1) of the RHS of (1) and (2) above gives the Woodbury formula
<math display="block">\left(A - UC^{-1}V\right)^{-1} = A^{-1} + A^{-1}U\left(C - VA^{-1}U\right)^{-1}VA^{-1}.</math>
{{collapse bottom}}