2017/08/30 by Joshua A. Grochow, Cristopher Moore, Grochow, Joshua A. +1
Computer Science · Engineering · Mathematics · #15A69 #68Q17 #68Q25 #Coding theory and cryptography #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #I.1.2 #Representation Theory (math.RT) #Symbolic Computation (cs.SC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1708.09398
openalex publication_date 2017/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than O(n3). 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).