Problem Detail: 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.
Asked By : AJed
Answered By : Yuval Filmus
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}_{irightarrow} A^{-1T}_{downarrow j}}{1 + (a’_{ij}-a_{ij})A^{-1}_{ij}}.$$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9875
