Sherman–Morrison formula explained

A and the outer product u v ^{sf{T}} of vectors u and v, the formula cheaply computes an updated matrix inverse $\backslash left(A\; +\; uv^\backslash textsf\backslash right)\backslash vphantom)^.$

The Sherman–Morrison formula is a special case of the Woodbury formula. Though named after Sherman and Morrison, it appeared already in earlier publications.^[3]

Statement

Suppose

A\in R ^{n x} is an invertible square matrix and u,v\in R ^{n} are column vectors. Then A + uv ^{sf{T}} is invertible iff 1 + v ^{sf{T}A} ^{-1} u ≠ 0 . In this case, \left(A + uv ^{sf{T}\right)} ^{-1} = A ^{-1} - {A ^{-1} uv ^{sf{T}A} ^{-1} \over 1 + v ^{sf{T}A} ^{-1} u}.

Here,

uv ^{sf{T}} is the outer product of two vectors u and v . The general form shown here is the one published by Bartlett.^[4]

Proof

(

\Leftarrow ) To prove that the backward direction 1 + v ^{sf{T}A} ^{-1} u ≠ 0 ⇒ A + uv ^{sf{T}} is invertible with inverse given as above) is true, we verify the properties of the inverse. A matrix Y (in this case the right-hand side of the Sherman–Morrison formula) is the inverse of a matrix X (in this case A + uv ^{sf{T}} ) if and only if XY = YX = I .

We first verify that the right hand side (

Y ) satisfies XY = I .\begin{align} XY & = \left(A + uv ^{sf{T}\right)\left(A} ^{-1} - {A ^{-1} uv ^{sf{T}A} ^{-1} \over 1 + v ^{sf{T}A} ^{-1} u}\right) \\[ 6 pt] & = AA ^{-1} + uv ^{sf{T}A} ^{-1} - {AA ^{-1} uv ^{sf{T}A} ^{-1} + uv ^{sf{T}A} ^{-1} uv ^{sf{T}A} ^{-1} \over 1 + v ^{sf{T}A} ^{-1} u} \\[ 6 pt] & = I + uv ^{sf{T}A} ^{-1} - {uv ^{sf{T}A} ^{-1} + uv ^{sf{T}A} ^{-1} uv ^{sf{T}A} ^{-1} \over 1 + v ^{sf{T}A} ^{-1} u} \\[ 6 pt] & = I + uv ^{sf{T}A} ^{-1} - {u\left( 1 + v ^{sf{T}A} ^{-1} u\right) v ^{sf{T}A} ^{-1} \over 1 + v ^{sf{T}A} ^{-1} u} \\[ 6 pt] & = I + uv ^{sf{T}A} ^{-1} - uv ^{sf{T}A} ^{-1} \\[ 6 pt] & = I \end{align}

To end the proof of this direction, we need to show that

YX = I in a similar way as above:YX = \left(A ^{-1} - {A ^{-1} uv ^{sf{T}A} ^{-1} \over 1 + v ^{sf{T}A} ^{-1} u}\right)(A + uv ^{sf{T})=} I.

(In fact, the last step can be avoided since for square matrices

X and Y , XY = I is equivalent to YX = I .)

(

⇒ ) Reciprocally, if 1 + v ^{sf{T}A} ^{-1} u = 0 , then via the matrix determinant lemma, \det\left(A + uv ^{sf{T}\right)=(1+} v ^{sf{T}A} ^{-1} u) \det(A) = 0 , so \left(A + uv ^{sf{T}\right)} is not invertible.

Application

If the inverse of

A is already known, the formula provides a numerically cheap way to compute the inverse of A corrected by the matrix uv ^{sf{T}} (depending on the point of view, the correction may be seen as a perturbation or as a rank-1 update). The computation is relatively cheap because the inverse of A + uv ^{sf{T}} does not have to be computed from scratch (which in general is expensive), but can be computed by correcting (or perturbing) A ^{-1} .

Using unit columns (columns from the identity matrix) for

u or v , individual columns or rows of A may be manipulated and a correspondingly updated inverse computed relatively cheaply in this way.^[5] In the general case, where A ^{-1} is an n -by-n matrix and u and v are arbitrary vectors of dimension n , the whole matrix is updated and the computation takes 3 n ^{2} scalar multiplications.^[6] If u is a unit column, the computation takes only 2 n ^{2} scalar multiplications. The same goes if v is a unit column. If both u and v are unit columns, the computation takes only n ^{2} scalar multiplications.

This formula also has application in theoretical physics. Namely, in quantum field theory, one uses this formula to calculate the propagator of a spin-1 field.^[7] The inverse propagator (as it appears in the Lagrangian) has the form

A + uv ^{sf{T}} . One uses the Sherman–Morrison formula to calculate the inverse (satisfying certain time-ordering boundary conditions) of the inverse propagator—or simply the (Feynman) propagator—which is needed to perform any perturbative calculation^[8] involving the spin-1 field.

One of the issues with the formula is that little is known about its numerical stability. There are no published results concerning its error bounds. Anecdotal evidence ^[9] suggests that the Woodbury matrix identity (a general case of the Sherman–Morrison formula) may diverge even for seemingly benign examples (when both the original and modified matrices are well-conditioned).

Alternative verification

Following is an alternate verification of the Sherman–Morrison formula using the easily verifiable identity

\left(I + wv ^{sf{T}\right)} ^{-1} = I - (wv ^{sf{T})/() }.

Let

u = Aw, and A + uv ^{sf{T}=} A\left(I + wv ^{sf{T}\right),}

then

\left(A + uv ^{sf{T}\right)} ^{-1} = \left(I + wv ^{sf{T}\right)} ^{-1} A ^{-1} = \left(I - (wv ^{sf{T})/() }\right)A^.

Substituting

w = A ^{-1} u gives\left(A + uv ^{sf{T}\right)} ^{-1} = \left(I - (A ^{-1} uv ^{sf{T})/() } \right)A^ = A^ - \frac

Generalization (Woodbury matrix identity)

Given a square invertible

n x n matrix A , an n x k matrix U , and a k x n matrix V , let B be an n x n matrix such that B = A + UV . Then, assuming \left(I _{k} + VA ^{-1} U\right) is invertible, we haveB ^{-1} = A ^{-1} - A ^{-1} U \left(I _{k} + VA ^{-1} U\right) ^{-1} VA ^{-1} .

See also

• The matrix determinant lemma performs a rank-1 update to a determinant.
• Woodbury matrix identity
• Quasi-Newton method
• Binomial inverse theorem
• Bunch–Nielsen–Sorensen formula
• Maxwell stress tensor contains an application of the Sherman–Morrison formula.

Notes and References

1. Jack . Sherman . Winifred J. . Morrison . Adjustment of an Inverse Matrix Corresponding to Changes in the Elements of a Given Column or a Given Row of the Original Matrix (abstract) . Annals of Mathematical Statistics . 20 . 621 . 1949 . 10.1214/aoms/1177729959. free.
2. Jack . Sherman . Winifred J. . Morrison . Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix . . 21 . 1 . 124 - 127 . 1950 . 10.1214/aoms/1177729893 . 35118 . 0037.00901. free .
3. William W. . Hager . Updating the inverse of a matrix . SIAM Review . 31 . 1989 . 221 - 239 . 2 . 10.1137/1031049 . 997457 . 2030425 . 7967459 .
4. Maurice S. . Bartlett . An Inverse Matrix Adjustment Arising in Discriminant Analysis . . 22 . 1 . 107 - 111 . 1951 . 10.1214/aoms/1177729698 . 40068 . 0042.38203. free .
5. [Amy Langville|Langville, Amy N.]
6. http://www.alglib.net/matrixops/general/invupdate.php Update of the inverse matrix by the Sherman–Morrison formula
7. [Propagator#Spin 1]
8. Web site: Perturbative quantum field theory.
9. Web site: MathOverflow discussion. MathOverflow.