Matrix determinant lemma derivation

Solution 1:

This is just Gaussian elimination. We begin with $\pmatrix{I+uv^T&0\\ 0&1}$ and we want to eliminate the summand $uv^T$ in the first sub-block using row or column additions (so that the determinant is preserved): \begin{align*} \pmatrix{I+uv^T&0\\ 0&1}\pmatrix{I&0\\ -v^T&1}&=\pmatrix{I+uv^T&0\\ -v^T&1},\\ \pmatrix{I&u\\ 0&1}\pmatrix{I+uv^T&0\\ -v^T&1}&=\pmatrix{I&u\\ -v^T&1},\\ \pmatrix{I&0\\ v^T&1}\pmatrix{I&u\\ -v^T&1}&=\pmatrix{I&u\\ 0&1+v^Tu}. \end{align*} Put them together, we get $$ \pmatrix{I&0\\ v^T&1}\pmatrix{I&u\\ 0&1}\pmatrix{I+uv^T&0\\ 0&1}\pmatrix{I&0\\ -v^T&1}=\pmatrix{I&u\\ 0&1+v^Tu}. $$ If you want, you may perform a further column addition to make the RHS block-diagonal: $$ \pmatrix{I&0\\ v^T&1}\pmatrix{I&u\\ 0&1}\pmatrix{I+uv^T&0\\ 0&1}\pmatrix{I&0\\ -v^T&1}\pmatrix{I&-u\\ 0&1}=\pmatrix{I&0\\ 0&1+v^Tu}. $$ Sherman–Morrison–Woodbury formula and Schur complement are also derived in the same spirit.

Solution 2:

I have no idea how this was invented and what was the original motivation, but let me outline a different proof for the formula $\det(I + uv^T) = 1 + v^T u$ which I think is much less magical and more natural.

Set

$$ B = uv^T = \begin{pmatrix} u_1 v_1 & \dots & u_1 v_n \\ u_2 v_1 & \dots & u_2 v_n \\ \vdots & \ddots & \vdots \\ u_n v_1 & \dots & u_n v_n \end{pmatrix} \in M_n(\mathbb{F}). $$

Let us start by finding the characteristic polynomial $p_B(x) = \det(B - xI)$ of $B$. Since $B$ has $\operatorname{rank}(B) \leq 1$, we know that it has at least $n - 1$ eigenvectors associated to the eigenvalue $0$. Since the sum of all eigenvalues must be $\operatorname{tr}(B) = v^T u$, we see that

$$ p_B(x) = \det(B - xI) = (-1)^{n} x^{n-1}(x - v^T u). $$

Now plug in $x = (-1)$ and deduce the required formula:

$$ p_B(1) = \det(B - (-1)I) = \det(B + I) = \det(I + uv^T) = (-1)^n (-1)^{n-1} (-1 - v^T u) = 1 + v^T u.$$