computing – Maths to Share

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.

Concavity of the squared sum of square roots is about an interesting homework problem from the same convex optimization course.

Tag: computing

Solving a system of equations vs inverting a matrix

Related posts