The recent publication in Nature of "Discovering faster matrix multiplication algorithms with reinforcement learning" by Fawzi et al. has shown a method for discovering fewer element multiplication steps in multiplying two matrices. The method is, to over simplify considerably, statistical, yet the resulting multiplication/addition schemas are combinatorial - i.e. the method may well be magic/oracular but the result is easily checkable.

From figure 3 in the paper, it gives minimum previously known mults for 2x2, 3x3, 4x4, and 5x5 matrices, 7,23,49, and 98 respectively, and the better ones found by their method for 4 and 5, namely 47 and 96 (for binary matrices).

It would be nice to know if there has been any research into determining if there are any exact lower bounds for these constants.

Is it known that 7 is the minimum for 2x2? That seems likely given the amount of investigation into it, but I don't think I've heard of any proof that that is the minimum. Maybe with an astronomical number of additions, one can get 6 mults or on the other hand there could be a proof that beyond some number of additions there is nothing more that can be done.

How about 23 mults for 3x3? There could easily be fewer mults but it is beyond our current search capabilities and maybe new techniques like RL/AlphaZero could be developed to hand it to us for checking.

A cursory search of OEIS doesn't turn up anything likely for 1,7,23. But of course, after 1, those values are in question.

Like Ramsey numbers, it may be hard to get exact lower bounds even for small constants. I'm just wondering what is known.

  • 2
    $\begingroup$ According to "On multiplication of 2 × 2 matrices" by Winograd, 7 multiplications is indeed optimal for a 2x2 matrix. $\endgroup$
    – Jake
    Oct 7, 2022 at 18:26
  • 1
    $\begingroup$ @Mitch yes [added because comment needs 15 characters] $\endgroup$
    – Chao Xu
    Oct 8, 2022 at 17:43
  • 1
    $\begingroup$ I am far from an expert, but the best lower bound I am aware of is 19 and can be found in On the complexity of the multiplication of matrices of small formats, Markus Bläser. Found it thanks to this paper arxiv.org/abs/1903.11391 which can also be interesting for you. $\endgroup$
    – holf
    Oct 9, 2022 at 5:27
  • 1
    $\begingroup$ Even the border rank of 2x2 matrix multiplication is known to be 7: arxiv.org/abs/math/0407224. This means that there is no sequence of tensors of rank 6 whose limit is <2,2,2>, the 2x2 matrix multiplication tensor. For a further generalization, see cjtcs.cs.uchicago.edu/articles/2018/5/cj18-05.pdf. $\endgroup$ Oct 10, 2022 at 6:13
  • 1
    $\begingroup$ There are also lower bounds for all values of $n$, for example theoryofcomputing.org/articles/v011a011/v011a011.pdf. $\endgroup$ Oct 10, 2022 at 6:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.