Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Clearer Understanding of Permutation and Transpositions

  1. Oct 5, 2009 #1
    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.

    I'm trying to get a better understanding of how to begin proofs. I'm always a little lost when trying to solve them.
    I 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? I wrote that

    α = τ_1 · · · τ_s = (τ_1 τ_s)(τ_1 τ_s-1)...(τ_1 τ_2)

    But does this qualify as a proof for showing that any l cycle can be written as a product of l-1 cycles? Even so, how does this make sense for s geq l -1? Sorry, I'm just trying to understand this more clearly.
  2. jcsd
  3. Oct 10, 2009 #2
    I'm not sure I understand your formulation. Or, it is your partial solution I do not grasp. Do I interpret i correctly if I'd restate it as follows?

    Let a be a k-cycle in Sn. Show that if a = t1 * t2 * ... * ts, where the ti are transpositions for 1 = 1, 2, ..., s, then s must be greater than or equal to k - 1.

    We have that, if a = (A1, A2, ... ,Ak), then a = (A1, Ak)(A1, Ak-1)...(A1, A2).

    Well, this is not a proof, as it only states that there exists a way to express a as a product of k - 1 transpositions. Now, it is easily seen that we can express a as a product of a larger number of such transpositions. Just multiply it by (1, 2)(1, 2), which is the identity. The problem is to show that there is no way to express a as a product of less transpositions. I haven't proven it, but I got a feeling that thinking about how a "moves" the Ai can lead you in the right direction.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook