Sherman–Morrison formula

From Wikipedia, the free encyclopedia
Jump to navigation Jump to 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 and the outer product, , of vectors and . 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 is an invertible square matrix and , are column vectors. Then is invertible iff . If is invertible, then its inverse is given by

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

Proof[edit]

() To prove that the backward direction ( is invertible with inverse given as above) is true, we verify the properties of the inverse. A matrix (in this case the right-hand side of the Sherman–Morrison formula) is the inverse of a matrix (in this case ) if and only if .

We first verify that the right hand side () satisfies .

In the same way, one can verify that:

() To prove the reverse direction, we suppose that , otherwise the result is trivial. Then,

Since is assumed invertible, is invertible as the product of invertible matrices. Thus, by our assumption that , we have that . By the identity above, this means that , and hence , as was to be shown.

Application[edit]

If the inverse of is already known, the formula provides a numerically cheap way to compute the inverse of corrected by the matrix (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 does not have to be computed from scratch (which in general is expensive), but can be computed by correcting (or perturbing) .

Using unit columns (columns from the identity matrix) for or , individual columns or rows of may be manipulated and a correspondingly updated inverse computed relatively cheaply in this way.[6] In the general case, where is a -by- matrix and and are arbitrary vectors of dimension , the whole matrix is updated[5] and the computation takes scalar multiplications.[7] If is a unit column, the computation takes only scalar multiplications. The same goes if is a unit column. If both and are unit columns, the computation takes only scalar multiplications.

Alternative verification[edit]

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

.

Let

then

.

Substituting gives

Generalization (Woodbury matrix identity)[edit]

Given a square invertible matrix , an matrix , and a matrix , let be an matrix such that . Then, assuming is invertible, we have

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 0035118. 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 0997457. 
  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 0040068. 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]