Sherman–Morrison formula

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged into Woodbury_matrix_identity. (Discuss)

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 dyadic product, $u v T$ , of a column vector $u$ and a row vector $v T$ . The Sherman–Morrison formula is a special case of the Woodbury formula.

1 Statement
2 Application
3 Verification
4 See also
5 References
6 External links

[edit] 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, $u v T$ is the dyadic product of two vectors u and v. The general form shown here is the one published by Bartlett^[4].

[edit] 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 $u v 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 + u v 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 vectors 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 $m$ matrix and $u$ and $v$ are arbitrary vectors (in which case the whole matrix is updated)^[4], the computation takes $3 m n$ scalar multiplications^[5].

If $u$ is a unit vector, only one row of $A - 1$ is updated^[1] and the computation takes only $2 m n$ scalar multiplications. The same goes if $v$ is a unit vector, in which case only one column of $A - 1$ is updated.

If both $u$ and $v$ are unit vectors, only a single element of $A - 1$ is updated^[2] and the computation takes only $m n$ scalar multiplications.

[edit] 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 + u v T$ ) if and only if $X Y = Y X = I$ .