# Can QR decomposition be used for matrix inversion?

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?

-
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

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.

-
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
@Peter: Huh? QR is not an eigenvalue-revealing decomposition (maybe you were thinking about the Schur decomposition?) –  Ｊ. Ｍ. 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.

-
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