Showing $A+uv^T$ is nonsingular and finding $A^{-1}$

Question

Suppose $A$ is a nonsingular matrix of order $n$, $u$ and $v$ are $n$-vectors, and $v^T A^{−1}u\neq −1$. Show that $A + uv^T$ is nonsingular with inverse

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

Answer 1

Show that it's non-singular

Hint: $M$ is non-singular if $Mx = 0 \Leftrightarrow x=0$. So if $A+uv^T$ is singular there is a $x\neq 0$ such that $Ax+uv^T x=0$, show that there is no such $x$.

Show that the inverse is given by what you quoted

Hint: just test it, if you multiply the formula by $(A+uv^T)$ and massage it a bit you will get the identity matrix (you will need to use the symmetry of the inner product (i.e., $x^T y =y^Tx$) and that's pretty much it)

Also this is a well known formula called the Sherman-Morrison formula, which you may want to look up.

Answer 2

If $\mathrm A \in \mathbb R^{n \times n}$ is invertible, then

$$\begin{array}{rl} (\mathrm A + \mathrm u \mathrm v^{\top})^{-1} &= (\mathrm A (\mathrm I_n + \mathrm A^{-1} \mathrm u \mathrm v^{\top}))^{-1}\\ &= (\mathrm I_n + \mathrm A^{-1} \mathrm u \mathrm v^{\top})^{-1} \mathrm A^{-1}\\ &= (\mathrm I_n - \mathrm A^{-1} \mathrm u \mathrm v^{\top} + (\mathrm A^{-1} \mathrm u \mathrm v^{\top})^2 - (\mathrm A^{-1} \mathrm u \mathrm v^{\top})^3 + \cdots) \, \mathrm A^{-1}\\ &= \mathrm A^{-1} - \mathrm A^{-1} \mathrm u \mathrm v^{\top} \mathrm A^{-1} + \mathrm A^{-1} \mathrm u \mathrm v^{\top} \mathrm A^{-1} \mathrm u \mathrm v^{\top} \mathrm A^{-1} - \cdots\\ &= \mathrm A^{-1} - \mathrm A^{-1} \mathrm u \left( 1 - \mathrm v^{\top} \mathrm A^{-1} \mathrm u + (\mathrm v^{\top} \mathrm A^{-1} \mathrm u)^2 - \cdots \right) \mathrm v^{\top} \mathrm A^{-1}\end{array}$$

where the geometric series

$$1 - \mathrm v^{\top} \mathrm A^{-1} \mathrm u + (\mathrm v^{\top} \mathrm A^{-1} \mathrm u)^2 - \cdots = \dfrac{1}{1 + \mathrm v^{\top} \mathrm A^{-1} \mathrm u}$$

converges if $| \mathrm v^{\top} \mathrm A^{-1} \mathrm u | < 1$. Assuming convergence,

$$\boxed{(\mathrm A + \mathrm u \mathrm v^{\top})^{-1} = \mathrm A^{-1} - \dfrac{\mathrm A^{-1} \mathrm u \mathrm v^{\top} \mathrm A^{-1}}{1 + \mathrm v^{\top} \mathrm A^{-1} \mathrm u}}$$