# Computing inverse matrix when an element changes

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.

• Great answers: I found the following paper that tackles this exact problem: Sankowski, Piotr. "Dynamic transitive closure via dynamic matrix inverse." Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on. IEEE, 2004.
– AJed
Feb 19, 2013 at 1:53
– Juho
Feb 20, 2013 at 15:21

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}_{\downarrow i} A^{-1T}_{j\rightarrow}}{1 + (a'_{ij}-a_{ij})A^{-1}_{ij}},$$ where $$A^{-1}_{\downarrow i}$$ denotes the $$i$$-th column vector of $$A^{-1}$$ and $$A^{-1}_{j\rightarrow}$$ denotes the $$j$$-th row vector of $$A^{-1}$$

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.

• Nice answer, but how different is this from the previous one of Yuval ?
– AJed
Feb 19, 2013 at 2:00
• A different perspective is all, if you like pivot operations this form shows the values to be zeroed, and that row or column operations may be done in this case. If an entire row were changed instead, it would still work but then column operations on $A^{-1}$ would be necessary. Feb 19, 2013 at 2:41