Sherman–Morrison formula

From Wikipedia, the free encyclopedia
  (Redirected from Sherman-Morrison formula)
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 . In this case,

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 .

() Reciprocally, if , then letting , one has thus has a non-trivial kernel and is therefore not invertible.

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.

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[8][circular reference]. The inverse propagator (as it appears in the Lagrangian) has the form . 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[9] involving the spin-1 field.

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
  8. ^ Propagator#Spin 1
  9. ^ [1]

External links[edit]