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.
While the identity is primarily used on matrices, it holds in a general ring or in an Ab-category.
The Woodbury matrix identity allows cheap computation of inverses and solutions to linear equations. However, little is known about the numerical stability of the formula. There are no published results concerning its error bounds. Anecdotal evidence  suggests that it may diverge even for seemingly benign examples (when both the original and modified matrices are well-conditioned).
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 and .
This identity itself can be viewed as the combination of two simpler identities. We obtain the first identity from
The second identity is the so-called push-through identity
that we obtain from
after multiplying by on the right and by on the left.
Putting all together,
where the first and second equality come from the first and second identity, respectively.
where can be written as because any positive semidefinite matrix is equal to for some .
The formula can be proven by checking that times its alleged inverse on the right side of the Woodbury identity gives the identity matrix:
First consider these useful identities,
Derivation via blockwise elimination
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 . Eliminating the first equation, we find that , which can be substituted into the second to find . Expanding and rearranging, we have , or . Finally, we substitute into our , and we have . Thus,
We have derived the Woodbury matrix identity.
Derivation from LDU decomposition
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
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−1U 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.
^ abcHenderson, H. V.; Searle, S. R. (1981). "On deriving the inverse of a sum of matrices" (PDF). SIAM Review. 23 (1): 53–60. doi:10.1137/1023004. hdl:1813/32749. JSTOR 2029838.
^Kurt S. Riedel, "A Sherman–Morrison–Woodbury Identity for Rank Augmenting Matrices with Application to Centering", SIAM Journal on Matrix Analysis and Applications, 13 (1992)659-662, doi:10.1137/0613040 preprint MR1152773
^Bernstein, Dennis S. (2018). Scalar, Vector, and Matrix Mathematics: Theory, Facts, and Formulas (Revised and expanded ed.). Princeton: Princeton University Press. p. 638. ISBN 9780691151205.
^Schott, James R. (2017). Matrix analysis for statistics (Third ed.). Hoboken, New Jersey: John Wiley & Sons, Inc. p. 219. ISBN 9781119092483.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.7.3. Woodbury Formula", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8