Matrix determinant lemma derivation

Question

While reading this wikipedia article on the determinant lemma, I stumbled upon this expression (in a proof section): \begin{equation} \begin{pmatrix} \mathbf{I} & 0 \\ \mathbf{v}^\mathrm{T} & 1 \end{pmatrix} \begin{pmatrix} \mathbf{I}+\mathbf{uv}^\mathrm{T} & \mathbf{u} \\ 0 & 1 \end{pmatrix} \begin{pmatrix} \mathbf{I} & 0 \\ -\mathbf{v}^\mathrm{T} & 1 \end{pmatrix} = \begin{pmatrix} \mathbf{I} & \mathbf{u} \\ 0 & 1 + \mathbf{v}^\mathrm{T}\mathbf{u} \end{pmatrix}. \end{equation}

Although I see that this equation "works", I'm interested in HOW this thing was invented. For example, why we have $u$ term in a central block matrix of the left side?

UPD A little clarification of the question above.

Let \begin{equation}L = \begin{pmatrix} \mathbf{I} & 0 \\ \mathbf{v}^\mathrm{T} & 1 \end{pmatrix} \end{equation}

I see that \begin{equation} L^{-1}= \begin{pmatrix} \mathbf{I} & 0 \\ -\mathbf{v}^\mathrm{T} & 1 \end{pmatrix} \end{equation}

and hence the first equation looks like \begin{equation} L\begin{pmatrix}\mathbf{I + uv^T} & \mathbf{u} \\ 0 & 1\end{pmatrix}L^{-1} = \begin{pmatrix} \mathbf{I} & \mathbf{u} \\ 0 & 1 + \mathbf{v}^\mathrm{T}\mathbf{u} \end{pmatrix}. \end{equation}

I see that $\det(L) = \det(L^{-1}) = 1 $. Hence determinants of RHS and LHS are equal as well.

What I do not understand is how we jumped from simple $\begin{pmatrix}\mathbf{I + uv^T} & \mathbf{0} \\ 0 & 1\end{pmatrix}$ or $\begin{pmatrix}\mathbf{I} & \mathbf{u} \\ \mathbf{-v}^T & 1\end{pmatrix}$ to $\begin{pmatrix}\mathbf{I + uv^T} & \mathbf{u} \\ 0 & 1\end{pmatrix}$ for a central part of LHS.

Thank you.

Answer 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.

Answer 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.$$