## Solving a system of equations vs inverting a matrix

I used to have trouble understanding why inverting an $n \times n$ matrix required the same order of operations as solving an $n \times n$ system of linear equations. Specifically, if $A$ is an $n\times n$ invertible matrix and $b$ is a length $n$ vector, then computing $A^{-1}$ and solving the equation $Ax = b$ can both be done in $O(n^3)$ floating point operations (flops). This surprised me because naively computing the columns of $A^{-1}$ requires solving the $n$ systems of equations

$Ax = e_1, Ax=e_2,\ldots, Ax = e_n,$

where $e_1,e_2,\ldots, e_n$ are the standard basis vectors. I thought this would mean that calculating $A^{-1}$ would require roughly $n$ times as many flops as solving a single system of equations. It was only in a convex optimization lecture that I realized what was going on.

To solve a single system of equations $Ax = b$, we first compute a factorization of $A$ such as the LU factorization. Computing this factorization takes $O(n^3)$ flops but once we have it, we can use it solve any new system with $O(n^2)$ flops. Now to solve $Ax=e_1,Ax=e_2,\ldots,Ax=e_n$, we can simply factor $A$ once and the perform $n$ solves using the factorization each of which requires an addition $O(n^2)$ flops. The total flop count is then $O(n^3)+nO(n^2)=O(n^3)$. Inverting the matrix requires the same order of flops as a single solve!

Of course, as John D Cook points out: you shouldn’t ever invert a matrix. Even if inverting and solving take the same order of flops, inverting is still more computational expensive and requires more memory.