3 ms·
re: group theory approaches This (http://www.siam.org/pdf/news/174.pdf http://www.siam.org/pdf/news/174.pdf) short, highly readable paper gives a high-level ov
by pmiller2 15y ago
re: group theory approaches
This (http://www.siam.org/pdf/news/174.pdf http://www.siam.org/pdf/news/174.pdf) short, highly readable paper gives a high-level overview of the group-theoretic approach. Here are the key points, quoted from the paper:
* "What Cohn and Umans realized is that under certain conditions, matrix multiplication, too, can be embedded into the group algebra of a finite
group G, although the embedding is more complex and the group must be non-abelian to yield a nontrivial bound."
The conditions that must be satisfied are as follows:
* "...the group has three subgroups, H_1, H_2, H_3, with the property that whenever h_1 ∈ H_1, h_2 ∈ H_2, and h_3 ∈ H_3 with h_1 h_2 h_3 = 1, then h_1 = h_2 = h_3 = 1" (AKA the "triple-product property,") and
* "|H1||H2||H3| > Σd_i^3," where the d_i's are the dimensions of the square submatrices into which we decompose the original matrix. (AKA "beating the sum of cubes.")
The groups that have been found to have these properties are "wreath products of abelian groups with the symmetric group S_n."