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: Permutations and cycles - linear algebra

  1. Jan 24, 2010 #1
    1. The problem statement, all variables and given/known data
    Let [tex]\rho[/tex] [tex]\in[/tex]Sym(n), p be prime, r be the remainder when n is divided by p (so 0[tex]\leq[/tex]r<p and n=qp+r for some integer q).

    1. Show that [tex]\rho[/tex]^p = [tex]\iota[/tex] iff the cycles of [tex]\rho[/tex] all have lengths 1 or p.

    2. Show that if [tex]\rho[/tex]^p = [tex]\iota[/tex] then |Supp([tex]\rho[/tex])| is a multiple of p and |Fix([tex]\rho[/tex])|[tex]\equiv[/tex] r(mod p).

    2. Relevant equations
    Fix([tex]\rho[/tex]) := {x|x[tex]\rho[/tex] = x}
    Supp([tex]\rho[/tex]) := {x|x[tex]\rho[/tex] [tex]\neq[/tex] x}

    3. The attempt at a solution

    I really don't have many ideas on these at all.

    1) If all cycles have length 1 then it is clear that [tex]\rho[/tex]p is the identity.
    I don't know what I can deduce from all cycles having length p. The other way around, I can see if we have the identity that all cycles could be length 1, but I don't know how to go about getting length p.

    2) I have no idea how to start this.

  2. jcsd
  3. Jan 24, 2010 #2
    When you write a permutation [tex]\rho[/tex], of lenght n, in terms of cycles, you have:

    [tex]\rho = \left(a_1...a_{k_1}\right)\left(a_{k_1}...a_{k_2}\right)...\left(a_{k_i}...a_{k_j}\right)[/tex]

    The cycles' lengths must sum to n and, if [tex]\rho^d = I[/tex], then all cycles must have undergone a full rotation after d iterations.

    But this implies that d must divide your prime p. Now, what are the possible divisors of p?

    As for (2), it's just a translation of the division n = qp + r in terms of the cycles: the cycles oh lenght p correspond to a factor in qp, and r = 1+1+...+1 (r times) are the cycles of lenght one.
  4. Jan 24, 2010 #3
    Thank you so much! I've just started with permutations and as of yet I haven't really grasped it, but I do understand that now.

    Another question:

    If t1 and t2 are transpositions in Sym(n), then show that t1t2 = I, (t1t2)2 = I or (t1t2)3 = I (I is the identity permutation).

    What condition on t1 and t2 determines which of these occurs?

    What is the cycle structure of t1t2 in each case?
  5. Jan 24, 2010 #4
    A transposition is a permutation that exchanges just two elements; in terms of cycles, a transposition has a cycle of lenght 2, and all the others of lenght 1.

    It's immediate that any transposition t verify t^2=I; it's less immediate that they generate the symmetric group, but they do: any permutation is the product of transpositions.

    For any two transpositions t1 and t2, your three cases correspond to:

    (1) t1 = t2; this gives t1t2=t2t1=I.

    (2) t1 and t2 are disjoint (their 2-cycles don't affect each other); in this case t1t2 is a permutation with exactly two 2-cycles (the others are 1-cycles).

    (3) The 2-cycles of t1 and t2 share one common element, so t1t2 has one 3-cycle (and the rest are 1-cycles).
  6. Jan 24, 2010 #5
    Thank you again!

    One last question:

    Let [tex]\rho[/tex] be in Sym(n). For which values of n is it true that if [tex]\rho[/tex] is even then [tex]\rho[/tex]^m = I for some odd integer m?

    Is this true for n=km where k is a natural number?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook