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: 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