Some additional questions: What about extended sequences of 2x2 matrix multiplications? Are there any savings if you're doing a sequence? What about *quaternion multiplication* itself? This can be done with fewer than the obvious number of scalar (Q1: real; Q2: complex) multiplications. Does this new theory provide any more insight into minimizing quaternion multiplication? What about quaternion rotations -- e.g., qvq* -- where q* is the quaternion conjugate of q ? Can this theory take advantage of the fact that q=q0+w, q*=q0-w, where q0 is real and w is a real 3-vector? Are there any new insights into FFT's -- e.g., a novel/elegant exposition? At 09:58 AM 12/9/2016, Cris Moore wrote:
Did I understand correctly that 2x2 is related to the symmetry of a equilateral triangle in n-space (what is 'n' here?)
yes, where n=2 (n is the size of matrices we're multiplying)
I.e., this is *not* the symmetric group on 3 elements, but the cyclic group of 3 elements, correct?
In fact it's the symmetric group, or alternately the dihedral group. So it includes all 3!=6 permutations.
I.e., this is *not* the symmetric group on 4 elements, but the symmetry group of the equilateral tetrahedron in ordinary 3-space?
For n > 2, what matters in this particular family of constructions (we're looking for others as well) is that we act on the vertices of the simplex in a 3-transitive way. [That means that any ordered triple of distinct elements can get sent to any other ordered triple.]
In n dimensions, this simplex has n+1 vertices. So in n=3 we use S_4, in n=4 we use A_5 (the even permutations of 5 objects), and in n=5 we use a funky embedding of S_5 in S_6 that acts 3-transitively on subsets of {1,2,3,4,5,6} of size 3.
Any chance that the idea of *solvable groups* comes up in relation to the matrix mult problem?
Well, there's a nice theory of permutation groups and when you can have 3-transitivity, 4-transitivity, etc. without having all permutations (or at least all even ones).
Does this "geometric" line of attack have any elegant treatment of *determinant* computation?
I'm not sure. As you probably know, understanding the determinant vs. the permanent in an algebraic/geometric way is one of the major goals of this field. My collaborator Josh Grochow knows a lot more about this than I do - Cris