GroupOrbits
GroupOrbits[group,{p1,…}]
returns the orbits of the points pi under the action of the elements of group.
GroupOrbits[group,{p1,…},f]
finds the orbits under the group action given by a function f.
Details
- Two points belong to the same orbit under group if there is an element g in group such that the image of one point under g is the other point.
- If a point p is fixed by all elements in group then it forms an orbit {p}.
- GroupOrbits[group] gives all orbits in the natural domain of action of group.
- Orbits are given as sorted lists.
- Evaluation of f[p,g] for an action function f, a point p and a permutation g of the given group is assumed to return another point p'.
- For permutation groups, the default group action is taken to be PermutationReplace.
Examples
open all close allBasic Examples (1)
group = PermutationGroup[{Cycles[{{1, 3, 6}, {2, 4}}], Cycles[{{6, 7}}]}];GroupOrbits[group, {3}]Point 7 belongs to the same orbit:
GroupOrbits[group, {7, 3}]Point 4 belongs to a different orbit:
GroupOrbits[group, {7, 3, 4}]Scope (4)
Orbits of integer points under a permutation group:
GroupOrbits[PermutationGroup[{Cycles[{{1, 2}}], Cycles[{{2, 3, 4, 5, 6}}]}], {4}]Orbits of all points in the support of the group:
GroupOrbits[PermutationGroup[{Cycles[{{1, 4}}]}]]When the group only contains the identity permutation, all points are singletons:
GroupOrbits[PermutationGroup[{}], {2, 3}]A rank-4 symbolic tensor that is symmetric in the first and second pairs of indices:
R[a_, b_, c_, d_] := R[b, a, c, d] /; a > b
R[a_, b_, c_, d_] := R[a, b, d, c] /; c > dMatrixForm[tensor = Array[R, {2, 2, 2, 2}]]A group of eight permutations:
group = PermutationGroup[{Cycles[{{1, 2}}], Cycles[{{1, 3}, {2, 4}}]}]GroupOrder[group]Construct the orbit of tensors under the action of transposition. Only two elements are different:
Map[MatrixForm, GroupOrbits[group, {tensor}, Transpose], {2}]Applications (3)
A group acts transitively in a domain if all points of the domain belong to the same orbit:
transitivePermutationGroupQ[group_, domain_] := GroupOrbits[group, domain] === {domain};These permutations generate a transitive group:
transitivePermutationGroupQ[PermutationGroup[{Cycles[{{1, 2}}], Cycles[{{1, 3}, {2, 4}}]}], {1, 2, 3, 4}]But these do not generate a transitive group on the same domain:
transitivePermutationGroupQ[PermutationGroup[{Cycles[{{1, 2}}], Cycles[{{3, 4}}]}], {1, 2, 3, 4}]The orbit of a permutation under standard permutation action is its conjugacy class:
GroupOrbits[SymmetricGroup[5], {Cycles[{{1, 2}, {3, 4, 5}}]}]Check whether a simple and connected graph is distance-transitive:
DistanceTransitiveGraphQ[g_Graph] := With[{dm = GraphDistanceMatrix[g], pg = GraphAutomorphismGroup[g]},
AllTrue[Range[Max[dm]], distanceTransitiveGraphQ[g, dm, pg, #]&]]
distanceTransitiveGraphQ[g_, dm_, pg_, d_] := With[{dom = Position[dm, d]}, GroupOrbits[pg, dom] === {dom}]These graphs are distance-transitive:
DistanceTransitiveGraphQ[GraphData["DodecahedralGraph"]]DistanceTransitiveGraphQ[GraphData["HeawoodGraph"]]These graphs are not distance-transitive:
DistanceTransitiveGraphQ[GraphData["ShrikhandeGraph"]]DistanceTransitiveGraphQ[GraphData["Tutte12Cage"]]Properties & Relations (8)
According to the orbit-counting lemma, the number of orbits of a permutation group is equal to the average number of fixed points of its elements.
This function returns the points fixed by a permutation:
fix[g_, n_] := Complement[Range[n], PermutationSupport[g]]fix[Cycles[{{2, 3}}], 6]Take a group with three orbits:
group = PermutationGroup[{Cycles[{{1, 2}}], Cycles[{{3, 4}}], Cycles[{{5, 6}}]}]GroupOrbits[group]Compute how many points are fixed by each element in the group:
list = GroupElements[group]Length /@ (fix[#, 6]& /@ list)The average is the number of orbits:
Mean[%]Orbits under the action of the identity group:
GroupOrbits[PermutationGroup[{}], Range[5]]GroupOrbits[PermutationGroup[{}]]Group orbits of an empty list:
GroupOrbits[PermutationGroup[{Cycles[{{1, 3}}], Cycles[{{1, 2, 3}}]}], {}]The lengths of the orbits are divisors of the order of the group:
group = PermutationGroup[{Cycles[{{1, 2}, {4, 5}}], Cycles[{{1, 7, 2}, {3, 12}, {4, 10}, {5, 6, 9, 11, 13, 14, 8, 15}}]}];GroupOrbits[group]Length /@ %GroupOrder[group]//FactorIntegerIf the generators have supports of very different size then usually there is one large and several small orbits:
group = PermutationGroup[{RandomPermutation[100], RandomPermutation[10000]}];Length /@ GroupOrbits[group]The orbit of point 1 under a group:
group = PermutationGroup[{Cycles[{{1, 2}, {3, 4}}], Cycles[{{2, 4}}]}];
GroupOrbits[group, {1}]Folding PermutationReplace over the group elements does not find all orbit points:
FoldList[PermutationReplace, 1, GroupElements[group]]For a general expression, an orbit under Permute action is equivalent to the action of all group elements:
GroupOrbits[AlternatingGroup[4], {F[a, b, c, d]}, Permute]Permute[F[a, b, c, d], AlternatingGroup[4]] === First[%]However, if the expression has repeated elements, then GroupOrbits will return only distinct results:
GroupOrbits[AlternatingGroup[4], {F[a, a, b, b]}, Permute]Permute[F[a, a, b, b], AlternatingGroup[4]] === First[%]These two expressions cannot be related by a group element because they belong to different orbits:
GroupOrbits[AlternatingGroup[4], {F[a, c, b, d], F[c, d, a, b]}, Permute]Permutations of an alternating group cannot change signature:
Map[Signature, %, {2}]Text
Wolfram Research (2010), GroupOrbits, Wolfram Language function, https://reference.wolfram.com/language/ref/GroupOrbits.html.
CMS
Wolfram Language. 2010. "GroupOrbits." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/GroupOrbits.html.
APA
Wolfram Language. (2010). GroupOrbits. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/GroupOrbits.html