Non-existence of a short algorithm for multiplication of $3\times 3$ matrices with group $S_4\times S_3$

Abstract

One of prospective ways to find new fast algorithms of matrix multiplication is to study algorithms admitting nontrivial symmetries. In the work possible algorithms for multiplication of $3\times 3$ matrices, admitting a certain group $G$ isomorphic to $S_4\times S_3$, are investigated. It is shown that there exist no such algorithms of length $\le 23$. In the first part of the work, which is the content of the present article, we describe all orbits of length $\le 23$ of $G$ on the set of decomposable tensors in the space $M\otimes M\otimes M$, where $M=M_3(\mathbb{C})$ is the space of complex $3\times 3$ matrices. In the second part of the work this description will be used to prove that a short algorithm with the above-mentioned group does not exist.

19 pp. Accepted for publication in Proceedings of the Institute of mathematics (of Academy of Sciences of Belarus)