Fast Matrix Multiplication via Group Actions

available for noncommercial, educational purposes, provided that this copyright statement appears on the reproduced materials and notice is given that the copy-ing is by permission of the author. To disseminate otherwise or to republish re-quires written permission from the author. Recent work has shown that fast matrix multiplication algorithms can be constructed by embedding the two input matrices into a group algebra, ap-plying a generalized discrete Fourier transform, and performing the multi-plication in the Fourier basis. Developing an embedding that yields a ma-trix multiplication algorithm with running time faster than naive matrix multiplication leads to interesting combinatorial problems in group theory. The crux of such an embedding, after a group G has been chosen, lies in finding a triple of subsets of G that satisfy a certain algebraic relation. I show how the process of finding such subsets can in some cases be greatly simplified by considering the action of the group G on an appropriate set X. In particular, I focus on groups acting on regularly branching trees