📂Matrix Algebra

Derivation of the Sherman-Morrison Formula

Theorem

Invertible matrix for $A \in \mathbb{R}^{n \times n}$ and $\mathbf{u} , \mathbf{v} \in \mathbb{R}^{n}$, the following holds true. $$1 + \mathbf{v}^{T} A^{-1} \mathbf{u} \ne 0 \iff \exists : \left( A + \mathbf{u} \mathbf{v}^{T} \right)^{-1}$$

Sherman-Morrison Formula

When $\left( A + \mathbf{u} \mathbf{v}^{T} \right)^{-1}$ exists, the concrete formula is as follows. $$\left( A + \mathbf{u} \mathbf{v}^{T} \right)^{-1} = A^{-1} - {{ A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }}$$

Explanation

The Sherman-Morrison formula itself can be widely used, such as in statistics to prove the Pearson theorem, etc. However, when just considering the proof of existence, one immediate application is to easily check whether an inverse matrix still exists when a small perturbation $\mathbf{u} \mathbf{v}^{T}$ is applied to $A$, or when a specific row or column is added or subtracted.

The Sherman-Morrison formula itself shows that it is possible to find a new inverse matrix without going through the process of recalculating the inverse matrix through $A^{-1}$, using only matrix multiplication, scalar multiplication, addition, and subtraction. Compared to the effort of calculating an inverse matrix from scratch, this method is so efficient that it can hardly be called a calculation.

Proof ¹

Existence

Matrix determinant lemma: For the invertible matrix $A \in \mathbb{R}^{n \times n}$ and $\mathbf{u} , \mathbf{v} \in \mathbb{R}^{n}$, the following holds true. $$\det \left( A + \mathbf{u} \mathbf{v}^{T} \right) = \left( 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} \right) \det A$$

According to the matrix determinant lemma, $$\det \left( A + \mathbf{u} \mathbf{v}^{T} \right) = \left( 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} \right) \det A$$ since $A$ is assumed to be an invertible matrix, $\det A \ne 0$, and the necessary and sufficient condition for $\det \left( A + \mathbf{u} \mathbf{v}^{T} \right) = 0$ to hold is $\left( 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} \right) = 0$.

■

Formula

It’s sufficient to just multiply $\left( A + \mathbf{u} \mathbf{v}^{T} \right)$ and $\left( A^{-1} - {{ A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }} \right)$ and check if it’s the identity matrix $I$. $$\begin{align*} & \left( A + \mathbf{u} \mathbf{v}^{T} \right) \left( A^{-1} - {{ A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }} \right) \\ =& A A^{-1} + \mathbf{u} \mathbf{v}^{T} A^{-1} - {{ A A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} + \mathbf{u} \mathbf{v}^{T} A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }} \\ =& I + \mathbf{u} \mathbf{v}^{T} A^{-1} - {{ \mathbf{u} \mathbf{v}^{T} A^{-1} + \mathbf{u} \mathbf{v}^{T} A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }} \\ =& I + \mathbf{u} \mathbf{v}^{T} A^{-1} - {{ \mathbf{u} \left( 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} \right) \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }} \\ =& I + \mathbf{u} \mathbf{v}^{T} A^{-1} - \mathbf{u} \mathbf{v}^{T} A^{-1} \\ =& I \end{align*}$$ Even if the order of multiplication is reversed, the result is the same, but this is omitted.

■