## Matrix multiplication

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

## 1 Answer

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)$.

-
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 2010 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 2010 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 2010 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 at 14:14
@David. You're right. I confused between solving $Ux=b$ and inverting $U$. – Denis Serre Jul 11 at 14:40
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9218178987503052, "perplexity_flag": "head"}