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