Let I(n) and U(n) be the number of steps needed to invert an nxn matrix and nxn upper triangle matrix respectively. Can we prove I(n)<=cU(n), where c is some constant?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
The answer is probably No, if you wish a constant independent of $n$. On the one hand, the naive method gives the optimal result $U(n)=n^2$. On the other hand, it is known that the complexity of inversion and that of matrix multiplication are the same (see for instance the second edition, to appear soon, of my book Matrices;Theory and Applications, GTM 216 SpringerVerlag, 2010). If the answer to your question is positive, this implies therefore that matrix multiplication can be done in $O(n^2)$ operations. This is highly unlikely. The state of the art tells us that it can be done in $O(n^{2.376})$ operations. Optimists believe that it could be done in $O(n^{2+\epsilon})$ for every $\epsilon>0$, but not in $O(n^2)$. 

