# Proof of transpositions

1. Oct 4, 2009

### MellyVG257

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

### tiny-tim

Welcome to PF!

Hi MellyVG257! Welcome to PF!

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

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)

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook