Sherman–Morrison formula

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

In mathematics, in particular linear algebra, the Sherman–Morrison formula,[1][2][3] named after Jack Sherman and Winifred J. Morrison, computes the inverse of the sum of an invertible matrix A and the outer product, u v^T, of vectors u and v. The Sherman–Morrison formula is a special case of the Woodbury formula. Though named after Sherman and Morrison, it appeared already in earlier publications.[4]

Statement[edit]

Suppose A is an invertible square matrix and u, v are vectors. Suppose furthermore that 1 + v^T A^{-1}u \neq 0. Then the Sherman–Morrison formula states that

(A+uv^T)^{-1} = A^{-1} - {A^{-1}uv^T A^{-1} \over 1 + v^T A^{-1}u}.

Here, uv^T is the outer product of two vectors u and v. The general form shown here is the one published by Bartlett.[5]

Application[edit]

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^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^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.[6] In the general case, where A^{-1} is a n times n matrix and u and v are arbitrary vectors of dimension n, the whole matrix is updated[5] and the computation takes 3n^2 scalar multiplications.[7] If u is a unit column, the computation takes only 2n^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.

Verification[edit]

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^T) if and only if XY = YX = I.

We first verify that the right hand side (Y) satisfies XY = I.

XY = (A + uv^T)\left( A^{-1} - {A^{-1} uv^T A^{-1} \over 1 + v^T A^{-1}u}\right)
= AA^{-1} +  uv^T A^{-1} - {AA^{-1}uv^T A^{-1} + uv^T A^{-1}uv^T A^{-1} \over 1 + v^TA^{-1}u}
= I +  uv^T A^{-1} - {uv^T A^{-1} + uv^T A^{-1}uv^T A^{-1} \over 1 + v^T A^{-1}u}
= I + uv^T A^{-1} - {u(1 + v^T A^{-1}u) v^T A^{-1} \over 1 + v^T A^{-1}u}

Note that v^T A^{-1}u is a scalar, so (1+v^T A^{-1}u) can be factored out, leading to:

XY= I + uv^T A^{-1} - uv^T A^{-1} = I.\,

In the same way, it is verified that

YX = \left(A^{-1} - {A^{-1}uv^T A^{-1} \over 1 + v^T A^{-1}u}\right)(A + uv^T) = I.

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

( I+wv^T )^{-1}=I-\frac{wv^T}{1+v^Tw}

Let u=Aw and A+uv^T=A\left( I+wv^T \right), then

( A+uv^T )^{-1}=( I+wv^T )^{-1}{A^{-1}}=\left( I-\frac{wv^T}{1+v^Tw} \right)A^{-1}

Substituting w={{A}^{-1}}u gives

( A+uv^T )^{-1}=\left( I-\frac{A^{-1}uv^T}{1+v^TA^{-1}u} \right)A^{-1}= {A^{-1}}-\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}

See also[edit]

References[edit]

  1. ^ Sherman, Jack; Morrison, Winifred J. (1949). "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. doi:10.1214/aoms/1177729959. 
  2. ^ Sherman, Jack; Morrison, Winifred J. (1950). "Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix". Annals of Mathematical Statistics 21 (1): 124–127. doi:10.1214/aoms/1177729893. MR 35118. Zbl 0037.00901. 
  3. ^ Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007), "Section 2.7.1 Sherman–Morrison Formula", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8 
  4. ^ Hager, William W. (1989). "Updating the inverse of a matrix". SIAM Review 31 (2): 221–239. doi:10.1137/1031049. JSTOR 2030425. MR 997457. 
  5. ^ a b Bartlett, Maurice S. (1951). "An Inverse Matrix Adjustment Arising in Discriminant Analysis". Annals of Mathematical Statistics 22 (1): 107–111. doi:10.1214/aoms/1177729698. MR 40068. Zbl 0042.38203. 
  6. ^ Langville, Amy N.; and Meyer, Carl D.; "Google's PageRank and Beyond: The Science of Search Engine Rankings", Princeton University Press, 2006, p. 156
  7. ^ Update of the inverse matrix by the Sherman–Morrison formula

External links[edit]