Computing inverse matrix when an element changes

Question

Given an $n \times n$ matrix $\mathbf{A}$. Let the inverse matrix of $\mathbf{A}$ be $\mathbf{A}^{-1}$ (that is, $\mathbf{A}\mathbf{A}^{-1} = \mathbf{I}$). Assume that one element in $\mathbf{A}$ is changed (let's say $a _{ij}$ to $a' _{ij}$). The objective is to find $\mathbf{A}^{-1}$ after this change. Is there a method to find this objective that is more efficient than re-calculating the inverse matrix from scratch.

Answer 1

The Sherman-Morrison formula could help:

$$ (A + uv^T)^{-1} = A^{-1} - \frac{A^{-1} uv^T A^{-1}}{1 + v^T A^{-1} u}. $$

Let $u = (a'_{ij}-a_{ij}) e_i$ and $v = e_j$, where $e_i$ is the standard basis column vector. You can check that if the updated matrix is $A'$ then $$ A^{\prime -1} = A^{-1} - \frac{(a'_{ij}-a_{ij})A^{-1}_{i\rightarrow} A^{-1T}_{\downarrow j}}{1 + (a'_{ij}-a_{ij})A^{-1}_{ij}}.$$

Answer 2

A single element change, given $A$ with $A^{-1}$, may be tracked with a rank one update. So yes, absolutely, there is a better way than recalculating the inverse from scratch.

Let $\delta = a_{ij}' - a_{ij}$ be the change of the element $a_{ij}$. Using $e_i$ as the unit column vector of one in the $i$ position and zeroes elsewhere, we have $$(A + e_i \delta e_j^\top )A^{-1} = I + e_i \delta e_j^\top A^{-1}$$

$e_i \delta e_j^\top$ is the zero matrix, except the value of $\delta$ in the $ij$ position. Can you see here how an appropriate rank one right multiplication with $A^{-1}$ may give the desired new inverse? (Or equivalently, elementary column operations on $A^{-1}$.)

Or if you like to do row operations instead, you can use $$A^{-1}(A + e_i \delta e_j^\top ) = I + A^{-1}e_i \delta e_j^\top$$

In the first case we have the identity with a row added. This is easy to do column operations upon to have the identity back again. Do these operations on $A^{-1}$ and the result is the new inverse, as desired. The second case is the identity with a column added. In that case, you may do row operations instead. You may choose whichever is more convenient.