Complexity of linear solvers vs matrix inversion Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given a solver of $N$ linear equations and $N$ unknown variables with computational cost $F(N)$, there is a trivial implementation of matrix inversion using the linear solver with overall computational cost equal to $N F(N)$. 
However, the resulting algorithm is not optimal for matrix inversion. Indeed, the time complexity of linear solvers is not smaller than $N^2$, whereas the time complexity of matrix inversion is not bigger than $N^{2.375}$, as implied by the Coppersmith–Winograd algorithm. 
Thus, my question is as follows. Given any solver of linear equations, is there some algorithm for inverting matrices that uses the linear solver and with the same time cost up to some constant? In other words, does a linear-solver with time cost $N^\alpha$ induce a matrix-inversion algorithm with cost $N^\alpha$? This question comes from the observation that the most efficient known linear solvers come from matrix-inversion algorithms.
 A: It depends what you mean by "solver of linear equations".
If by "solver of linear equations" you mean it can also compute a basis for the kernel of a matrix, then they are indeed equivalent. The equivalence can be shown in two steps:

*

*Computing kernel is equivalent to matrix multiplication. Theorem 16.18 in Bürgisser-Clausen-Shokrollahi.


*Matrix multiplication is equivalent to matrix inversion, see, e.g., Prop 16.6 in Bürgisser-Clausen-Shokrollahi (ibid.).
On the other hand, if you mean "Given $A,b$, it outputs an $x$ such that $Ax=b$, if one exists, and otherwise says NO", then the equivalence between this and matrix inversion (equivalently, from a complexity perspective, matrix multiplication) I believe is an open question, e.g. see the last slide here.
A: A linear solver with optimal complexity $N^2$ will have to be applied $N$ times to find the entire inverse of the $N\times N$ real matrix $A$, solving $Ax=b$ for $N$ basis vectors $b$. This is a widely used technique, see for example Matrix Inversion Using Cholesky Decomposition, because it has modest storage requirements, in particular if $A$ is sparse. The Coppersmith–Winograd algorithm offers a smaller computational cost of order $N^{2.3}$, but this improvement over the $N^3$ cost by matrix inversion is only reached for values of $N$ that are prohibitively large with respect to storage requirements. An alternative to linear solvers with a $N^{2.8}$ computational cost, the Strassen algorithm, is an improvement for $N>1000$, which is also much larger than in typical applications.
So I would think the bottom line is, yes, linear solvers are computationally more expensive for matrix inversion than the best direct methods, but this is only felt for very large values of $N$, while for moderate $N\lesssim 1000$ the linear solvers are faster and have a much reduced storage requirement than direct matrix inversion.
