arXiv:math/0307321math.GR
A group-theoretic approach to fast matrix multiplication
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
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 C[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^(2 + o(1)) support n-by-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.
I was puzzled as well. There is an analogous of the FFT method of multiplying polynomials and integers to the matrix multiplication case [1], but it is not as simple and probably does not belong in an introduction to linear algebra. [1] http://arxiv.org/abs/math/0307321v2
pbsdView on HNParent context