[MauranKilom]

> with the holy grail obviously being 1 itself.

It's not at all obvious to me why the number of multiplications must be at least n². Can you prove that? (To be clear, n² multiplications is most certainly the lower bound, but I can't come up with a good argument as to why.)

This is why the trivial "you must read n² entries from each input matrix and write n² entries in the end" is helpful: It's an extremely obvious lower bound on the asymptotic complexity. Sure, it's not what we're trying to reduce (and getting < n² multiplications would be a ridiculous result), but anyone can see that it's true.

[kevinventullo]

If matrix A has a single nonzero column (ai) in the first column and B has a single nonzero row (bj) in the first row, then A * B computes all pairwise products ai * bj.

To be honest I’m not sure whether that really proves it. Does computing a single multiplication require a multiplication?

[fastball]

By definition, a matrix multiplication takes rows and multiplies them by columns. For a pair of square matrices, where there are n rows in A and n columns in B, you (by definition) need to multiply them by each other at least once, otherwise it's not matrix multiplication, it's matrix... something else.

[MauranKilom]

> By definition, a matrix multiplication takes rows and multiplies them by columns.

> you (by definition) need to multiply them by each other at least once

Why does multiplying a row with a column require at least one multiplication? "By definition" it takes n multiplications (!), but in the context of matrix multiplication we can do it with less - possibly with O(1) multiplications. And it seems neither you nor me can come up with a good argument why it can't take less, despite discussing it for a while.

Which is why "you need to write n² entries" is used as an argument for the O(n²) bound, even if it has nothing to do with the number of multiplications.