Service level

2014-01-27T19:28:27Z

12.18.100.126: /* Service level */

In [[mathematics]], in particular [[linear algebra]], the '''Sherman–Morrison formula''',<ref name="SM1949">{{cite journal
|first=Jack |last=Sherman
|first2=Winifred J. |last2=Morrison
|title=Adjustment of an Inverse Matrix Corresponding to Changes in the Elements of a Given Column or a Given Row of the Original Matrix (abstract)
|journal=Annals of Mathematical Statistics
|volume=20 |pages=621 |year=1949
|doi=10.1214/aoms/1177729959 }}</ref><ref name="SM1950">{{cite journal
|first=Jack |last=Sherman
|first2=Winifred J. |last2=Morrison
|title=Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix
|journal=[[Annals of Mathematical Statistics]]
|volume=21 |issue=1 |pages=124–127 |year=1950
|doi=10.1214/aoms/1177729893 |mr=35118 | zbl=0037.00901 }}</ref><ref name="PFTV1992">{{Citation
|last1=Press |first1=William H.
|last2=Teukolsky |first2=Saul A.
|last3=Vetterling |first3=William T.
|last4=Flannery |first4=Brian P.
|title=Numerical Recipes: The Art of Scientific Computing |edition=3rd |year=2007 |publisher=Cambridge University Press |publication-place=New York
|isbn=978-0-521-88068-8
|chapter=Section 2.7.1 Sherman–Morrison Formula
|chapter-url=http://apps.nrbook.com/empanel/index.html?pg=76 }}</ref> named after Jack Sherman and Winifred J. Morrison, computes the inverse of the sum of an [[inverse matrix|invertible]] [[matrix (mathematics)|matrix]] <math>A</math>
and the [[outer product]], <math>u v^T</math>, of [[vector (mathematics)|vectors]] <math>u</math> and <math>v</math>. The Sherman–Morrison formula is a special case of the [[Woodbury matrix identity|Woodbury formula]].
Though named after Sherman and Morrison, it appeared already in earlier publications.<ref name="hager">{{cite journal
|first=William W. |last=Hager
|title=Updating the inverse of a matrix
|journal=SIAM Review
|volume=31 |year=1989 |pages=221–239 |issue=2
|doi=10.1137/1031049 |mr=997457 |jstor=2030425 }}</ref>

== Statement ==
Suppose <math>A</math> is an [[invertible]] [[square matrix]] and <math>u</math>, <math>v</math> are [[Vector (geometric)|vectors]]. Suppose furthermore that <math>1 + v^T A^{-1}u \neq 0</math>. Then the Sherman–Morrison formula states that
:<math>(A+uv^T)^{-1} = A^{-1} - {A^{-1}uv^T A^{-1} \over 1 + v^T A^{-1}u}.</math>

Here, <math>uv^T</math> is the [[outer product]] of two vectors <math>u</math> and <math>v</math>. The general form shown here is the one published by Bartlett.<ref name="B1951">{{cite journal
|first=Maurice S. |last=Bartlett
|title=An Inverse Matrix Adjustment Arising in Discriminant Analysis
|journal=[[Annals of Mathematical Statistics]]
|volume=22 |issue=1 |pages=107–111 |year=1951
|doi=10.1214/aoms/1177729698 |mr=40068 | zbl = 0042.38203
}}</ref>

==Application==

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

Using [[unit column]]s (columns from the [[identity matrix]]) for <math>u</math> or <math>v</math>, individual columns or rows of <math>A</math> may be manipulated
and a correspondingly updated inverse computed relatively cheaply in this way.<ref>Langville, Amy N.; and Meyer, Carl D.; "Google's PageRank and Beyond: The Science of Search Engine Rankings", Princeton University Press, 2006, p. 156</ref> In the general case, where <math>A^{-1}</math> is a <math>n</math> times <math>n</math> matrix
and <math>u</math> and <math>v</math> are arbitrary vectors of dimension <math>n</math>, the whole matrix is updated<ref name="B1951" /> and the computation takes <math>3n^2</math> scalar multiplications.<ref>[http://www.alglib.net/matrixops/general/invupdate.php Update of the inverse matrix by the Sherman–Morrison formula]</ref> If <math>u</math> is a unit column, the computation takes only <math>2n^2</math> scalar multiplications. The same goes if <math>v</math> is a unit column. If both <math>u</math> and <math>v</math> are unit columns, the computation takes only <math>n^2</math> scalar multiplications.

==Verification==

We verify the properties of the inverse.
A matrix <math>Y</math> (in this case the right-hand side of the Sherman–Morrison formula)
is the inverse of a matrix <math>X</math> (in this case <math>A+uv^T</math>)
if and only if <math>XY = YX = I</math>.

We first verify that the right hand side (<math>Y</math>) satisfies <math>XY = I</math>.
:<math>XY = (A + uv^T)\left( A^{-1} - {A^{-1} uv^T A^{-1} \over 1 + v^T A^{-1}u}\right)</math>

::<math>= 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}</math>

::<math>= I + uv^T A^{-1} - {uv^T A^{-1} + uv^T A^{-1}uv^T A^{-1} \over 1 + v^T A^{-1}u}</math>

::<math>= I + uv^T A^{-1} - {u(1 + v^T A^{-1}u) v^T A^{-1} \over 1 + v^T A^{-1}u}</math>
Note that <math>v^T A^{-1}u</math> is a scalar, so <math>(1+v^T A^{-1}u)</math> can be factored out, leading to:
:<math>XY= I + uv^T A^{-1} - uv^T A^{-1} = I.\,</math>

In the same way, it is verified that

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

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

: <math>( I+wv^T )^{-1}=I-\frac{wv^T}{1+v^Tw}</math>

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

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

Substituting <math>w={{A}^{-1}}u</math> gives

: <math>( 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}</math>

== 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]]

== References ==
{{reflist}}

== External links ==
* {{MathWorld|title=Sherman–Morrison formula|urlname=Sherman-MorrisonFormula}}

{{DEFAULTSORT:Sherman-Morrison formula}}
[[Category:Linear algebra]]
[[Category:Matrix theory]]

formulasearchengine - User contributions [en]

Service level