Insightful proofs for Sherman-Morrison Formula and Matrix Determinant Lemma

Question

There are two statement about a matrix under rank-one updates that I would be grateful if you give me some insightful proofs.

Suppose $A$ be a nonsingular $n \times n$ matrix and $\mathbf{u},\mathbf{v}$ be vectors.

First, the Sherman-Morrison formula states that:

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

(We can prove this by verifying that the RHS multiplied by $A + \mathbf{u} \mathbf{v}^T$ is $I$.)

Second, Matrix Determinant Lemma states that:

$$\det\left(A+\mathbf{u}\mathbf{v}^T\right) = \det(A) \left( 1 + \mathbf{v}^T A^{-1}\mathbf{u} \right).$$

(In the proof from wikipedia, we just have to verify some identity again.)

It's easy to verify these proofs but it's not clear to me how to come up with the identity. Are there any other proofs which are not just by multiplication of matrices, and give us some insight ? Or even some informal explanation ?

Answer 1

I should preface this with a disclaimer. It may not be the kind of insight you are looking for and certainly not as insightful as the previous answers, but it is a very direct derivation only requiring the most basic knowledge of linear algebra.

Suppose you wish to solve the following for $\mathbf{x}$:

$$\left(A+\mathbf{uv}^T\right)\mathbf{x}=\mathbf{y}$$ $$A\mathbf{x}=\mathbf{y}-\mathbf{uv}^T\mathbf{x}$$ $$\mathbf{x}=A^{-1}\mathbf{y}-A^{-1}\mathbf{uv}^T\mathbf{x}$$

Notice that $\mathbf{v}^T\mathbf{x}$ is a scalar, let us call it $s$.

So the solution for $\mathbf{x}$ in terms of $s$ is:

$$\mathbf{x}=A^{-1}\mathbf{y}-A^{-1}\mathbf{u}s$$

And solving for $s$:

$$s=\mathbf{v}^T\mathbf{x}=\mathbf{v}^TA^{-1}\mathbf{y}-\mathbf{v}^TA^{-1}\mathbf{u}s$$ $$\left(1+\mathbf{v}^TA^{-1}\mathbf{u}\right)s=\mathbf{v}^TA^{-1}\mathbf{y}$$ $$s=\frac{\mathbf{v}^TA^{-1}\mathbf{y}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}$$

Substituting for $s$ in the solution for $\mathbf{x}$: $$\mathbf{x}=A^{-1}\mathbf{y}-\frac{A^{-1}\mathbf{uv}^TA^{-1}\mathbf{y}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}$$

Or:

$$\mathbf{x}=\left(A^{-1}-\frac{A^{-1}\mathbf{uv}^TA^{-1}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}\right)\mathbf{y}$$

So:

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

Answer 2

Look first at $I + \mathbf{u}\mathbf{v}^\top$. This may require factoring $A + \mathbf{u}\mathbf{v}^\top = A\left(I + A^{-1}\mathbf{u}\mathbf{v}^\top\right)$ which may help the intuition for the term $A^{-1}\mathbf{u}$ in the formulas.

Consider how $I + \mathbf{u}\mathbf{v}^\top$ acts on the vector $\mathbf{u}$: $$\left(I + \mathbf{u}\mathbf{v}^\top\right)\mathbf{u} = \mathbf{u} + \mathbf{u}\mathbf{v}^\top\mathbf{u} = \left(1+\mathbf{v}^\top\mathbf{u}\right)\mathbf{u}$$

This shows that $\mathbf{u}$ is a right eigenvector with eigenvalue of $1+\mathbf{v}^\top\mathbf{u}$. The inverse must have the same eigenvector but with eigenvalue $(1+\mathbf{v}^\top\mathbf{u})^{-1}$. (If $\mathbf{v}^\top\mathbf{u}=-1$ then the matrix is singular.) The rest of the eigenvalues are ones, since any $\mathbf{b}$ such that $\mathbf{v}^\top\mathbf{b} = 0$ gives $\left(I + \mathbf{u}\mathbf{v}^\top\right)\mathbf{b}=\mathbf{b}$. This completes the entire spectrum ( so long as $\mathbf{v}^\top\mathbf{u} \ne -1$), showing eignevalues of ones and the value of $1 + \mathbf{v}^\top\mathbf{u}$.

From here notice that any matrix with such a spectrum must be of the form $I+\mathbf{u}g\mathbf{v}^\top$ (after the factorization of $A$ mentioned earlier) where $g$ is any scalar. This is the general form of matrix that has such a spectrum, with all except one of the eigenvalues as ones, the other eignevalue with the right and left eigenvectors of $\mathbf{u}$ and $\mathbf{v}^\top$ (having eigenvalue parametric in the variable $g$).

Once the necessity of that form is realized, the rest is algebra, finding the value for $g$ that solves the equations. For example, the inverse:

\begin{align} \left(I+ \mathbf{u}\mathbf{v}^\top\right) \left(I+ \mathbf{u}\mathbf{v}^\top\right)^{-1} &= I \\ \left(I+ \mathbf{u}\mathbf{v}^\top\right) \left(I+ \mathbf{u}g\mathbf{v}^\top\right) &=I \\ I+ \mathbf{u}g\mathbf{v}^\top+ \mathbf{u}\mathbf{v}^\top + \mathbf{u}\mathbf{v}^\top\mathbf{u}g\mathbf{v}^\top&=I \\ I+ \mathbf{u}\left(g+ 1 + \mathbf{v}^\top\mathbf{u}g \right)\mathbf{v}^\top&=I \\ \Rightarrow g+ 1 + \mathbf{v}^\top\mathbf{u}g &= 0 \\ g(1+\mathbf{v}^\top\mathbf{u}) &= -1 \\ g = \frac{-1}{1+\mathbf{v}^\top\mathbf{u}} \\ \end{align}

