# Insightful proofs for Sherman-Morrison Formula and Matrix Determinant Lemma

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 ?

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}}$$

• Thank you Paul Hanson. I think your way of finding the inverse of $A+uv^T$ is the best method. Dec 17, 2019 at 9:07
• I also think so, because it has the flavor of a Schur-type argument: you solve part of the equation in terms of other parts (here, $x$ in terms of $s$). Also it generalizes to arbitrary rank (Woodbury formula) Jun 25, 2020 at 10:05

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)$$

• This gives very good explanation. But could you explain more why only $I +\mathbf{u}g\mathbf{v}^T$ satisfies such a spectrum ?
– eig
Dec 17, 2012 at 12:58
• Oh, by looking at the spectrum of $I+\mathbf{u}\mathbf{v}^T$, we have the nice proof for Matrix Determinant Lemma as well.
– eig
Dec 17, 2012 at 14:20
• @eig If the dimension is $n \times n$ then there are $n-1$ independent vectors that are orthogonal to $\mathbf{v}$ so that there are that many right eigenvectors with eigenvalue of $1$, since when right multiplying gives only the term from $I$ because the other term is $0$. Thus the entire spectrum of $n$ eigenvectors is determined, $n-1$ of them with value $1$ and the other has value $1+\mathbf{v}^\top\mathbf{u}$ Dec 17, 2012 at 16:42
• @adam you're explaining a matrix with form $I + ugv$ will satisfy such a spectrum. But your statement is "matrix with such a spectrum must be of the form $I + ugv$". How do you get it? Dec 23, 2016 at 16:17
• @ctNGUYEN The spectrum along with the eigenvectors of course. Take the difference of that form and a general matrix of unknown form but with the same spectrum and eigenvectors. Does thier difference equal the zero matrix? Of course because all eigenvalues are zero. Mar 26, 2017 at 4:03

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*}

• Hi Yury, Very wonderful this proof. I never imagined getting the Sherman-Morrison formula using the series of powers of $(I -X)^{-1}$. Dec 16, 2012 at 20:08
• This type of perturbation arguments is very useful to get intuition on other type of equalities: if an identity holds perturbatively, it usually holds non-perturbatively too. Another nice example is showing that the spectrum of AB and BA are the same except for possibly zero, by showing that one resolvent can be deduced from the other: see the beginning of math.byu.edu/~pace/cont-math_web.pdf Jun 25, 2020 at 9:49

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.

• nice demonstration for the rank! Another message is that any rank one change of appropriate scale results in making the matrix singular-- when $1 + k\mathbf{v}^\top A^{-1}\mathbf{u} = 0$ for some scalar $k$ Dec 16, 2012 at 21:44

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}$$