Formula for $(A + vv^\top)^{-1}$ in terms of $A^{-1}$ and $v$.

Question

Let $A \in {\rm GL}(n,\Bbb R)$ and $v \in \Bbb R^n$. Is there a formula for $(A + vv^\top)^{-1}$ in terms of $A^{-1}$ and $v$, assuming that $A+vv^\top$ is actually invertible? I'd appreciate any references. Thanks.

Answer 1

You are searching for the Sherman-Morrison formula. Bindel has a nice presentation here:

http://www.cs.cornell.edu/~bindel/class/cs6210-f09/lec12.pdf

Answer 2

Carl Christian's answer is very nice, I will just give an alternative answer which may be less useful in this case but uses a general workhorse idea.

If $A$ and $A+vv^\top$ are assumed to be invertible, that means that $A^{-1}(A+vv^\top)=1+A^{-1}vv^\top$ is also invertible, which is equivalent to $A^{-1}vv^\top$ having no eigenvalue equal to $-1$ (see comments below). Otherwise, since the corresponding eigenvector $w$ (which must be a scalar multiple of $A^{-1}v$) satisfies $\langle v,w\rangle A^{-1}v=-w$, one has that $\langle v,w\rangle\neq 0$ and therefore $\langle v,A^{-1}v\rangle=-1$. Not surprisingly, the condition for the validity of the rhs of the Sherman-Morrison formula is precisely that $\langle v,A^{-1}v\rangle\neq -1$. In particular, if $A$ is positive definite, both conditions above are satisfied.

Assume instead that $A^{-1}$ is invertible and that the operator norm of $A^{-1}vv^\top$ is less than one (the latter is a stronger hypothesis than the one discussed in the previous paragraph). In this case, you may use the Neumann series formula for the inverse of perturbations of identity, which converges in operator norm (by the way, this works with $A$ any bounded linear operator on a Hilbert space containing $v$ such that $A^{-1}$ is bounded and $\|A^{-1}vv^\top\|<1$): $$(A+vv^\top)^{-1} = (1+A^{-1}vv^\top)^{-1}A^{-1} = \left(\sum^\infty_{k=0}(-1)^k(A^{-1}vv^\top)^k\right)A^{-1}\ .$$