This is great!

I'll end here. As always, if there are any mistakes or comments, I'm all ears!

Interestingly, fast MM algorithms give rise to fast algorithms for closely related problems. For example, an O(n^ω) algorithm for MM implies (and vice versa!) an O(n^ω) algorithm for the computation of inverses, determinants, kernels, characteristic polynomials, and more!

For example, rank((2,2,2)) ≤ 7 corresponds to Strassen's result. A bound due to Pan, [Pan78], gives rank((70,70,70)) ≤ 143640, yielding a O(n^2.79)-time algorithm!

The key result connecting tensor rank and fast MM algorithms is the following: if the rank of the (q,q,q) MM tensor is at most r, then there exists an O(n^(log_q(r))-time algorithm for MM.

An important concept is the notion of tensor rank. Informally, the rank of a tensor T is the minimum number of rank 1 tensors that sum up to T. A rank 1 tensor is one that is nonzero and "fully factors."

To generalize Strassen's algorithm, we can represent matrix multiplication as a bilinear map, i.e. a tensor (of order 3). I won't get into the specifics here (because they're hard to typeset), but the results are very interesting.

Strassen's breakthrough [Str69] was discovered via an exhaustive case analysis, realizing that one could reduce 8 MM operations to 7. The recurrence is then
T(n) = 7T(n/2) + O(n^2) = O(n^(log 7)) ≤ O(n^2.8).

Strassen's realization was a result of trying to prove that O(n^3) was the optimal bound!

A standard divide-and-conquer approach to MM consists of dividing the original n x n matrix into (n/2) x (n/2) blocks and performing the product blockwise. This gives us a recurrence

T(n) = 8T(n/2) + O(n^2) = 0(n^(log 8)) =0(n^3)

since we do 8 multiplications and O(n^2) work to read and recombine.

I’ve seen "Lemma" for one direction, and "Theorem" stating both directions and proving one, and invoking the lemma for the other.

These experiences wouldn’t have been possible without the unending support of Raf Frongillo, @huckbennett.bsky.social, Sriram Sankaranarayanan, Joan Gabriele, and The Boettcher Foundation. I am very grateful!