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: Proof of transpositions

  1. Oct 4, 2009 #1
    1. The problem statement, all variables and given/known data

    Let α (alpha) all in S_n be a cycle of length l. Prove that if α = τ_1 · · · τ_s, where τ_i are transpositions, then s geq l − 1.

    2. Relevant equations

    3. The attempt at a solution

    What I was actually looking for is where to start with this proof. I don't want the answer, just a push in what direction I should be heading in. This is my trouble with proofs, I usually have no idea where to start.

    I've been told in the past to start with definitions of what is given to you in the question.

    A transposition is a permutation (bijective function of X onto itself) f, such that there exist i,j such that f(a_i) = a_j, f(a_j) = a_i and f(a_k) = a_k for all other k.

    I know that "l" is the length of the cycle.

    I also know that I want to somehow show that s is greater than l - 1 cycles. Does this mean I need to find out or show that any l cycle can be written as a product of l-1 cycles? Sorry, I'm just having a hard time with understanding this one.

    But I don't see how this helps me. Any suggestions?
    Last edited: Oct 5, 2009
  2. jcsd
  3. Oct 5, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hi MellyVG257! Welcome to PF! :smile:

    (have a geq: ≤ and try using the X2 tag just above the Reply box :wink:)

    For example, (1,2,3,4,5) = (1,2)(2,3)(3,4)(4,5)

    but also = (1,2)(2,4)(4,5)(3,5)(2,5)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook