[Linear Algebra] Sherman-Morrison and Woodbury Formulas
Matrix Determinant Lemma
$\mathbf{Lemma\ 1.}$ $\text{det}(I_n + UV^\top) = \text{det}(I_k + V^\top U)$
$\mathbf{Proof.}$
Consider the following matrix multiplication:
\[\begin{aligned} \left[\begin{array}{cc} I_n & \mathbf{0} \\ V^{\top} & I_k \end{array}\right]\left[\begin{array}{cc} I_n+U V^{\top} & U \\ \mathbf{0} & I_k \end{array}\right]\left[\begin{array}{cc} I_n & \mathbf{0} \\ -V^{\top} & I_k \end{array}\right] \end{aligned}\]where $U$ and $V$ are $n \times k$ matrices. Note that the multiplication of the first two matrices is
\[\begin{aligned} \left[\begin{array}{cc} I_n+U V^{\top} & U \\ V^{\top}+V^{\top} U V^{\top} & I_k+V^{\top} U \end{array}\right] \end{aligned}\]Thus, the result of the multiplication is
\[\begin{aligned} \left[\begin{array}{cc} I_n & U \\ \mathbf{0} & I_k+V^{\top} U \end{array}\right] \end{aligned}\]Done by $\text{det}(AB) = \text{det}(A) \text{det}(B)._\blacksquare$
$\mathbf{Lemma\ 2.}$ Matrix Determinant Lemma
Let $A$ be an $n \times n$ invertible matrix, and $U$ and $V$ be $n \times k$ matrices. Then,
$\mathbf{Proof.}$
Note that $A + UV^\top = A(I_n + A^{-1} U V^\top$. Then,
\[\begin{align*} \operatorname{det}\left(A+U V^{\top}\right) &= \text{det}(A) \operatorname{det}\left(I_n + A^{-1} UV^\top\right) \\ &= \operatorname{det}(A) \operatorname{det}\left(I_k+V^{\top} A^{-1} U\right) \end{align*}\]by plugging $A^{-1} U$ into $U$ in $\mathbf{Lemma\ 1}._\blacksquare$
Woodbury Formula
Let $A$ be an $n \times n$ invertible matrix, and $U$ and $V$ be $n \times k$ matrices. Then, $I_k + V^\top A^{-1} U$ is invertible if and only if $A + UV^\top$ is invertible. In such case,
\[\left(A+U V^{\top}\right)^{-1}=A^{-1}-A^{-1} U\left(I_k+V^{\top} A^{-1} U\right)^{-1} V^{\top} A^{-1}\]$\mathbf{Proof.}$
Invertibility is obvious from $\mathbf{Lemma\ 2}$. Now, suppose $A + UV^\top$ is invertible. Then by determinant lemma, $I_k + V^\top A^{-1} U$ is invertible, too.
First, let’s find the inverse of $I_n + UV^\top$. Consider the form of $I_n + UBV^\top$ with some $k \times k$ matrix $B$ as a candidate. Then,
\[\begin{aligned} \left(I_n+U V^{\top}\right)\left(I_n+U B V^{\top}\right)=I_n+U V^{\top}+U B V^{\top}+U V^{\top} U B V^{\top}=I_n+U\left(I_k+B+V^{\top} U B\right) V^{\top} \end{aligned}\]So, $I_k + B + V^\top U B = \mathbf{0}$ is necessary and sufficient condition for invertibility of $I_n + UV^\top$. From
\[\begin{aligned} -I_k=B+V^{\top} U B=\left(I_k+V^{\top} U\right) B \end{aligned}\]we obtain $B = -(I_k + V^\top U)^{-1}$. Thus, $(I_n + UV^\top)^{-1} = I_n - U (I_k + V^\top U)^{-1} V^\top$.
Finally, the inverse of $A + UV^\top$ is
\[\begin{aligned} \left(A+U V^{\top}\right)^{-1} & =\left(A\left(I_n+A^{-1} U V^{\top}\right)\right)^{-1} \\ & =\left(I_n+A^{-1} U V^{\top}\right)^{-1} A^{-1} \\ & =\left(I_n-A^{-1} U\left(I_k+V^{\top} A^{-1} U\right)^{-1} V^{\top}\right) A^{-1} \\ & =A^{-1}-A^{-1} U\left(I_k+V^{\top} A^{-1} U\right)^{-1} V^{\top} A^{-1} \end{aligned}\]Sherman-Morrison Formula
Let $A$ be an $n \times n$ invertible matrix, and $\mathbf{u}$ and $\mathbf{v}$ be $\mathbb{R}^n$ vector. Then, $1 + \mathbf{v}^\top A^{-1} \mathbf{u} \neq 0$ if and only if $A + \mathbf{uv}^\top$ is invertible. In such case,
\[\begin{aligned} \left(A+\mathbf{u} \mathbf{v}^{\top}\right)^{-1}=A^{-1}-\frac{A^{-1} \mathbf{u v}^{\top} A^{-1}}{1+\mathbf{v}^{\top} A^{-1} \mathbf{u}} \end{aligned}\]$\mathbf{Proof.}$
Special case of Woodbury Formula.
Leave a comment