# Number of additions in naive matrix multiplication

In the naive matrix multiplication algorithm where you have 3 loops, the total number of multiplications is $$n^2(n)=n^3$$ given that we have two matrices each with size $$n\times n$$. But a proof claims that the number of additions is $$(n-1)$$, so the total number of additions is $$n^2(n-1)$$. I don't understand how the number of additions is $$(n-1)$$ as I think it should be $$n$$ because whenever we multiply we add that element, so we should have the same number of multiplications $$n$$?

When you add $$n$$ terms there are only $$n-1$$ additions. For example, $$1+2+3$$ has only two additions. You are making a fencepost error.

• I wish I had found the name for this kind of error earlier! It crops up everywhere.
– Joe
Jan 18, 2021 at 15:31
• @Joe.Thank you very much, but why for boolean product, we would have $n$ or bit operations and not $n+1$ as in addition in traditional matrix multiplication in my question?
– Avv
Jan 18, 2021 at 17:32
• @Avra: I don't understand this question at all. What operation are you asking about? Jan 18, 2021 at 17:38
• @RossMillikan. I mean the Boolean product of two matrices has two operations, meet $\cap$ and join $\cup$. The number of join operations, which are equivalent to addition in the above algorithm, is not $(n-1)$, but it's $n$
– Avv
Jan 19, 2021 at 14:31
• I don't know what those operations are on matrices. I know what they are on sets, where there are $n-1$ operations on $n$ sets. Jan 19, 2021 at 15:21