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\}\; ight)^\{-1\}=mathbf\{A\}^\{-1\}\; -\; mathbf\{A\}^\{-1\}mathbf\{UB\}left(mathbf\{B\}+mathbf\{BVA\}^\{-1\}mathbf\{UB\}\; ight)^\{-1\}mathbf\{BVA\}^\{-1\}$

provided A and B + BVA^-1UB are nonsingular. Note that if B is invertible, the two B terms flanking the quantity inverse in the right-hand side can be replaced with (B^-1)^-1, which results in

:$left(mathbf\{A\}+mathbf\{UBV\}\; ight)^\{-1\}=mathbf\{A\}^\{-1\}\; -\; mathbf\{A\}^\{-1\}mathbf\{U\}left(mathbf\{B\}^\{-1\}+mathbf\{VA\}^\{-1\}mathbf\{U\}\; ight)^\{-1\}mathbf\{VA\}^\{-1\}$

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

Verification

First notice that :$left(mathbf\{A\}\; +\; mathbf\{UBV\}\; ight)\; mathbf\{A\}^\{-1\}mathbf\{UB\}\; =\; mathbf\{UB\}\; +\; mathbf\{UBVA\}^\{-1\}mathbf\{UB\}\; =\; mathbf\{U\}\; left(mathbf\{B\}\; +\; mathbf\{BVA\}^\{-1\}mathbf\{UB\}\; ight).$

Now multiply the matrix we wish to invert by its alleged inverse :$left(mathbf\{A\}\; +\; mathbf\{UBV\}\; ight)\; left(\; mathbf\{A\}^\{-1\}\; -\; mathbf\{A\}^\{-1\}mathbf\{UB\}left(mathbf\{B\}\; +\; mathbf\{BVA\}^\{-1\}mathbf\{UB\}\; ight)^\{-1\}mathbf\{BVA\}^\{-1\}\; ight)$:$=\; mathbf\{I\}\_p\; +\; mathbf\{UBVA\}^\{-1\}\; -\; mathbf\{U\}\; left(mathbf\{B\}\; +\; mathbf\{BVA\}^\{-1\}mathbf\{UB\}\; ight)\; left(mathbf\{B\}\; +\; mathbf\{BVA\}^\{-1\}mathbf\{UB\}\; ight)^\{-1\}mathbf\{BVA\}^\{-1\}$:$=\; mathbf\{I\}\_p\; +\; mathbf\{UBVA\}^\{-1\}\; -\; mathbf\{U\; BVA\}^\{-1\}\; =\; mathbf\{I\}\_p\; !$

which verifies that it is the inverse.

So we get that -- if A^-1 and $left(mathbf\{B\}\; +\; mathbf\{BVA\}^\{-1\}mathbf\{UB\}\; ight)^\{-1\}$ exist, then $left(mathbf\{A\}\; +\; mathbf\{UBV\}\; ight)^\{-1\}$ exists and is given by the theorem above.cite book | author = Gilbert Strang | title = Introduction to Linear Algebra | edition = 3rd edition | year = 2003 | publisher = Wellesley-Cambridge Press: Wellesley, MA | isbn = 0-9614088-98]

pecial cases

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

:$left(mathbf\{A\}+mathbf\{B\}\; ight)^\{-1\}\; =\; mathbf\{A\}^\{-1\}\; -\; mathbf\{A\}^\{-1\}mathbf\{B\}left(mathbf\{B\}+mathbf\{BA\}^\{-1\}mathbf\{B\}\; ight)^\{-1\}mathbf\{BA\}^\{-1\}.$

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

:$left(mathbf\{A\}+mathbf\{uv\}^mathrm\{T\}\; ight)^\{-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^-1 and one needs to invert matrices of the form A+uv^T quickly.

If we set A = I_"p" and B = I_"q", we get :$left(mathbf\{I\}\_p\; +\; mathbf\{UV\}\; ight)^\{-1\}\; =\; mathbf\{I\}\_p\; -\; mathbf\{U\}left(mathbf\{I\}\_q\; +\; mathbf\{VU\}\; ight)^\{-1\}mathbf\{V\}$

In particular, if "q" = 1, then

:$left(mathbf\{I\}+mathbf\{uv\}^mathrm\{T\}\; ight)^\{-1\}\; =\; mathbf\{I\}\; -\; frac\{mathbf\{uv\}^mathrm\{T\{1+mathbf\{v\}^mathrm\{T\}mathbf\{u.$

ee also

*Woodbury matrix identity
*Sherman-Morrison formula
*Invertible matrix
*Matrix determinant lemma
* For certain cases where "A" is singular and also Moore-Penrose pseudoinverse, see 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, [http://dx.doi.org/10.1137/0613040 DOI 10.1137/0613040] [http://math.nyu.edu/mfdd/riedel/ranksiam.ps preprint] [http://www.ams.org/mathscinet-getitem?mr=1152773 MR 1152773]
* Moore-Penrose pseudoinverse#Updating the pseudoinverse

References