Woodbury matrix identity

In mathematics (specifically linear algebra), the Woodbury matrix identity, named after Max A. Woodbury, says that the inverse of a rank-"k" correction of some matrix can be computed by doing a rank-"k" correction to the inverse of the original matrix. Alternative names for this formula are the matrix inversion lemma, Sherman–Morrison–Woodbury formula or just Woodbury formula. However, the identity appeared in several papers before the Woodbury report.
The Woodbury matrix identity is
where "A", "U", "C" and "V" are conformable matrices: "A" is "n"×"n", "C" is "k"×"k", "U" is "n"×"k", and "V" is "k"×"n". This can be derived using blockwise matrix inversion.
While the identity is primarily used on matrices, it holds in a general ring or in an Ab-category.
Discussion.
To prove this result, we will start by proving a simpler one. Replacing "A" and "C" with the identity matrix "I", we obtain another identity which is a bit simpler:
To recover the original equation from this "reduced identity", set formula_3 and formula_4.
This identity itself can be viewed as the combination of two simpler identities. We obtain the first identity from
thus,
and similarly
The second identity is the so-called push-through identity
that we obtain from
after multiplying by formula_10 on the right and by formula_11 on the left.
Special cases.
When formula_12 are vectors, the identity reduces to the Sherman–Morrison formula.
In the scalar case it (the reduced version) is simply
Inverse of a sum.
If "n" = "k" and "U" = "V" = "I""n" is the identity matrix, then
Continuing with the merging of the terms of the far right-hand side of the above equation results in Hua's identity
Another useful form of the same identity is
which has a recursive structure that yields
This form can be used in perturbative expansions where "B" is a perturbation of "A".
Variations.
Binomial inverse theorem.
If "A", "B", "U", "V" are matrices of sizes "n"×"n", "k"×"k", "n"×"k", "k"×"n", respectively, then
provided "A" and "B" + "BVA"−1"UB" are nonsingular. Nonsingularity of the latter requires that "B"−1 exist since it equals and the rank of the latter cannot exceed the rank of "B".
Since "B" is invertible, the two "B" terms flanking the parenthetical quantity inverse in the right-hand side can be replaced with which results in the original Woodbury identity.
A variation for when "B" is singular and possibly even non-square:
Formulas also exist for certain cases in which "A" is singular.
Derivations.
Direct proof.
The formula can be proven by checking that formula_20 times its alleged inverse on the right side of the Woodbury identity gives the identity matrix:
Alternative proofs.
First consider these useful identities,
Now, 
Deriving the Woodbury matrix identity is easily done by solving the following block matrix inversion problem
Expanding, we can see that the above reduces to
which is equivalent to formula_26. Eliminating the first equation, we find that formula_27, which can be substituted into the second to find formula_28. Expanding and rearranging, we have formula_29, or formula_30. Finally, we substitute into our formula_31, and we have formula_32. Thus,
We have derived the Woodbury matrix identity.
We start by the matrix
By eliminating the entry under the "A" (given that "A" is invertible) we get
Likewise, eliminating the entry above "C" gives
Now combining the above two, we get
Moving to the right side gives
which is the LDU decomposition of the block matrix into an upper triangular, diagonal, and lower triangular matrices.
Now inverting both sides gives
We could equally well have done it the other way (provided that "C" is invertible) i.e.
Now again inverting both sides,
Now comparing elements (1, 1) of the RHS of (1) and (2) above gives the Woodbury formula
Applications.
This identity is useful in certain numerical computations where "A"−1 has already been computed and it is desired to compute ("A" + "UCV")−1. With the inverse of "A" available, it is only necessary to find the inverse of "C"−1 + "VA"−1"U" in order to obtain the result using the right-hand side of the identity. If "C" has a much smaller dimension than "A", this is more efficient than inverting "A" + "UCV" directly. A common case is finding the inverse of a low-rank update "A" + "UCV" of "A" (where "U" only has a few columns and "V" only a few rows), or finding an approximation of the inverse of the matrix "A" + "B" where the matrix "B" can be approximated by a low-rank matrix "UCV", for example using the singular value decomposition.
This is applied, e.g., in the Kalman filter and recursive least squares methods, to replace the parametric solution, requiring inversion of a state vector sized matrix, with a condition equations based solution. In case of the Kalman filter this matrix has the dimensions of the vector of observations, i.e., as small as 1 in case only one new observation is processed at a time. This significantly speeds up the often real time calculations of the filter.
In the case when "C" is the identity matrix "I", the matrix formula_43 is known in numerical linear algebra and numerical partial differential equations as the capacitance matrix.