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 T , 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.
Suppose A is an invertible square matrix and u , v are column vectors. Suppose furthermore that 1 + v T A − 1 u ≠ 0 . Then the Sherman–Morrison formula states that
( A + u v T ) − 1 = A − 1 − A − 1 u v T A − 1 1 + v T A − 1 u . Here, u v T is the outer product of two vectors u and v . The general form shown here is the one published by Bartlett.
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 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 a n -by- n matrix and u and v are arbitrary vectors of dimension n , the whole matrix is updated and the computation takes 3 n 2 scalar multiplications. If u is a unit column, the computation takes only 2 n 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.
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 .
We first verify that the right hand side ( Y ) satisfies X Y = I .
X Y = ( A + u v T ) ( A − 1 − A − 1 u v T A − 1 1 + v T A − 1 u ) = A A − 1 + u v T A − 1 − A A − 1 u v T A − 1 + u v T A − 1 u v T A − 1 1 + v T A − 1 u = I + u v T A − 1 − u v T A − 1 + u v T A − 1 u v T A − 1 1 + v T A − 1 u = I + u v T A − 1 − u ( 1 + v T A − 1 u ) v T A − 1 1 + v T A − 1 u = I + u v T A − 1 − u v T A − 1 1 + v T A − 1 u is a scalar = I In the same way, one can verify that:
Y X = ( A − 1 − A − 1 u v T A − 1 1 + v T A − 1 u ) ( A + u v T ) = I . Following is an alternate verification of the Sherman–Morrison formula using the easily verifiable identity
( I + w v T ) − 1 = I − w v T 1 + v T w Let
u = A w , and A + u v T = A ( I + w v T ) , then
( A + u v T ) − 1 = ( I + w v T ) − 1 A − 1 = ( I − w v T 1 + v T w ) A − 1 Substituting w = A − 1 u gives
( A + u v T ) − 1 = ( I − A − 1 u v T 1 + v T A − 1 u ) A − 1 = A − 1 − A − 1 u v T A − 1 1 + v T A − 1 u Given a square invertible n × n matrix A , an n × k matrix U , and a k × n matrix V , let B be an n × n matrix such that B = A + U V . Then, assuming ( I k + V A − 1 U ) is invertible, we have
B − 1 = A − 1 − A − 1 U ( I k + V A − 1 U ) − 1 V A − 1 