In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than @math . While the recursive construction in his algorithm is very clear, the key gain was made by showing that 2 x 2 matrix multiplication could be performed with only 7 multiplications instead of 8. The latter construction was arrived at by a process of elimination and appears to come out of thin air. Here, we give the simplest and most transparent proof of Strassen's algorithm that we are aware of, using only a simple unitary 2-design and a few easy lines of calculation. Moreover, using basic facts from the representation theory of finite groups, we use 2-designs coming from group orbits to generalize our construction to all n (although the resulting algorithms aren't optimal for n at least 3).
One may also reasonably wonder whether there is any relationship between our group-based construction and the family of group-based constructions suggested by Cohn and Umans @cite_16 , including the constructions given in @cite_9 and generalizations in @cite_4 . While there may be a common generalization that captures both methods, at the moment we don't know of any direct relationship between the two. Indeed, one cannot use the group-theoretic approach of @cite_16 to explain Strassen's result, even though the constructions of @cite_9 get a better exponent: The only way to use their approach for the @math case is to embed @math into the cyclic group @math , but Cohn and Umans showed that one could not beat @math using only abelian groups. (Some of their more complicated constructions can beat @math in abelian groups, but those involve embedding multiple copies of @math into the same group simultaneously, whereas here we are explicitly talking about embedding a single copy of @math .)
@cite_9 @cite_16 @cite_4
2111612671 2951997246
We develop a new, group-theoretic approach to bounding the exponent of matrix multiplication. There are two components to this approach: (1) identifying groups G that admit a certain type of embedding of matrix multiplication into the group algebra spl Copf [G], and (2) controlling the dimensions of the irreducible representations of such groups. We present machinery and examples to support (1), including a proof that certain families of groups of order n sup 2+o(1) support n spl times n matrix multiplication, a necessary condition for the approach to yield exponent 2. Although we cannot yet completely achieve both (1) and (2), we hope that it may be possible, and we suggest potential routes to that result using the constructions in this paper. 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. Embedding matrix multiplication into general algebra multiplication yields bounds on s-rank (not ordinary rank) and, prior to this paper, that had been a barrier to working with general algebras. We identify adjacency algebras of coherent configurations as a promising family of algebras in the generalized framework. Coherent configurations are combinatorial objects that generalize groups and group actions; adjacency algebras are the analogue of group algebras and retain many of their important features. As with groups, coherent configurations support matrix multiplication when a natural combinatorial condition is satisfied, involving triangles of points in their underlying geometry. Finally, we prove a closure property involving symmetric powers of adjacency algebras, which enables us to prove nontrivial bounds on omega using commutative coherent configurations and suggests that commutative coherent configurations may be sufficient to prove omega = 2. Altogether, our results show that bounds on omega can be established by embedding large matrix multiplication instances into small commutative coherent configurations, while avoiding the representation-theoretic complications that were present in the group-theoretic approach.