RUS  ENG
Full version
JOURNALS // Proceedings of the Institute of Mathematics of the NAS of Belarus // Archive

Tr. Inst. Mat., 2022 Volume 30, Number 1-2, Pages 99–116 (Mi timb337)

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

V. P. Burichenko

Institute of Mathematics of the National Academy of Sciences of Belarus

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\times3$ 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 $\leq23$. In the first part of the work, which is the content of the present article, we describe all orbits of length $\leq23$ 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\times3$ 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.

UDC: 519.712.6+512.64

MSC: 68Q25, 20C

Language: English



© Steklov Math. Inst. of RAS, 2025