Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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} $$
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.
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.
