2
$\begingroup$

$C = A+D$, $A$ being square matrix and $D$ a full rank diagonal matrix. Is there any easy way to compute $C^{-1}$ from $A^{-1}$ and $D$

Edit 2: (important edit) Iam interested in this question, because my matrix $A$ is huge and so is $C$. So computing inverse of $C$ is not practical, but luckily the matrix $A$ is unitary, so $A^{-1} = A^*$, so I easily have $A^{-1}$, and finding ways to use it to get $C^{-1}$.

$\endgroup$
  • $\begingroup$ $C$ need not be even invertible. Take $A=I$ and $D=-I$. $\endgroup$ – Anurag A Oct 30 '18 at 5:47
  • $\begingroup$ @AnuragA : I am not talking about $A = I$. just a general case. Just asume $C$ is invertible, is there a way to compute it faster from knowledge of $A^{-1}$ $\endgroup$ – Rajesh Dachiraju Oct 30 '18 at 5:52
  • $\begingroup$ In general also there is no guarantee that $C$ is invertible. For example, take $A=\begin{bmatrix}1&2\\0&-2\end{bmatrix}$ and $D=\begin{bmatrix}-1&0\\0&2\end{bmatrix}$. Then $C=\begin{bmatrix}0&2\\0&0\end{bmatrix}$ is NOT invertible. $\endgroup$ – Anurag A Oct 30 '18 at 5:54
1
$\begingroup$

I think that you cannot expect better than a complexity $\sim n^3$.

Indeed i) $(A+D)^{-1}=D^{-1}(I+AD^{-1})^{-1}$. (it's not better using the Woodbury identity).

All the calculations are in $O(n^2)$, except the calculation of $(I+U)^{-1}$ where $U=AD^{-1}$.

or ii) $(A+D)^{-1}=A^*(I+DA^*)^{-1}$. Here all is in $O(n^2)$ except the calculations of $(I+V)^{-1}$, where $V=DA^*$, and of the product of the result by $A^*$.

Then the problem reduces to the calculation of $(I+W)^{-1}$ where $W$ is, roughly speaking, a polar form. Then $W$, a priori, has no particularity. Then the complexity of the previous calculation is $\sim n^3$.

Remark. The hypothesis $||W||<1$ is absolutely useless; to believe the opposite is an urban legend. Indeed $(I+W)^{-1}\approx I-W+W^2-W^3$ has already a complexity $\sim 2n^3$.

$\endgroup$
  • $\begingroup$ Its not evident that you have tried to use the fact that $A$ is unitary. Please see my full question, where I have mentioned $A$ is unitary. Hope it will change the answer. $\endgroup$ – Rajesh Dachiraju Oct 30 '18 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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