Non-existence of a short algorithm for multiplication of 3×3 matrices with group S_4× S_3
share
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×3 matrices, admitting a certain group G isomorphic to S_4× S_3, are investigated. It is shown that there exist no such algorithms of length ≤23. In the first part of the work, which is the content of the present article, we describe all orbits of length ≤23 of G on the set of decomposable tensors in the space M⊗ M⊗ M, where M=M_3(ℂ) is the space of complex 3×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.
READ FULL TEXT