Sherman–Morrison formula - Misplaced Pages

Formula computing the inverse of the sum of a matrix and the outer product of two vectors

In linear algebra, the Sherman–Morrison formula, named after Jack Sherman and Winifred J. Morrison, computes the inverse of a "rank-1 update" to a matrix whose inverse has previously been computed. That is, given an invertible matrix $A$ and the outer product $uv^{\textsf {T}}$ of vectors $u$ and $v,$ the formula cheaply computes an updated matrix inverse ${\textstyle \left(A+uv^{\textsf {T}}\right){\vphantom {)}}^{\!-1}.}$

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\in \mathbb {R} ^{n\times n}$ is an invertible square matrix and $u,v\in \mathbb {R} ^{n}$ are column vectors. Then $A+uv^{\textsf {T}}$ is invertible if and only if $1+v^{\textsf {T}}A^{-1}u\neq 0$ . In this case,

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

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

Proof

( $\Leftarrow$ ) To prove that the backward direction $1+v^{\textsf {T}}A^{-1}u\neq 0\Rightarrow A+uv^{\textsf {T}}$ is invertible with inverse given as above) is true, 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^{\textsf {T}}$ ) if and only if $XY=YX=I$ .

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

{\begin{aligned}XY&=\left(A+uv^{\textsf {T}}\right)\left(A^{-1}-{A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\right)\\&=AA^{-1}+uv^{\textsf {T}}A^{-1}-{AA^{-1}uv^{\textsf {T}}A^{-1}+uv^{\textsf {T}}A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\&=I+uv^{\textsf {T}}A^{-1}-{uv^{\textsf {T}}A^{-1}+uv^{\textsf {T}}A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\&=I+uv^{\textsf {T}}A^{-1}-{u\left(1+v^{\textsf {T}}A^{-1}u\right)v^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\&=I+uv^{\textsf {T}}A^{-1}-uv^{\textsf {T}}A^{-1}\\&=I\end{aligned}}

To end the proof of this direction, we need to show that $YX=I$ in a similar way as above:

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

(In fact, the last step can be avoided since for square matrices $X$ and $Y$ , $XY=I$ is equivalent to $YX=I$ .)

( $\Rightarrow$ ) Reciprocally, if $1+v^{\textsf {T}}A^{-1}u=0$ , then via the matrix determinant lemma, $\det \!\left(A+uv^{\textsf {T}}\right)=(1+v^{\textsf {T}}A^{-1}u)\det(A)=0$ , so $\left(A+uv^{\textsf {T}}\right)$ is not invertible.

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^{\textsf {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^{\textsf {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 an $n$ -by- $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.

This formula also has application in theoretical physics. Namely, in quantum field theory, one uses this formula to calculate the propagator of a spin-1 field. The inverse propagator (as it appears in the Lagrangian) has the form $A+uv^{\textsf {T}}$ . One uses the Sherman–Morrison formula to calculate the inverse (satisfying certain time-ordering boundary conditions) of the inverse propagator—or simply the (Feynman) propagator—which is needed to perform any perturbative calculation involving the spin-1 field.

One of the issues with the formula is that little is known about its numerical stability. There are no published results concerning its error bounds. Anecdotal evidence suggests that the Woodbury matrix identity (a generalization of the Sherman–Morrison formula) may diverge even for seemingly benign examples (when both the original and modified matrices are well-conditioned).

Alternative verification

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

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

Let

u=Aw,\quad {\text{and}}\quad A+uv^{\textsf {T}}=A\left(I+wv^{\textsf {T}}\right),

then

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

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

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

Generalization (Woodbury matrix identity)

Given a square invertible $n\times n$ matrix $A$ , an $n\times k$ matrix $U$ , and a $k\times n$ matrix $V$ , let $B$ be an $n\times n$ matrix such that $B=A+UV$ . Then, assuming $\left(I_{k}+VA^{-1}U\right)$ is invertible, we have