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.



Inverting lower triangular matrix in time $n^2$
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](https://www.lehigh.edu/~gi02/m242/08linstras.pdf) 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.


