Sherman–Morrison formula

From Wikipedia, the free encyclopedia

In mathematics, in particular linear algebra, the Sherman–Morrison formula^[1] computes the inverse of the sum of an invertible matrix $A$ and the dyadic product, $u v$ , of a column vector $u$ and a row vector $v$ . The Sherman–Morrison formula is a special case of the Woodbury formula.

1 Definition
2 Application
3 Proof
4 References
5 External links

[edit] Definition

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

$(A+uv)^{-1} = A^{-1} - {A^{-1}uvA^{-1} \over 1 + vA^{-1}u}.$

Here, uv is the dyadic product of two vectors u and v.

[edit] Application

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 $u v$ (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 + u v$ 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 vectors for $u$ or $v$ , individual columns or rows of $A$ may be manipulated and a correspondingly updated inverse computed relatively cheaply in this way.

[edit] Proof

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 + u v$ ) if and only if $X Y = Y X = I$ .

We first verify that the right hand side ( $Y$ ) satisfies $X Y = I$ . Note that $v A - 1 u$ is a scalar and can be factored out.

$XY = (A + uv)\left( A^{-1} - {A^{-1} uv A^{-1} \over 1 + vA^{-1}u}\right)$

$= AA^{-1} + uvA^{-1} - {AA^{-1}uvA^{-1} + uvA^{-1}uvA^{-1} \over 1 + vA^{-1}u}$

$= I + uvA^{-1} - {uvA^{-1} + uvA^{-1}uvA^{-1} \over 1 + vA^{-1}u}$

$= I + uvA^{-1} - {(1 + vA^{-1}u) uvA^{-1} \over 1 + vA^{-1}u}$

$= I + uvA^{-1} - uvA^{-1}\,$

= I .

In the same way, we can verify that

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

[edit] References

^ William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling, Numerical Recipes in C: The Art of Scientific Computing, pp.73+. Cambridge University Press (1992). ISBN 0-521-43108-5.