1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How to find the orbits of a subgroup?

  1. Jun 30, 2010 #1
    1. The problem statement, all variables and given/known data
    Hi everyone. I have just joined the community, and I really appreciate your help. Here is what I'm struggling with:

    Assume a permutation group G generated by set S, i.e., G=<S>. Since S is given, we can easily find the orbit partition for G. Now assume the subgroup H of G that fixes one point in the permutation group. Can we easily find the orbit partition of H?

    Let me give you an example:
    Imagine group G with generators g1 = (1, 2)(3,4) and g2 = (2,5)(3,4). The orbit partition for G is {{1,2,5}, {3,4}}. Now imagine the subgroup H of G that fixes 3. What is the orbit partition for H?

    P.S: I think you know what "fixing a point" means, but here is a hint. A point in a permutation set is fixed, if it is mapped to itself in all the permutations in the set. For example, 5 is mapped to 5 in g1, so 5 is fixed in g1.

    2. The attempt at a solution
    I wanna mention two things, first the answer for the example I gave. Looking at generators g1 and g2, you realize that 3 is not fixed in any of them, but if you compose g1 and g2, you will get g1.g2=(2,5,1) which fixes 3. So you can say that the orbit of H is {{3}, {4}, {1,2,5}}.
    Second, I thought that Schreier-Sims algorithm could solve this problem in general case, but then I found out that it is usually used to check membership. I have not yet found a direct link from Schreier-Sims algorithm to what I want, but there might be a way to use Schreier-Sims algorithm.

    Thanks for your help! :-)
  2. jcsd
  3. Jun 30, 2010 #2
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook