In this post, I am going to motivate an intuitive derivation of the
Sherman-Morrison
formula
using Schur complements.
Recall the following fact (see also this Wikipedia
entry on Schur
complements).
Lemma 1. Let M∈R(n+m)×(n+m) be a block
matrix with blocks M=(ACBD). If A is invertible, then there exist
invertible matrices P1, Q1∈Rn×n such that
P1MQ1=(A−BD−1CD). Similarly, if D is invertible, then
there exist invertible matrices P2, Q2∈Rn×n
such that P2MQ2=(AD−CA−1B).
For the purposes of this post, we won’t need to know what Pi and
Qi look like. It is enough to know that these matrices and their
inverses have simple forms.
We will apply
Lemma 1
to the matrix (Ac⊺b1), where A∈Rn×n is
invertible and b, c∈Rn. For notational convenience,
let P=P1P2−1 and Q=Q2−1Q1. We have that
(A−bc⊺1)=P(A1−c⊺A−1b)Q. This identity tells us that
A−bc⊺ is invertible if and only if 1−c⊺A−1b
is invertible, i.e., nonzero. Finally, inverting both sides of the
equation, we have that ((A−bc⊺)−11)=Q−1(A−11−c⊺A−1b1)P−1. In particular, the top left block of
the matrix on the right is the inverse of A−bc⊺.
Looking back at the derivation, the main idea was to use a change of
variables (the Pi, Qi matrices) to “shift” the inversion of
A−bc⊺, an a priori difficult task, to the inversion of
the scalar 1−c⊺A−1b, a much simpler task. This
generalizes in a number of ways. For example, the same derivation
applied to the (n+m)×(n+m) dimensional block matrix
(AC⊺BIm), where A∈Rn×n is
invertible and B, C∈Rn×m, gives a formula for
the inverse of A−BC⊺ in terms of the inverses of A and
I−C⊺A−1B. This latter formula is known as the Woodbury
matrix identity.