patternModerate
Computing inverse matrix when an element changes
Viewed 0 times
inversechangeselementwhenmatrixcomputing
Problem
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.
Solution
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 + 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}$
Context
StackExchange Computer Science Q#9875, answer score: 13
Revisions (0)
No revisions yet.