[sage-combinat-devel] Re: Canonical form for permutation groups
On Wednesday, 10 April 2013 20:59:49 UTC+8, Christian Stump wrote: > > Hi, > > I wonder if there is a way to get a canonical form of a subgroup of a > permutation group (or, even better, any group). This would be > something like a method "canonical_labeling" for permutation groups > that returns an isomorphic permutation group, and such that two groups > are isomorphic if and only if their "canonical labellings" coincide. > > I don't think anything like that is currently implemented, right? > > A "natural" implementation would be to compute the multiplication > table of the group, apply the canonical form algorithm from graphs (by > simultaneous row and column permutations of the multiplication table), > obtain a canoncial form of the multiplication table, and turn this > data into a canonical form of a permutation group. > no, no, that's not what you want to do, certainly. A much more efficient way is to compute a strong generating set w.r.t. a "canonical" minimal base. (A base of a permutation group is a tuple of points (s_1,...,s_t) s.t. each group element g is uniquely defined by (g(s_1),...,g(s_t))). > @Nathann et al.: would this be doable without too much effort from the > current algorithm for graphs? How far is the current implementation > from the possibility to take any n*n array (or square matrix, but with > no/less restrictions on the entries) and get it into a canonical form > by simultaneous row and column permutations? > > Cheers, Christian > -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-combinat-devel] Re: Canonical form for permutation groups
Clearly there is no canonical form for arbitrary groups/subgroups since there is no algorithm to compare finitely generated groups. For finite groups there is, of course. In GAP one would just IdGroup() to get a unique label. A GPL-ed clone of the finite groups database in GAP would be nice, then we could distribute it by default... On Wednesday, April 10, 2013 1:59:49 PM UTC+1, Christian Stump wrote: > > Hi, > > I wonder if there is a way to get a canonical form of a subgroup of a > permutation group (or, even better, any group). This would be > something like a method "canonical_labeling" for permutation groups > that returns an isomorphic permutation group, and such that two groups > are isomorphic if and only if their "canonical labellings" coincide. > > I don't think anything like that is currently implemented, right? > > A "natural" implementation would be to compute the multiplication > table of the group, apply the canonical form algorithm from graphs (by > simultaneous row and column permutations of the multiplication table), > obtain a canoncial form of the multiplication table, and turn this > data into a canonical form of a permutation group. > > @Nathann et al.: would this be doable without too much effort from the > current algorithm for graphs? How far is the current implementation > from the possibility to take any n*n array (or square matrix, but with > no/less restrictions on the entries) and get it into a canonical form > by simultaneous row and column permutations? > > Cheers, Christian > -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
