Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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 Springer-Verlag, 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)$.

share|improve this answer
    
I never would have guessed that inversion and multiplication have the same complexity. Is it a Fourier-ish trick, or something else entirely? –  Matt Noonan Sep 17 '10 at 12:16
1  
Matt: Inversion can be done by multiplying with so-called "Gauss transforms", which is nothing more than the matrix formalism of the steps done in row reduction/Gaussian elimination. Thus, for any "fast" way of multiplying matrices, there would be a corresponding "fast" way of inverting them. –  J. M. Sep 17 '10 at 12:42
3  
@Matt. Conversely, inversion of $3n\times 3n$ matrices can be used to multiply $n\times n$ matrices with the same complexity, up to a universal constant. If $A$ and $B$ are given, just invert the block triangular matrix whose diagonal is ($I_n$ $I_n$ $I_n$) and is boardered by the diagonal ($A$ $B$); the other blocks are $0_n$'s. –  Denis Serre Sep 17 '10 at 13:37
    
Denis, I'm confused. To me, the naive method of inverting an upper triangular matrix has complexity $n^3$. Moreover, your answer seem to show that the answer is YES: You have just shown that $U(3n)$ bounds $n \times n$ matrix multiplication. –  David Speyer Jul 11 '12 at 14:14
    
@David. You're right. I confused between solving $Ux=b$ and inverting $U$. –  Denis Serre Jul 11 '12 at 14:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.