Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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 '13 at 1:53
    
If the paper answers or addresses your problem in some way, it's OK to add an answer! :) After all, comments might get deleted at any time. –  Juho Feb 20 '13 at 15:21
1  
Ok, I will summarize the answer later and include it as an answer. –  AJed Feb 20 '13 at 16:22
add comment

2 Answers

up vote 8 down vote accepted

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}}.$$

share|improve this answer
add comment

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.

share|improve this answer
    
Nice answer, but how different is this from the previous one of Yuval ? –  AJed Feb 19 '13 at 2:00
1  
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. –  adam W Feb 19 '13 at 2:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.