Sherman-Morrison

(A + uv^ )^-1 = A^-1 - A^-1 u v^ A^-11 + v^ A^-1 u — rank-1 update, rank-1 correction.

The idea

Theorem (Sherman-Morrison formula).

Let $A$ be an invertible $n \times n$ matrix and let $u, v$ be vectors with $1 + v^{\top} A^{-1} u \neq 0$. Then $A + uv^{\top}$ is invertible and $(A + uv^{\top})^{-1} = A^{-1} - \frac{A^{-1} u\, v^{\top} A^{-1}}{1 + v^{\top} A^{-1} u}.$

The formula updates an inverse we already have. The change added to $A$ is an outer product $uv^{\top}$, the matrix whose $(i,j)$ entry is $u_i v_j$; every column of it is a multiple of $u$, so it has rank $1$, the smallest nonzero rank a change can have.

The formula says the correction to the inverse is equally simple: an outer product of the vectors $A^{-1}u$ and $v^{\top}A^{-1}$, divided by a single scalar. Computing it takes a few matrix-vector products and one outer product — work proportional to $n^{2}$ — instead of the $n^{3}$ of inverting $A + uv^{\top}$ from scratch.

The hypothesis $1 + v^{\top} A^{-1} u \neq 0$ cannot be dropped: when that scalar is zero, $A + uv^{\top}$ is singular and has no inverse at all.

Ways to work on it

• Walkthrough. Apply the Sherman-Morrison formula to invert a rank-one update of the identity.
• Practice. Compute the Sherman-Morrison denominator for diagonal A and basis vectors u, v.
• Hardest. Multiple choice on the identities and algorithms that extend the rank-one update idea.

Not sure where to start? Take the ten-question placement test.