<p>The recent publication in Nature of <a href="https://doi.org/10.1038/s41586-022-05172-4" rel="nofollow noreferrer">&quot;Discovering faster matrix multiplication algorithms with reinforcement learning&quot;</a> 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.</p>
<p>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).</p>
<p>It would be nice to know if there has been any research into determining if there are any exact lower bounds for these constants.</p>
<p><strong>Is it known that 7 is the minimum for 2x2?</strong> 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.</p>
<p><strong>How about 23 mults for 3x3?</strong> 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.</p>
<p>A cursory search of <a href="https://oeis.org/search?q=1%2C7%2C23&amp;sort=&amp;language=&amp;go=Search&amp;n=100" rel="nofollow noreferrer">OEIS</a> doesn't turn up anything likely for 1,7,23. But of course, after 1, those values are in question.</p>
<p>Like Ramsey numbers, it may be hard to get exact lower bounds even for small constants. I'm just wondering what is known.</p>

CC BY-SA 4.0
2022-10-07T18:26:57.620Z
According to "On multiplication of 2 × 2 matrices" by Winograd, 7 multiplications is indeed optimal for a 2x2 matrix.
Jake
CC BY-SA 4.0
2022-10-07T23:03:18.087Z
@Jake Does he give a proof of impossibility for 6?
Mitch
CC BY-SA 4.0
2022-10-08T17:43:39.217Z
@Mitch yes [added because comment needs 15 characters]
Chao Xu
CC BY-SA 4.0
2022-10-08T21:34:37.600Z
@ChaoXu Nice, [paper is here](https://www.sciencedirect.com/science/article/pii/0024379571900097). The next question is... how about for 3?
Mitch
CC BY-SA 4.0
2022-10-09T05:27:42.730Z
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 https://arxiv.org/abs/1903.11391 which can also be interesting for you.
holf
CC BY-SA 4.0
2022-10-09T20:46:44.230Z
@holf Nice reference. It's at [Bläser 2019](https://www.sciencedirect.com/science/article/pii/S0885064X02000079)
Mitch
CC BY-SA 4.0
2022-10-10T06:13:47.587Z
Even the border rank of 2x2 matrix multiplication is known to be 7: https://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 http://cjtcs.cs.uchicago.edu/articles/2018/5/cj18-05.pdf.
Yuval Filmus
CC BY-SA 4.0
2022-10-10T06:14:25.853Z
There are also lower bounds for all values of $n$, for example https://theoryofcomputing.org/articles/v011a011/v011a011.pdf.
Yuval Filmus
CC BY-SA 4.0
2022-10-10T15:01:02.083Z
@YuvalFilmus From those links, I couldn't figure out the intuitive relation between border rank and # of mult operations. Any quick intuition?
Mitch
CC BY-SA 4.0
2022-10-10T16:01:18.810Z
If the border rank of $n \times n$ matrix multiplication is $r$, then $\omega \leq \log_n r$.
Yuval Filmus
CC BY-SA 4.0
2022-10-10T16:02:34.010Z
The intuition is that for the various constructions encountered in fast matrix multiplication theory, border rank is as good as rank.
Yuval Filmus
<lower-bounds><matrix-product><enumeration>
Exact lower bound on matrix multiplication
Mitch
# Exact lower bound on matrix multiplication

(Asked by: username_0 on 2022-10-07)

The recent publication in Nature of ["Discovering faster matrix multiplication algorithms with reinforcement learning"](https://doi.org/10.1038/s41586-022-05172-4) 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](https://oeis.org/search?q=1%2C7%2C23&sort=&language=&go=Search&n=100) 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.

**Tags:** lower-bounds, matrix-product, enumeration

> **Comments:**
> **username_1**: According to "On multiplication of 2 × 2 matrices" by Winograd, 7 multiplications is indeed optimal for a 2x2 matrix.  
> **username_0**: @username_1 Does he give a proof of impossibility for 6?  
> **username_2**: @username_0 yes [added because comment needs 15 characters]  
> **username_0**: @ChaoXu Nice, [paper is here](https://www.sciencedirect.com/science/article/pii/0024379571900097). The next question is... how about for 3?  
> **username_3**: 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 https://arxiv.org/abs/1903.11391 which can also be interesting for you.  
> **username_0**: @username_3 Nice reference. It's at [Bläser 2019](https://www.sciencedirect.com/science/article/pii/S0885064X02000079)  
> **username_4**: Even the border rank of 2x2 matrix multiplication is known to be 7: https://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 http://cjtcs.cs.uchicago.edu/articles/2018/5/cj18-05.pdf.  
> **username_4**: There are also lower bounds for all values of $n$, for example https://theoryofcomputing.org/articles/v011a011/v011a011.pdf.  
> **username_0**: @YuvalFilmus From those links, I couldn't figure out the intuitive relation between border rank and # of mult operations. Any quick intuition?  
> **username_4**: If the border rank of $n \times n$ matrix multiplication is $r$, then $\omega \leq \log_n r$.  
> **username_4**: The intuition is that for the various constructions encountered in fast matrix multiplication theory, border rank is as good as rank.  

---

## 0 answers

