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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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)$.
answered Sep 17, 2010 at 10:52
-
$\begingroup$ I never would have guessed that inversion and multiplication have the same complexity. Is it a Fourier-ish trick, or something else entirely? $\endgroup$ Commented Sep 17, 2010 at 12:16
-
1$\begingroup$ 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. $\endgroup$ Commented Sep 17, 2010 at 12:42
-
3$\begingroup$ @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. $\endgroup$ Commented Sep 17, 2010 at 13:37
-
$\begingroup$ 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. $\endgroup$ Commented Jul 11, 2012 at 14:14
-
$\begingroup$ @David. You're right. I confused between solving $Ux=b$ and inverting $U$. $\endgroup$ Commented Jul 11, 2012 at 14:40