3
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $$? $\endgroup$ – Saeed Jan 10 at 22:14
  • $\begingroup$ @Saeed see my latest edit; I had a few mistakes there $\endgroup$ – Omnomnomnom Jan 10 at 22:20
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Where did you get $(*)$. I mean it is the expansion of what? $\endgroup$ – Saeed Jan 10 at 22:09
  • $\begingroup$ @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. $\endgroup$ – egreg Jan 10 at 22:13
  • $\begingroup$ Could you please add $I-A^{-1}wv^T=$ to $*$ for clarity? $\endgroup$ – Saeed Jan 10 at 22:17
  • $\begingroup$ @Saeed Added... $\endgroup$ – egreg Jan 10 at 22:31
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.