15
$\begingroup$

Is there a formula to calculate the number of multiplications that take place when multiplying 2 matrices? For example

$$\begin{pmatrix}1&2\\3&4\end{pmatrix} \times \begin{pmatrix}5&6\\7&8\end{pmatrix} = \text{8 multiplications and 4 additions} $$

$\endgroup$
  • 1
    $\begingroup$ There is actually a way to multiply a pair of $2\times2$ matrices doing only 7 multiplications, and finding the minimum number of multiplications for $n\times n is ongoing research. But the number of multiplications required by the straightforward method is not a research question, and research is what this website is about. $\endgroup$ – Gerry Myerson Sep 5 '13 at 6:34
23
$\begingroup$

Doing a $k\times l$ times $l\times m$ matrix multiplication in the straightforward way, every entry of the result is a scalar product of of two $l$-vectors, which requires $l$ multiplications and $l-1$ additions. Multiply that by the number $km$ of entries of the result (or don't multiply if you have sufficiently many processors to do everything in parallel).

$\endgroup$
5
$\begingroup$

I would like to give a simple answer for square, $n$ x $n$ matrices using the standard matrix multiplication algorithm.

Say you have two square matrices $A$ and $B$. Computing element $a_{ij}$ of $AB$ requires taking the dot product of row $i$ in $A$ and column $j$ in B. Computing the dot product requires $n$ multiplications and $n-1$ additions. Since there are $n^2$ elements, the dot product must be computed $n^2$ times.

Thus the total number of operations is $n^2(n+(n-1))=2n^3-n^2 = O(n^3).$

$\endgroup$