Sherman–Morrison Formula

Definition

Suppose $\mathbf{A}\in {\mathbb{R}}^{n\times n}$ is an invertible matrix an d $\mathbf{v},\mathbf{u}\in {\mathbb{R}}^n$. Then, $\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺}$ is invertible $\iff 1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}\ne 0$. In this case, $(\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺}{)}^{-1}={\mathbf{A}}^{-1}-\frac{{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}}{1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}}$

Proof

Multiplying $(\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺})$ to the RHS gives $\left({\mathbf{A}}^{-1}-\frac{{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}}{1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}}\right)(\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺})=\mathbf{I}+{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}-\frac{{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}(\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺})}{1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}}\text{(1)}$

Since ${\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}$ is a scalar, The numerator of the last term can be expressed as ${\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}(\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺})={\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}+({\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}){\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}=(1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}){\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}$

So, $\text{(1)}=\mathbf{I}+{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}-\frac{(1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}){\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}}{1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}}=\text{(1)}=\mathbf{I}+{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}-{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}=\mathbf{I}$ $\therefore (\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺}{)}^{-1}={\mathbf{A}}^{-1}-\frac{{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}}{1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}}$

Examples

Updating Fitted Least Square Estimator

Sherman–Morrison formula can be used for updating fitted Least Square estimator

Let $\hat{\mathbf{x}}=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}{\mathbf{A}}^{⊺}\mathbf{b}$ be the least square estimator of $\mathbf{Ax}=\mathbf{b}$ and the matrices with a new data be ${\mathbf{A}}_a=\left[\begin{array}{c}\mathbf{A}\\ {\mathbf{a}}^{⊺}\end{array}\right]$ and ${\mathbf{b}}_a=\left[\begin{array}{c}\mathbf{b}\\ b\end{array}\right]$ Then, ${\hat{\mathbf{x}}}_{\text{new}}=({\mathbf{A}}_a^{⊺}{\mathbf{A}}_a{)}^{-1}{\mathbf{A}}_a^{⊺}{\mathbf{b}}_a={\left(\left[\begin{array}{cc}{\mathbf{A}}^{⊺}& \mathbf{a}\end{array}\right]\left[\begin{array}{c}\mathbf{A}\\ {\mathbf{a}}^{⊺}\end{array}\right]\right)}^{-1}\left[\begin{array}{cc}{\mathbf{A}}^{⊺}& \mathbf{a}\end{array}\right]\left[\begin{array}{c}\mathbf{b}\\ b\end{array}\right]=({\mathbf{A}}^{⊺}\mathbf{A}+\mathbf{a}{\mathbf{a}}^{⊺}{)}^{-1}({\mathbf{A}}^{⊺}\mathbf{b}+b\mathbf{a})$

Let $\mathbf{P}:=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}$ for convenience Then, ${\mathbf{P}}_a:=({\mathbf{A}}^{⊺}\mathbf{A}+\mathbf{a}{\mathbf{a}}^{⊺}{)}^{-1}=\mathbf{P}-\frac{\mathbf{Pa}{\mathbf{a}}^{⊺}\mathbf{P}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}-\frac{({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}\mathbf{a}{\mathbf{a}}^{⊺}({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}}{1+{\mathbf{a}}^{⊺}({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}\mathbf{a}}$ by Sherman-Morrison formula

So, ${\hat{\mathbf{x}}}_{\text{new}}=({\mathbf{A}}^{⊺}\mathbf{A}+\mathbf{a}{\mathbf{a}}^{⊺}{)}^{-1}({\mathbf{A}}^{⊺}\mathbf{b}+b\mathbf{a})=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}{\mathbf{A}}^{⊺}\mathbf{b}-\frac{\mathbf{Pa}{\mathbf{a}}^{⊺}\mathbf{P}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}{\mathbf{A}}^{⊺}\mathbf{b}+b{\mathbf{P}}_a\mathbf{a}=\hat{\mathbf{x}}-\frac{\mathbf{Pa}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}{\mathbf{a}}^{⊺}\hat{\mathbf{x}}+b{\mathbf{P}}_a\mathbf{a}$ where ${\mathbf{P}}_a\mathbf{a}=\mathbf{Pa}-\frac{\mathbf{Pa}{\mathbf{a}}^{⊺}\mathbf{Pa}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}=\frac{\mathbf{Pa}+\mathbf{Pa}{\mathbf{a}}^{⊺}\mathbf{Pa}-\mathbf{Pa}{\mathbf{a}}^{⊺}\mathbf{Pa}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}=\frac{\mathbf{Pa}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}$ by expansion $\therefore {\hat{\mathbf{x}}}_{\text{new}}=\hat{\mathbf{x}}-{\mathbf{P}}_a\mathbf{a}{\mathbf{a}}^{⊺}\hat{\mathbf{x}}+b{\mathbf{P}}_a\mathbf{a}=\hat{\mathbf{x}}+{\mathbf{P}}_a\mathbf{a}(b-{\mathbf{a}}^{⊺}\hat{\mathbf{x}})$

So, ${\hat{\mathbf{x}}}_{\text{new}}$ can be obtained without additional inverse matrix calculation.

Facts

Sherman–Morrison formula is a special case of the Woodbury Formula