Woodbury matrix identity

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics (specifically linear algebra), the Woodbury matrix identity, named after Max A. Woodbury[1][2] 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.[3]

The Woodbury matrix identity is[4]

where A, U, C and V all denote matrices of the correct (conformable) sizes. Specifically, A is n-by-n, U is n-by-k, C is k-by-k and V is k-by-n. This can be derived using blockwise matrix inversion.

For a more general formula for which the matrix C need not be invertible or even square, see Binomial inverse theorem.

In the special case where C is the 1-by-1 unit matrix, this identity reduces to the Sherman–Morrison formula. In the special case when C is the identity matrix I, the matrix is known in numerical linear algebra and numerical partial differential equations as the capacitance matrix.[3]

Direct proof[edit]

The formula can be proven by checking that times its alleged inverse on the right side of the Woodbury identity gives the identity matrix:

Algebraic proof[edit]

First consider these useful identities,


Derivation via blockwise elimination[edit]

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[edit]

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 + 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.

See also[edit]


  1. ^ Max A. Woodbury, Inverting modified matrices, Memorandum Rept. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950, 4pp MR38136
  2. ^ Max A. Woodbury, The Stability of Out-Input Matrices. Chicago, Ill., 1949. 5 pp. MR32564
  3. ^ a b Hager, William W. (1989). "Updating the inverse of a matrix". SIAM Review. 31 (2): 221–239. doi:10.1137/1031049. JSTOR 2030425. MR 997457. 
  4. ^ Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2nd ed.). SIAM. p. 258. ISBN 978-0-89871-521-7. MR 1927606. 

External links[edit]