Title: Designing Strassen's algorithm,
Abstract: In 1969, Strassen shocked the world by showing that two n x n matrices could
be multiplied in time asymptotically less than $O(n^3)$. 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).