# Fastest algorithm for matrix inversion

What is the fastest way to compute the inverse of the matrix, whose entries are from file $\mathbb{R}$ (set of real numbers)?

One way to calculate the inverse is using the gaussian elimination method. In this method append more columns(double the number of columns ) to the input matrix and then we try to make last row zero except the last column entry and second last and so on until we get a identity matrix and then we stop and we have a inverse of input matrix. Consider the cost of one multiplication, division and addition is constant. Then total $O(n^2)$ many operations is needed.

Is there any algorithm which is faster than the above algorithm? Please give the algorithm or reference to the algorithm

• Beyond wikipedias method collection (and links, you can try and account for memory hierarchy and other aspects of machine architecture - neither of which looks core computer science. – greybeard Nov 1 '17 at 13:24
• Also worth pointing out the standard disclaimer: If you're trying to solve a real-world problem, be aware that inverting a matrix (larger than, say, 4x4) is usually not a good idea. – Pseudonym Nov 1 '17 at 23:49

## 1 Answer

Gaussian elimination requires $O(n^3)$ operations, not $O(n^2)$.

In general, matrix inversion has the same exponent as matrix multiplication (any matrix multiplication algorithm faster than $O(n^3)$ gives a matrix inversion algorithm faster than $O(n^3)$), see for example P.Burgisser, M.Clausen, M.A.Shokrollahi "Algebraic complexity theory", Chapter 16 "Problems related to matrix multiplication".

• I am not getting how matrix multiplication related to matrix inversion – Complexity Nov 1 '17 at 14:03
• Matrix inversion is by definition related to matrix multiplication. But from algorithmic point of view, you can calculate matrix inversion with blockwise inversion method, so for every $\epsilon$ for which exists an matrix multiplication algorithm working in $O(n^{2+\epsilon})$ time there is also a matrix inversion algorithm with same complexity. – Szymon Stankiewicz Nov 1 '17 at 20:13