# Best known bounds on (border) ranks of small matrix multiplication tensors?

The $(m,n,p)$-matrix multiplication tensor is a representation of the bilinear map $T\colon\mathbb{R}^{m\times n}\times\mathbb{R}^{n\times p}\rightarrow\mathbb{R}^{m\times p}$ given by $T(A,B)=AB$. Any low-rank decomposition of this tensor leads to a faster-than-naive matrix multiplication algorithm (à la the Strassen algorithm). Actually, to get a fast algorithm, it suffices for arbitrarily small perturbations of this tensor to have low rank; the minimum of such ranks is called the border rank.

Where can I find a recent table of the best known upper and lower bounds on the rank and border rank of the $(m,n,p)$-matrix multiplication tensor for moderately small values of $m$, $n$ and $p$?

Slide 24 here is close to what I want, though I would prefer explicit citations and larger $m$, $n$ and $p$.

Here's a related question that focuses on the $(3,3,3)$ case.

• Have you already looked into the book: Tensors: geometry and applications by Landsberg? – Suvrit Sep 9 '16 at 15:28
• @Survit - I've looked online, but the links I found only provide limited views. While I haven't found what I'm looking for, I did find a drawing of a pickle held to someone's head: ams.org/books/gsm/128/gsm128-endmatter.pdf#page=19 – Dustin G. Mixon Sep 9 '16 at 20:02
• Being completely not a specialist in this field I nevertheless suggest that I know a person who must know the exact answer to your question. His personal page is spring.inm.ras.ru/osel (Ivan Oseledets) and one of his main research topics (together with E.E. Tyrtyshnikov) are so called tensor train approximations which are something closely related to low-rank approximations for tensors. So, probably you could ask the professor. – VorKir Sep 11 '16 at 10:53

There is a table at http://cristal.univ-lille.fr/~sedoglav/FMM/ that (try to) gather such bounds

• It is also good to summarize the content for the case something happens to the link. – András Bátkai Dec 10 '17 at 14:47

There are upper bounds collections in 1 and 2.

The best known lower bounds for (3,3,3) is $R \geq 19$ by Bläser (3), for (2,2,m) is $R \geq 3m + 2$ by Alekseev (4, in Russian), and general lower bounds in 5 and 6

1 C.-E. Drevet, Md. Nazrul Islam, and É. Schost. "Optimization techniques for small matrix multiplication." Theor. Comp. Sci. 412(22) (2011), pp. 2219-2236.

2 A. V. Smirnov. "The bilinear complexity and practical algorithms for matrix multiplication." Comput. Math. and Math. Physics 53(12) (2013), pp. 1781-1795.

3 M. Bläser. "On the complexity of the multiplication of matrices of small formats." J. of Complexity 19(1) (2003), pp. 43-60.

4 V. B. Alekseev "On bilinear complexity of multiplication of $m \times 2$ and $2 \times 2$ matrices" Chebyshevsky Sbornik 16(4) (2015), pp. 11-27 [in Russian]

5 J.M. Landsberg, G. Ottaviani "New Lower Bounds for the Border Rank of Matrix Multiplication" Theory of Computing 11, 2015

6 A. Massarenti, E. Ravioli "On the rank of $n\times n$ matrix multiplication", arXiv:1211.6320v2 [corrected version of a journal paper in Lin. Alg. Appl.]