Sherman–Morrison formula

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 ${\displaystyle A}$ and the outer product, ${\displaystyle uv^{\textsf {T}}}$, of vectors ${\displaystyle u}$ and ${\displaystyle 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

Suppose ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ is an invertible square matrix and ${\displaystyle u,v\in \mathbb {R} ^{n}}$ are column vectors. Then ${\displaystyle A+uv^{\textsf {T}}}$is invertible iff ${\displaystyle 1+v^{\textsf {T}}A^{-1}u\neq 0}$. In this case,

${\displaystyle \left(A+uv^{\textsf {T}}\right)^{-1}=A^{-1}-{A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}.}$

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

Proof

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

We first verify that the right hand side (${\displaystyle Y}$) satisfies ${\displaystyle XY=I}$.

${\displaystyle {\begin{aligned}XY&=\left(A+uv^{\textsf {T}}\right)\left(A^{-1}-{A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\right)\\[6pt]&=AA^{-1}+uv^{\textsf {T}}A^{-1}-{AA^{-1}uv^{\textsf {T}}A^{-1}+uv^{\textsf {T}}A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\[6pt]&=I+uv^{\textsf {T}}A^{-1}-{uv^{\textsf {T}}A^{-1}+uv^{\textsf {T}}A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\[6pt]&=I+uv^{\textsf {T}}A^{-1}-{u\left(1+v^{\textsf {T}}A^{-1}u\right)v^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\[6pt]&=I+uv^{\textsf {T}}A^{-1}-uv^{\textsf {T}}A^{-1}\\[6pt]\end{aligned}}}$

To end the proof of this direction, we need to show that ${\displaystyle YX=I}$ in a similar way as above:

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

(${\displaystyle \Rightarrow }$) Reciprocally, if ${\displaystyle 1+v^{\textsf {T}}A^{-1}u=0}$, then letting ${\displaystyle x=A^{-1}u}$, ${\displaystyle \left(A+uv^{\textsf {T}}\right)}$ has a non-regular kernel and is therefore not invertible.

Application

If the inverse of ${\displaystyle A}$ is already known, the formula provides a numerically cheap way to compute the inverse of ${\displaystyle A}$ corrected by the matrix ${\displaystyle uv^{\textsf {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 ${\displaystyle A+uv^{\textsf {T}}}$ does not have to be computed from scratch (which in general is expensive), but can be computed by correcting (or perturbing) ${\displaystyle A^{-1}}$.

Using unit columns (columns from the identity matrix) for ${\displaystyle u}$ or ${\displaystyle v}$, individual columns or rows of ${\displaystyle A}$ may be manipulated and a correspondingly updated inverse computed relatively cheaply in this way.[6] In the general case, where ${\displaystyle A^{-1}}$ is a ${\displaystyle n}$-by-${\displaystyle n}$ matrix and ${\displaystyle u}$ and ${\displaystyle v}$ are arbitrary vectors of dimension ${\displaystyle n}$, the whole matrix is updated[5] and the computation takes ${\displaystyle 3n^{2}}$ scalar multiplications.[7] If ${\displaystyle u}$ is a unit column, the computation takes only ${\displaystyle 2n^{2}}$ scalar multiplications. The same goes if ${\displaystyle v}$ is a unit column. If both ${\displaystyle u}$ and ${\displaystyle v}$ are unit columns, the computation takes only ${\displaystyle 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.[8] The inverse propagator (as it appears in the Lagrangian) has the form ${\displaystyle \left(A+uv^{\textsf {T}}\right)}$. 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

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

${\displaystyle \left(I+wv^{\textsf {T}}\right)^{-1}=I-{\frac {wv^{\textsf {T}}}{1+v^{\textsf {T}}w}}}$.

Let

${\displaystyle u=Aw,\quad {\text{and}}\quad A+uv^{\textsf {T}}=A\left(I+wv^{\textsf {T}}\right),}$

then

${\displaystyle \left(A+uv^{\textsf {T}}\right)^{-1}=\left(I+wv^{\textsf {T}}\right)^{-1}A^{-1}=\left(I-{\frac {wv^{\textsf {T}}}{1+v^{\textsf {T}}w}}\right)A^{-1}}$.

Substituting ${\displaystyle w=A^{-1}u}$ gives

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

Generalization (Woodbury matrix identity)

Given a square invertible ${\displaystyle n\times n}$ matrix ${\displaystyle A}$, an ${\displaystyle n\times k}$ matrix ${\displaystyle U}$, and a ${\displaystyle k\times n}$ matrix ${\displaystyle V}$, let ${\displaystyle B}$ be an ${\displaystyle n\times n}$ matrix such that ${\displaystyle B=A+UV}$. Then, assuming ${\displaystyle \left(I_{k}+VA^{-1}U\right)}$ is invertible, we have

${\displaystyle B^{-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 you can found application of SM formula.

References

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" (PDF). SIAM Review. 31 (2): 221–239. doi:10.1137/1031049. JSTOR 2030425. MR 0997457.
5. 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

External links

• Weisstein, Eric W. "Sherman–Morrison formula". MathWorld.