# Why do researchers only count the number of multiplications when analyse the time complexity of Matrix Multiplication?

Multiplications are everything. The exponent on the eventual running time is fully dependent only on the number of multiplications. The additions sort of disappear.

I was wondering how I should understand this. Why the number of additions doesn't matter?

• now I realised that the distance of my example is NOT metric. Jul 30, 2022 at 5:35

It looks like the article was written by someone who does not understand matrix multiplication.

the number of additions is equal to the number of entries in the matrix, so four for the two-by-two matrices and 16 for the four-by-four matrices.

With the classic matrix multiplication algorithm (which is the one explained in the example) between two $$4\times 4$$ matrices, each coefficient of the product requires $$3$$ additions, so a total of $$3\times 16 = 48$$ additions, not $$16$$.

Usually, when it is said that only multiplications matter and not additions, it means of matrices, not coefficients.

For example, a "naive" divide-and-conquer strategy compute $$A\times B$$ where $$A,B$$ are matrices of size $$n\times n$$ by doing $$8$$ products of matrices of size $$\frac{n}{2}\times\frac{n}{2}$$ (and some additions of matrices, but those are done in complexity $$O(n^2)$$, which is negligible in front of the complexity of matrix multiplication). That way, the complexity verifies $$C(n) = 8C\left(\frac{n}{2}\right) + O(n^2)$$ and it is easily proven that $$C(n) = O(n^3)$$, so this strategy is not an improvement.

The Strassen algorithm use a divide-and-conquer strategy to improve complexity: it does $$7$$ products of matrices of size $$\frac{n}{2}\times\frac{n}{2}$$ and some additions, so the complexity verifies $$C(n) = 7C\left(\frac{n}{2}\right) + O(n^2)$$ and we get $$C(n)\simeq O(n^{2.8})$$.

In the two examples above, the number of matrices multiplications matter much more than the number of matrices additions. But in both, the number of multiplications/additions on coefficients is not compared.

It is confirmed in the article:

Volker Strassen reportedly set out to prove that there was no way to multiply two-by-two matrices using fewer than eight multiplications. Apparently he couldn’t find the proof, and after a while he realized why: There’s actually a way to do it with seven!

• I understood what you said about multiplication/additions of matrices. But what do you mean by multiplications/additions on coefficients? Apr 22, 2021 at 2:24
• $5 \times 7$ is a multiplication of coefficients. $\begin{pmatrix}5 & 2 \\3 & 7\end{pmatrix}\times \begin{pmatrix}1 & 8 \\2 & 4\end{pmatrix}$ is a multiplication of matrices. Apr 22, 2021 at 2:32
• Sorry it's may be dumb question: what do you mean by "But in both, the number of multiplications/additions on coefficients is not compared"? I didn't see any multiplications/additions on coefficients in both algorithms. Apr 22, 2021 at 2:48
• In both algorithms, additions on coefficients are done when adding matrices (so $n^2$ additions for the sum of two $n\times n$ matrices). Multiplications on coefficients are done in the base case, that is the multiplication of two matrices of size $1 \times 1$ (which is the same as the multiplication of two coefficients). The complexity $C(n)$ counts the total number of arithmetic operations on coefficients, may they be multiplications or additions. Apr 22, 2021 at 3:05