I have a lower $n\times n$ triangular matrix called $A$ and I want to get $A^{-1}$ solved in $O(n^2)$. How can I do it?
I tried using a method called "forward substitution", but the inversion is solved in $O(n^3)$ for full $n\times n$ matrix.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityI have a lower $n\times n$ triangular matrix called $A$ and I want to get $A^{-1}$ solved in $O(n^2)$. How can I do it?
I tried using a method called "forward substitution", but the inversion is solved in $O(n^3)$ for full $n\times n$ matrix.
No such method is known at present.
If one could invert lower triangular $n \times n$ matrices in time $O(n^2)$ then one could multiply $N \times N$ matrices in time $O(N^2)$. Indeed let $n=3N$ and apply the putative inversion algorithm to the block matrix $$ \left( \begin{array}{ccc} I & 0 & 0 \cr B & I & 0 \cr 0 & A & I \end{array} \right) $$ for any $N\times N$ matrices $A,B$: the inverse is $$ \left( \begin{array}{rrr} I & 0 & 0 \cr -B & I & 0 \cr AB & \!\!\! -A & I \end{array} \right) \, , $$ so you could read $AB$ off the bottom left block.
It is still an open problem whether general matrix multiplication can be done in time $O(N^2)$, or even $O(N^{2+o(1)})$. In particular it follows that no method is known to do what you are asking.
In fact it is known that conversely an algorithm that takes $O(N^2)$ or $O(N^{2+o(1)})$ time to multiply $N \times N$ matrices would let us also invert $n \times n$ matrices in time $O(n^2)$ or $O(n^{2+o(1)})$ respectively (with a different $O$-constant, and not limited to triangular matrices). So your question is in fact equivalent to the open question about fast matrix multiplication. See for instance page 3 of these lecture notes by Garth Isaak, which also shows the block-diagonal trick (in the upper- instead of lower-triangular setting).
POSTSCRIPT Strictly speaking, the reduction from $O(N^c)$ matrix multiplication to $O(n^c)$ inversion of triangular matrices means only that either we don't know how to attain $c=2$ or $c=2+o(1)$ in the latter problem, or such an algorithm is known but somehow nobody has noticed that this solves the former problem. But the second possibility seem most unlikely, because fast matrix multiplication is such a celebrated problem, and its reduction to triangular-matrix inversion is quite well known.