Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  1. Is there any simple algorithm for matrix inversion (that can be implemented using C/C++)?

  2. Can QR decomposition be used for matrix inversion? How?

share|improve this question
    
Please clarify what is B"H in the beginning of the question? –  user21436 Feb 14 '12 at 17:39
    
It means with g-d's help (without it there shall be no benefit to this question, nor to any of the answers to it). –  Yan Raf Feb 14 '12 at 18:14
    
The first question might be more suitable for scicomp.SE. –  user2468 Feb 20 '12 at 21:09
add comment

2 Answers

Gauss–Jordan elimination can be used for matrix inversion.

A QR-decomposition can certainly be used for matrix inversion because if $A=QR$ then $A^{-1} = R^{-1} Q^{-1} = R^{-1} Q^{T}$ and $R^{-1}$ is easy to compute because $R$ is triangular.

But consider why you need to invert a matrix. In most cases, you don't: you just need to solve a linear system $Ax=b$. If $A=QR$ then this system is equivalent to $Rx = Q^T b$, which is easy to solve because $R$ is triangular.

share|improve this answer
    
Thanks much for this useful answer. Could you elaborate on "$R^{-1}$ is easy to compute because $R$ is triangular"? How is a triangular matrix easily inverted? –  Yan Raf Feb 14 '12 at 18:18
    
Any matrix-decomposition will most likely give you the inverse (but not all decompositions are possible for all invertible matrices, for example cholesky is only usable for symmetric matrices). Two additional neat ways to get the inverse is by applying Cayley-Hamilton or the neat but rare adjugate matrix –  Peter Sheldrick Feb 14 '12 at 18:22
    
@YanRaf, $R^{-1}$ is easy to invert, since the diagonal contains the eigenvalues from which you get the eigendecomposition. However, maybe lhf was refering to solving $Rx=y$, which is solvable by back-/foward-substitution. –  Peter Sheldrick Feb 14 '12 at 18:32
    
@YanRaf, yes, I meant back-/foward-substitution. –  lhf Feb 14 '12 at 18:43
1  
@Peter: Huh? QR is not an eigenvalue-revealing decomposition (maybe you were thinking about the Schur decomposition?) –  J. M. Feb 15 '12 at 14:05
show 1 more comment

Regarding your first question: every computable algorithm can be implemented in C/C++ because they have same power as a Turing machine.

share|improve this answer
    
I would love to see a C/C++ implementation of algorithms which require more than $2^{2^{2^{2^{2^{100}}}}}$ many instructions. –  Asaf Karagila May 19 '12 at 21:02
    
@AsafKaragila 64KB is enought for everybody. –  Trismegistos May 21 '12 at 9:15
    
It was 640K and it is completely out of context... –  Asaf Karagila May 21 '12 at 9:39
    
No it is not. Use your imagination and you will know what progarm size have to your wish. –  Trismegistos May 21 '12 at 12:42
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.