So that we have $$\left(I+ \mathbf{u}\mathbf{v}^\top\right)^{-1} = \left(I+ \mathbf{u}\frac{-1}{1+\mathbf{v}^\top\mathbf{u}}\mathbf{v}^\top\right)$$

Answer 3

Note that it is sufficient to prove the Sherman-Morrison Formula for $A = I$. Indeed suppose that we proved it for $A=I$ then \begin{align*} (A+\mathbf{u}\mathbf{v}^T)^{-1} &= (A(I+(A^{-1}\mathbf{u})\mathbf{v}^T))^{-1} = \left(I - \frac{(A^{-1}\mathbf{u})\mathbf{v}^T}{1+\mathbf{v}^T(A^{-1}\mathbf{u})}\right)A^{-1} \\ &= A^{-1} - \frac{A^{-1}\mathbf{u}\mathbf{v}^TA^{-1}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}. \end{align*}

Here is a derivation of the Sherman-Morrison Formula for the case $A=I$ when $\|u\| < 1$ and $\|v\| < 1$. \begin{align*} (I+\mathbf{u}\mathbf{v}^T)^{-1} &= \sum_{k=0}^{\infty} (-1)^k (\mathbf{u}\mathbf{v}^T)^k = I + \sum_{k=1}^{\infty} (-1)^k (\mathbf{u}\mathbf{v}^T)^k\\ &= I + \mathbf{u}\left(\sum_{k=1}^{\infty} (-1)^{k} (\mathbf{v}^T\mathbf{u})^{k-1} \right)\mathbf{v}^T = I - \mathbf{u} \times \frac{1}{1 + \mathbf{v}^T\mathbf{u}} \times \mathbf{v}^T\\ &=I - \frac{\mathbf{u} \mathbf{v}^T}{1 + \mathbf{v}^T\mathbf{u}} \end{align*}

Answer 4

The idea behind Sherman Morrison is to see how a low-rank perturbation affects the inverse. i.e. if we write $$\left(A + uv^T \right)^{-1} - A^{-1} = B$$ we want to know if something can be said about $B$. $$\left(A + uv^T \right) \left( A^{-1} + B\right) = I$$ Hence, $$I + uv^T A^{-1} + AB + uv^T B = I$$ Hence, this shows that $$AB = -uv^T\left(A^{-1} + B \right)$$ is a rank $1$ matrix. Since $A$ is a full-rank matrix, we see that $B$ should be rank $1$. This is the main take-home message of Sherman-Morrison i.e. a rank $r$ update is preserved under inversion. Once this is realized, the exact formula for $B$ can then be obtained from algebraic manipulations.

Answer 5

A general formula (Sherman-Morrison-Woodbury) can be derived from computing the inverse of a block matrix $M=\begin{pmatrix} A &B\\ C&D \end{pmatrix} $, with $A\in\mathrm{GL}_n(\mathbb{F}),~D\in\mathrm{M}_m(\mathbb{F}),~B\in\mathrm{M}_{n\times m}(\mathbb{F})$ and $C\in\mathrm{M}_{m\times n}(\mathbb{F})$. One have $$M\in\mathrm{GL}_{n+m}(\mathbb{F})\iff \mathrm{det}(D-CA^{-1}B)\neq0\quad(*)$$ since $$ M=\begin{pmatrix} I_n &0\\ CA^{-1}&I_m \end{pmatrix}\begin{pmatrix} A &0\\ 0&D-CA^{-1}B \end{pmatrix}\begin{pmatrix} I_n &A^{-1}B\\ 0&I_m \end{pmatrix}$$ Then, from two representations of the block matrix $M$, one gets \begin{align*} M^{-1}&=\begin{pmatrix} I_n &-A^{-1}B\\ 0&I_m \end{pmatrix}\begin{pmatrix} A^{-1} &0\\ 0&(D-CA^{-1}B)^{-1} \end{pmatrix}\begin{pmatrix} I_n &0\\ -CA^{-1}&I_m \end{pmatrix}&\\ &=\begin{pmatrix} I_n &0\\ -D^{-1}C&I_m \end{pmatrix}\begin{pmatrix} (A-BD^{-1}C)^{-1} &0\\ 0&D^{-1} \end{pmatrix}\begin{pmatrix} I_n &-BD^{-1}\\ 0&I_m \end{pmatrix}& \end{align*} A straightforward calculation shows that $$(A-BD^{-1}C)^{-1}=A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1}\quad (**)$$ Now, for Shermann-Morrison formula's, a substition : $D=1, B=-u\in\mathrm{M}_{n\times1}(\mathbb{F})$ and $C=v^{T}\in\mathrm{M}_{1\times n}(\mathbb{F})$, induces:

From $(*)$, \begin{align*}A+uv^{T}\in\mathrm{GL}_n(\mathbb{F})&\iff \mathrm{det}(v^{T}A^{-1}u)\neq0\\&\iff (v^{T}A^{-1}u)\neq0\end{align*} and from $(**)$, $$(A+uv^{T})^{-1}=A^{-1}-\dfrac{A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}$$