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, $u v^\textsf$, 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\in\mathbb^$ is an invertible square matrix and $u,v\in\mathbb^n$ are column vectors. Then $A + uv^\textsf$ is invertible iff $1 + v^\textsf A^u \neq 0$. In this case,
:$\left(A + uv^\textsf\right)^ = A^ - .$

Here, $uv^\textsf$ 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^\textsfA^u \neq 0 \Rightarrow A + uv^\textsf$ 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$) if and only if $XY = YX = I$.

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

:\begin
XY &= \left(A + uv^\textsf\right)\left(A^ - \right) \\ pt &= AA^ + uv^\textsfA^ - \\ pt &= I + uv^\textsfA^ - \\ pt &= I + uv^\textsfA^ - \\ pt &= I + uv^\textsfA^ - uv^\textsfA^\\ pt
\end

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

:$YX = \left(A^ - \right)(A + uv^\textsf) = 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^\textsfA^u = 0$, then via the matrix determinant lemma, $\det\!\left(A + uv^\textsf\right)=(1 + v^\textsf A^ u) \det(A) = 0$, so $\left(A + uv^\textsf\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$ (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$ does not have to be computed from scratch (which in general is expensive), but can be computed by correcting (or perturbing) $A^$.

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^$ is a $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 $\left(A + uv^\textsf\right)$. 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.

Alternative verification

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

: $\left(I + wv^\textsf\right)^ = I - \frac$.

Let

:$u = Aw, \quad \text \quad A + uv^\textsf = A\left(I + wv^\textsf\right),$

then

: $\left(A + uv^\textsf\right)^ = \left(I + wv^\textsf\right)^ A^ = \left(I - \frac\right)A^$.

Substituting $w = A^u$ gives

: $\left(A + uv^\textsf\right)^ = \left(I - \frac \right)A^ = A^ - \frac$

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^ U\right)$ is invertible, we have

:$B^ = A^ - A^U \left(I_k + VA^U\right)^ VA^.$

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
* Maxwell stress tensor contains an application of the Sherman–Morrison formula.

References

External links

*

{{DEFAULTSORT:Sherman-Morrison formula
Linear algebra
Matrix theory