Showing $A+uv^T$ is nonsingular and finding $A^{-1}$ 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}$$
 A: 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.
A: 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}}$$ 
A: As noted in another answer, this is known as the Sherman-Morrison formula. One can actually deduce the formula using only knowledge about matrix multiplication, without guessing or knowing the form of the inverse in advance. Suppose first that the inverse exists. Let $(A+uv^T)^{-1} = A^{-1}+B$. Expanding $(A+uv^T)(A^{-1}+B) = I$, we get $I+uv^TA^{-1}+(A+uv^T)B=I$ and hence
$$
B = -(A+uv^T)^{-1}uv^TA^{-1} = -(A^{-1}+B)uv^TA^{-1}.\tag{1}
$$
Let $w=-(A^{-1}+B)u$, so $(1)$ gives $B = wv^TA^{-1}$ and
\begin{align}
B&= -(A^{-1}+wv^TA^{-1})uv^TA^{-1}\\
&= -A^{-1}uv^TA^{-1} - w\color{red}{(v^TA^{-1}u)}v^TA^{-1}\\
&= -A^{-1}uv^TA^{-1} - \color{red}{(v^TA^{-1}u)}wv^TA^{-1}\\
&= -A^{-1}uv^TA^{-1} - (v^TA^{-1}u)B.
\end{align}
Therefore
$$
B = -\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}
$$
and the inversion formula follows from $(A+uv^T)^{-1} = A^{-1}+B$. You can easily verify by direct calculation that $(A+uv^T)(A^{-1}+B)$ is indeed equal to $I$.
