The usual number of scalar operations (i.e., the total number of additions and multiplications) required to
perform Matrix Multiplication is

(1) |

(2) |

(3) | |||

(4) |

so (2) becomes

(5) |

Two matrices can therefore be multiplied

(6) |

(7) |

(8) |

(9) | |||

(10) | |||

(11) | |||

(12) | |||

(13) | |||

(14) | |||

(15) |

Then the matrix product is given using the remaining eight additions as

(16) | |||

(17) | |||

(18) | |||

(19) |

(Strassen 1969, Press

Matrix inversion of a matrix
to yield
can also be done in fewer operations
than expected using the formulas

(20) | |||

(21) | |||

(22) | |||

(23) | |||

(24) | |||

(25) | |||

(26) | |||

(27) | |||

(28) | |||

(29) | |||

(30) |

(Strassen 1969, Press

**References**

Coppersmith, D. and Winograd, S. ``Matrix Multiplication via Arithmetic Programming.'' *J. Symb. Comput.* **9**, 251-280, 1990.

Pan, V. *How to Multiply Matrices Faster.* New York: Springer-Verlag, 1982.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Is Matrix Inversion an Process?''
§2.11 in *Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed.*
Cambridge, England: Cambridge University Press, pp. 95-98, 1989.

Strassen, V. ``Gaussian Elimination is Not Optimal.'' *Numerische Mathematik* **13**, 354-356, 1969.

© 1996-9

1999-05-26