Binomial inverse theorem

In mathematics, the binomial inverse theorem is useful for expressing matrix inverses in different ways.

If A, U, B, V are matrices of sizes p×p, p×q, q×q, q×p, respectively, then

\left(\mathbf {A} +\mathbf {UBV} \right)^{-1}=\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\mathbf {UB} \left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right)^{-1}\mathbf {BVA} ^{-1}

provided A and B + BVA⁻¹UB are nonsingular. Nonsingularity of the latter requires that B⁻¹ exist since it equals B(I+VA^—1UB) and the rank of the latter cannot exceed the rank of B.^[1]

Since B is invertible, the two B terms flanking the parenthetical quantity inverse in the right-hand side can be replaced with (B⁻¹)⁻¹, which results in

\left(\mathbf {A} +\mathbf {UBV} \right)^{-1}=\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\mathbf {U} \left(\mathbf {B} ^{-1}+\mathbf {VA} ^{-1}\mathbf {U} \right)^{-1}\mathbf {VA} ^{-1}.

This is the Woodbury matrix identity, which can also be derived using matrix blockwise inversion.

A more general formula exists when B is singular and possibly even non-square:^[1]

(\mathbf {A+UBV} )^{-1}=\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\mathbf {U} (\mathbf {I+BVA} ^{-1}\mathbf {U} )^{-1}\mathbf {BVA} ^{-1}.

Formulas also exist for certain cases in which A is singular.^[2]

Verification

First notice that

\left(\mathbf {A} +\mathbf {UBV} \right)\mathbf {A} ^{-1}\mathbf {UB} =\mathbf {UB} +\mathbf {UBVA} ^{-1}\mathbf {UB} =\mathbf {U} \left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right).

Now multiply the matrix we wish to invert by its alleged inverse:

\left(\mathbf {A} +\mathbf {UBV} \right)\left(\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\mathbf {UB} \left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right)^{-1}\mathbf {BVA} ^{-1}\right)

=\mathbf {I} _{p}+\mathbf {UBVA} ^{-1}-\mathbf {U} \left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right)\left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right)^{-1}\mathbf {BVA} ^{-1}

=\mathbf {I} _{p}+\mathbf {UBVA} ^{-1}-\mathbf {UBVA} ^{-1}=\mathbf {I} _{p}\!

which verifies that it is the inverse.

So we get that if A⁻¹ and $\left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right)^{-1}$ exist, then $\left(\mathbf {A} +\mathbf {UBV} \right)^{-1}$ exists and is given by the theorem above.^[3]

Special cases

First

If p = q and U = V = I_p is the identity matrix, then

\left(\mathbf {A} +\mathbf {B} \right)^{-1}=\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\mathbf {B} \left(\mathbf {B} +\mathbf {BA} ^{-1}\mathbf {B} \right)^{-1}\mathbf {BA} ^{-1}.

Remembering the identity

\left(\mathbf {C} \mathbf {D} \right)^{-1}=\mathbf {D} ^{-1}\mathbf {C} ^{-1},

we can also express the previous equation in the simpler form as

\left(\mathbf {A} +\mathbf {B} \right)^{-1}=\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\left(\mathbf {I} +\mathbf {B} \mathbf {A} ^{-1}\right)^{-1}\mathbf {B} \mathbf {A} ^{-1}.

Continuing with the merging of the terms of the far right-hand side of the above equation results in Hua's identity

\left(\mathbf {A} +\mathbf {B} \right)^{-1}=\mathbf {A} ^{-1}-\left(\mathbf {A} +\mathbf {A} \mathbf {B} ^{-1}\mathbf {A} \right)^{-1}.

Second

If B = I_q is the identity matrix and q = 1, then U is a column vector, written u, and V is a row vector, written v^T. Then the theorem implies the Sherman-Morrison formula:

\left(\mathbf {A} +\mathbf {uv} ^{\mathrm {T} }\right)^{-1}=\mathbf {A} ^{-1}-{\frac {\mathbf {A} ^{-1}\mathbf {uv} ^{\mathrm {T} }\mathbf {A} ^{-1}}{1+\mathbf {v} ^{\mathrm {T} }\mathbf {A} ^{-1}\mathbf {u} }}.

This is useful if one has a matrix A with a known inverse A⁻¹ and one needs to invert matrices of the form A+uv^T quickly for various u and v.

Third

If we set A = I_p and B = I_q, we get

\left(\mathbf {I} _{p}+\mathbf {UV} \right)^{-1}=\mathbf {I} _{p}-\mathbf {U} \left(\mathbf {I} _{q}+\mathbf {VU} \right)^{-1}\mathbf {V} .

In particular, if q = 1, then

\left(\mathbf {I} +\mathbf {uv} ^{\mathrm {T} }\right)^{-1}=\mathbf {I} -{\frac {\mathbf {uv} ^{\mathrm {T} }}{1+\mathbf {v} ^{\mathrm {T} }\mathbf {u} }},

which is a particular case of the Sherman-Morrison formula given above.

References

^ ^a ^b Henderson, H. V., and Searle, S. R. (1981), "On deriving the inverse of a sum of matrices", SIAM Review 23, pp. 53-60 doi:10.1137/1023004 [1].
^ Kurt S. Riedel, "A Sherman–Morrison–Woodbury Identity for Rank Augmenting Matrices with Application to Centering", SIAM Journal on Matrix Analysis and Applications, 13 (1992)659-662, doi:10.1137/0613040 preprint MR1152773
^ Gilbert Strang (2003). Introduction to Linear Algebra (3rd ed.). Wellesley-Cambridge Press: Wellesley, MA. ISBN 0-9614088-9-8.

[HS-1] Henderson, H. V., and Searle, S. R. (1981), "On deriving the inverse of a sum of matrices", SIAM Review 23, pp. 53-60 doi:10.1137/1023004 [1].

[2] Kurt S. Riedel, "A Sherman–Morrison–Woodbury Identity for Rank Augmenting Matrices with Application to Centering", SIAM Journal on Matrix Analysis and Applications, 13 (1992)659-662, doi:10.1137/0613040 preprint MR1152773

[strang-3] Gilbert Strang (2003). Introduction to Linear Algebra (3rd ed.). Wellesley-Cambridge Press: Wellesley, MA. ISBN 0-9614088-9-8.

[1]

[2]

[3]