Sherman–Morrison formula

In mathematics, in particular linear algebra, the Sherman–Morrison formula, named after Jack Sherman and Winifred J. Morrison, computes the inverse of the sum of an invertible matrix $A$ and the outer product, $uv^{T}$, of vectors $u$ and $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.

Statement

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

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

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

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 $uv^{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 $A+uv^{T}$ 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 columns (columns from the identity matrix) for $u$ or $v$, individual columns or rows of $A$ may be manipulated and a correspondingly updated inverse computed relatively cheaply in this way. In the general case, where $A^{-1}$ is a $n$ times $n$ matrix and $u$ and $v$ are arbitrary vectors of dimension $n$, the whole matrix is updated and the computation takes $3n^{2}$ scalar multiplications. If $u$ is a unit column, the computation takes only $2n^{2}$ scalar multiplications. The same goes if $v$ is a unit column. If both $u$ and $v$ are unit columns, the computation takes only $n^{2}$ scalar multiplications.

Verification

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+uv^{T}$) if and only if $XY=YX=I$.

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

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

$=AA^{-1}+uv^{T}A^{-1}-{AA^{-1}uv^{T}A^{-1}+uv^{T}A^{-1}uv^{T}A^{-1} \over 1+v^{T}A^{-1}u}$

$=I+uv^{T}A^{-1}-{uv^{T}A^{-1}+uv^{T}A^{-1}uv^{T}A^{-1} \over 1+v^{T}A^{-1}u}$

$=I+uv^{T}A^{-1}-{u(1+v^{T}A^{-1}u)v^{T}A^{-1} \over 1+v^{T}A^{-1}u}$

Note that $v^{T}A^{-1}u$ is a scalar, so $(1+v^{T}A^{-1}u)$ can be factored out, leading to:

$XY=I+uv^{T}A^{-1}-uv^{T}A^{-1}=I.\,$

In the same way, it is verified that

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

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

$(I+wv^{T})^{-1}=I-{\frac {wv^{T}}{1+v^{T}w}}$

Let $u=Aw$ and $A+uv^{T}=A\left(I+wv^{T}\right)$, then

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

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

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

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

External links

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