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