Prove $(I + uv^T)^{-1} = I - \frac{uv^T}{1 + v^Tu}$ for $u^Tv \neq -1$

Question

I've tried for some time to prove the following, which seems to be very easy to prove, and that's why I'm very ashamed of myself.

Prove that for every $u, v \in \mathbb{R}^n$$$(I + uv^T)^{-1} = I - \frac{uv^T}{1 + v^Tu}$$ for $u^Tv \neq -1$.

My conclusions:

1. $v^Tu = u^T v$, and this is the dot product between $u$ and $v$.

2. $u v^T$ is a $n \times n$ matrix

3. $v u^T = (u v^T)^T$ (I'm not completely sure about this one)

4. $I$ is the identity matrix

5. Of course we want $u^T v \neq -1$ because otherwise we would have a denominator equal $0$

6. In the RHS of the equation, we're dividing a matrix by a scalar

7. In the RHS of the equation, we're subtracting a matrix from the identity matrix.

Many observations and conclusions but no answer yet. I've tried to manipulate both LHS and RHS but without success. I've been doing this quite enough to say that usually, in this cases, it's not just about manipulation of formulas (in the trivial sense), but sometimes we also need to manipulate them "cleverly", which is difficult and even difficult to define.

Answer 1

\begin{align}(I+uv^T)(I-\frac{uv^T}{1+v^Tu})&=I+uv^T-\frac{uv^T}{1+v^Tu}-\frac{uv^Tuv^T}{1+v^Tu}\\ &=I+uv^T-(1+v^Tu)\frac{uv^T}{1+v^Tu}\\ &=I+uv^T-uv^T\\ &=I\end{align}

Remark:

Your point number 3 is correct.

From the first line to second line, I use the fact that $v^Tu$ is a scalar, as it's a dot product as mentioned in your first point.

Answer 2

Hint: To show that something ($S$) is the inverse of $A$, show that $SA=Id$.

Answer 3

Your "inspection" of both sides of your equation is very valuable.

Here is a proof by expansion into series ($\frac{1}{1+x}=\sum_{k=0}^{\infty}(-1)^kx^k$):

The important thing to be conscious in the following computations is that $uv^T$ is a matrix whereas $v^Tu \in \mathbb{R}$ (in particular, you can just move it in front of any expression).

• LHS = $(I + uv^T)^{-1} = \sum_{k=0}^{\infty}(-1)^k (uv^T)^k $

$ \ \ \ \ \ \ \ \ \ \ \ \ = I - uv^T + (uv^T)(uv^T) - (uv^T)(uv^T)(uv^T) + ....$

$ \ \ \ \ \ \ \ \ \ \ \ \ = I - uv^T + u(v^Tu)v^T - u(v^Tu)(v^Tu)v^T + ....$

$ \ \ \ \ \ \ \ \ \ \ \ \ = I - uv^T + (v^Tu)uv^T - (v^Tu)^2 uv^T + ....$

$ \ \ \ \ \ \ \ \ \ \ \ \ = I - (1-(v^Tu)+(v^Tu)^2 -...) uv^T $

• RHS = $I - \frac{uv^T}{1 + v^Tu} $

$ \ \ \ \ \ \ \ \ \ \ \ \ = I - uv^T\sum_{k=0}^{\infty}(-1)^k (v^Tu)^k $

$ \ \ \ \ \ \ \ \ \ \ \ \ = I - uv^T(I - uv^T + (uv^T)(uv^T) - (uv^T)(uv^T)(uv^T) + ....)$

$ \ \ \ \ \ \ \ \ \ \ \ \ = I - uv^T(I - uv^T + u(v^Tu)v^T - u(v^Tu)(v^Tu)v^T + ....)$

$ \ \ \ \ \ \ \ \ \ \ \ \ =I - uv^T + u(v^Tu)v^T - u(v^Tu)(v^Tu)v^T + ... $

$ \ \ \ \ \ \ \ \ \ \ \ \ =I - uv^T + (v^Tu)uv^T - (v^Tu)^2 uv^T + ... $

$ \ \ \ \ \ \ \ \ \ \ \ \ =I - (1-(v^Tu)+(v^Tu)^2 +...) uv^T $

Under condition $|v^Tu|<1$, numerical series $S=\sum_{k=0}^{\infty}(-1)^k (v^Tu)^k$ is convergent. Thus LHS and RHS have the common expression: $I-Suv^T.$

Remark: the interest of this proof is its heuristic character. But the proof given by @SiongthyeGoh is more general: it works in all cases where $v^Tu \neq -1$.