# Another proof for Sherman Morrison Formula?

The proof of Sherman Morrison Formula is on wikipedia as well as this question Proof of the Sherman-Morrison Formula.

Isn't there a proof which does not uses multiplication of the inverse and the matrix? I mean, it definitely arises from some equalities that wind up to this.

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

Here's a proof adapted from wikipedia's proof for the (more general) Woodbury matrix identity.

We would like to find a matrix $$X$$ such that $$(A + uv^T)X = I \implies AX + uv^TX = I$$ Now, if we define $$Y = (v^TX)$$, then we can rewrite this as a system of equations: $$A X + uY = I\\ v^TX - Y = 0$$ That is, $$\pmatrix{A & u\\v^T&-1} \pmatrix{X\\Y} = \pmatrix{I\\0}$$ We can solve this system using an augmented matrix and block-matrix operations. In particular, we have $$\left[ \begin{array}{cc|c} A & u & I\\ v^T & -1&0 \end{array} \right] \to \left[ \begin{array}{cc|c} I & A^{-1}u & A^{-1}\\ v^T & -1&0 \end{array} \right] \to \left[ \begin{array}{cc|c} I & A^{-1}u & A^{-1}\\ 0 & -1 - v^TA^{-1}u & -v^TA^{-1} \end{array} \right] \to\\ \left[\begin{array}{cc|c} I & A^{-1}u & A^{-1}\\ 0 & 1 & \frac{1}{1 + v^TA^{-1}u}v^TA^{-1} \end{array} \right] \implies \begin{cases} X + A^{-1}uY = A^{-1}\\ Y = \frac{1}{1 + v^TA^{-1}u}v^TA^{-1} \end{cases}$$ All that remains is substitution. That is, we have $$X = A^{-1} - A^{-1}uY = A^{-1} - A^{-1}u\left( \frac{1}{1 + v^TA^{-1}u}v^TA^{-1}\right) = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1 + v^TA^{-1}u}$$

• in the implication $=I$ is missing. Could you help me to get the final result, I mean substitute what to what? Can you complete the proof. Because now by substitution we have $$X + \frac{A^{-1}uv^T}{1 + v^TA^{-1}u}X = I$$? – Saeed Jan 10 at 22:14
• @Saeed see my latest edit; I had a few mistakes there – Omnomnomnom Jan 10 at 22:20

Write $$A+uv^T=A(I+A^{-1}uv^T)$$; we are to find an inverse of $$I+A^{-1}uv^T$$. It's a bit simpler if we set $$w=-u$$, so instead we look for an inverse of $$I-A^{-1}wv^T$$; the idea that comes to mind is to consider, formally, $$(I-A^{-1}wv^T)^{-1}=I+A^{-1}wv^T+(A^{-1}wv^T)^2+(A^{-1}wv^T)^3+\dotsb \tag{*}$$ taking from $$\frac{1}{1-x}=1+x+x^2+\dotsb$$

Now $$(A^{-1}wv^T)^2=A^{-1}wv^TA^{-1}wv^T=(v^TA^{-1}w)A^{-1}wv^T$$ and $$(A^{-1}wv^T)^3= A^{-1}wv^TA^{-1}wv^TA^{-1}wv^TA^{-1}wv^T= (v^TA^{-1}w)^2A^{-1}wv^T$$ and, by induction, $$(A^{-1}wv^T)^n=(v^TA^{-1}w)^{n-1}A^{-1}wv^T$$ so the formal sum (*) becomes $$I+A^{-1}wv^T+(v^TA^{-1}w)A^{-1}wv^T+(v^TA^{-1}w)^2A^{-1}wv^T+(v^TA^{-1}w)^3A^{-1}wv^T+\dotsb$$ and therefore $$I+\biggl(\,\sum_{n\ge0}(v^TA^{-1}w)^n\biggr)A^{-1}wv^T$$ The term in parentheses is the inverse of $$1-v^TA^{-1}w$$. Returning to $$u$$, we find that the inverse should be $$I-\frac{1}{1+v^TA^{-1}u}A^{-1}uv^T$$ Multiplying on the right by $$A^{-1}$$ we see that the inverse of $$A+uv^T$$ should be $$A^{-1}-\frac{1}{1+v^TA^{-1}u}A^{-1}uv^TA^{-1}$$ Now we can do the multiplication and verify that the intuition is correct.

• Where did you get $(*)$. I mean it is the expansion of what? – Saeed Jan 10 at 22:09
• @Saeed $\frac{1}{1-x}=1+x+x^2+\dots+x^n+\dotsb$ (for $|x|<1$, but with no restriction in formal power series). The argument just formal, but it can be made rigorous. – egreg Jan 10 at 22:13
• Could you please add $I-A^{-1}wv^T=$ to $*$ for clarity? – Saeed Jan 10 at 22:17
• @Saeed Added... – egreg Jan 10 at 22:31

Let $$w=-A^{-1}u$$. Then the problem boils down to proving the equivalent identity that $$(I-wv^T)^{-1} = I+\frac{wv^T}{1-v^Tw}.\tag{1}$$ Let us abuse the symbol $$v$$ and denote by $$v(\cdot)$$ the linear functional $$x\mapsto v^Tx$$. Then $$I-wv^T$$ is a matrix representation of the linear function $$y = f(x) = x - v(x)w.$$ The inverse of this mapping is clearly $$x = f^{-1}(y) = y+v(x)w\tag{2}$$ but we wish to express $$v(x)$$ in terms of $$y$$. Now, since $$v$$ is a linear functional, $$v(y)=v\left(x-v(x)w\right)=v(x)-v(x)v(w).$$ Therefore $$v(x)=\frac{v(y)}{1-v(w)}$$ and $$(2)$$ gives $$f^{-1}(y) = y+\frac{v(y)w}{1-v(w)}$$ and $$(1)$$ follows immediately.

One may argue that the above proof is not what you want because it "uses multiplication of the inverse and the matrix" implicitly, but I think it is worthwhile to prove the identity from an alternative perspective.