# 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 $A$ and the outer product, $u v^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.[4]

## Statement

Suppose $A$ is an invertible square matrix and $u$, $v$ are column 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.[5]

## 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.[6] 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[5] and the computation takes $3n^2$ scalar multiplications.[7] 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^TA^{-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^Tw}$

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^Tw} \right)A^{-1}$

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

$( 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}$