The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication

We show how to construct highly symmetric algorithms for matrix multiplication. In particular, we consider algorithms which decompose the matrix multiplication tensor into a sum of rank-1 tensors, where the decomposition itself consists of orbits under some finite group action. We show how to use the representation theory of the corresponding group to derive simple constraints on the decomposition, which we solve by hand for n=2,3,4,5, recovering Strassen's algorithm (in a pa...

In 2003 COHN and UMANS introduced a group-theoretic approach to fast matrix multiplication. This involves finding large subsets of a group $G$ satisfying the Triple Product Property (TPP) as a means to bound the exponent $\omega$ of matrix multiplication. Recently, Hedtke and Murthy discussed several methods to find TPP triples. Because the search space for subset triples is too large, it is only possible to focus on subgroup triples. We present methods to upgrade a given T...

Many fundamental questions in theoretical computer science are naturally expressed as special cases of the following problem: Let $G$ be a complex reductive group, let $V$ be a $G$-module, and let $v,w$ be elements of $V$. Determine if $w$ is in the $G$-orbit closure of $v$. I explain the computer science problems, the questions in representation theory and algebraic geometry that they give rise to, and the new perspectives on old areas such as invariant theory that have aris...

A generalization of recent group-theoretic matrix multiplication algorithms to an analogue of the theory of partial matrix multiplication is presented. We demonstrate that the added flexibility of this approach can in some cases improve upper bounds on the exponent of matrix multiplication yielded by group-theoretic full matrix multiplication. The group theory behind our partial matrix multiplication algorithms leads to the problem of maximizing a quantity representing the "f...

We study the complexity of multiplication in noncommutative group algebras which is closely related to the complexity of matrix multiplication. We characterize such semisimple group algebras of the minimal bilinear complexity and show nontrivial lower bounds for the rest of the group algebras. These lower bounds are built on the top of Bl\"aser's results for semisimple algebras and algebras with large radical and the lower bound for arbitrary associative algebras due to Alder...

This is the second in a series of papers on rank decompositions of the matrix multiplication tensor. We present new rank $23$ decompositions for the $3\times 3$ matrix multiplication tensor $M_{\langle 3\rangle}$. All our decompositions have symmetry groups that include the standard cyclic permutation of factors but otherwise exhibit a range of behavior. One of them has 11 cubes as summands and admits an unexpected symmetry group of order 12. We establish basic information re...

We introduce a relaxation of the notion of tensor rank, called s-rank, and show that upper bounds on the s-rank of the matrix multiplication tensor imply upper bounds on the ordinary rank. In particular, if the "s-rank exponent of matrix multiplication" equals 2, then omega = 2. This connection between the s-rank exponent and the ordinary exponent enables us to significantly generalize the group-theoretic approach of Cohn and Umans, from group algebras to general algebras. Em...

The recent discovery that the exponent of matrix multiplication is determined by the rank of the symmetrized matrix multiplication tensor has invigorated interest in better understanding symmetrized matrix multiplication. I present an explicit rank 18 Waring decomposition of $sM_{\langle 3\rangle}$ and describe its symmetry group.

In 2003, Cohn and Umans described a framework for proving upper bounds on the exponent $\omega$ of matrix multiplication by reducing matrix multiplication to group algebra multiplication, and in 2005 Cohn, Kleinberg, Szegedy, and Umans proposed specific conjectures for how to obtain $\omega=2$. In this paper we rule out obtaining $\omega=2$ in this framework from abelian groups of bounded exponent. To do this we bound the size of tricolored sum-free sets in such groups, exten...

The aim of the present paper is to generalize the notion of the group determinants for finite groups. For a finite group $G$ of order $kn$ and its subgroup $H$ of order $n$, one may define an $n$ by $kn$ matrix $X=(x_{hg^{-1}})_{h\in H,g\in G}$, where $x_g$ ($g\in G$) are indeterminates indexed by the elements in $G$. Then, we define an invariant $\Theta(G,H)$ for a given pair $(G,H)$ by the $k$-wreath determinant of the matrix $X$, where $k$ is the index of $H$ in $G$. The $...