# 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^{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}$ is an invertible square matrix and ${\displaystyle u}$, ${\displaystyle v}$ are vectors. Suppose furthermore that ${\displaystyle 1+v^{T}A^{-1}u\neq 0}$. Then the Sherman–Morrison formula states that

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

Here, ${\displaystyle uv^{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]

## 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^{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^{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}$ times ${\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.

## Verification

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

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

${\displaystyle XY=(A+uv^{T})\left(A^{-1}-{A^{-1}uv^{T}A^{-1} \over 1+v^{T}A^{-1}u}\right)}$
${\displaystyle =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}}$
${\displaystyle =I+uv^{T}A^{-1}-{uv^{T}A^{-1}+uv^{T}A^{-1}uv^{T}A^{-1} \over 1+v^{T}A^{-1}u}}$
${\displaystyle =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 ${\displaystyle v^{T}A^{-1}u}$ is a scalar, so ${\displaystyle (1+v^{T}A^{-1}u)}$ can be factored out, leading to:

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

In the same way, it is verified that

${\displaystyle 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

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

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

${\displaystyle (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}}}$