Permutations and Transpositions problem help

[jeannie165]

Can someone help me? I need to prove that for m>=2, m permutations can be written as at most m-1 transpositions. I can't figure this out for the life of me! thanks in advance

 

[AKG]

I don't think this is right. Say m = 2, so we have 2 permutations. Since a transposition is a permutation, we can have, say:

(1 2)(3 4)

There's m (2) permutatitions (specifically, they are transpositions, but transpositions are permutations). They can't be written in m-1 (1) transposition. I assume you meant something else by "m transpositions" but I'll let you clarify.

 

[jeannie165]

ok...I had found one that said m>=2 but another for m>=3. Let's go with 3...then for instance (1 3 2) for S_5 can be written as a product of at most 2 transpositions...i.e. (1 3)(1 2) or a couple of others. I see this...but I can't figure how to prove for the nth term.

 

[matt grime]

samething there though:

(12)(34)(56)

Do you mean a cycle of length m (an m cycle?)

 

[jeannie165]

yes...I suppose I mean a cycle of length m...that would be the m permutations I think. I'm really floundering when it comes to this permutation stuff...thanks.

 

[matt grime]

"m permutations" isn't an m-cycle. It is, well, m permutations, and to be honest is a strange phrase, hence why I clarified what you might want.

 

[jeannie165]

This probelm is from Fraleigh's 4th ed...stated as follows
Prove the following about S_n if n>=2.
Every permutation in S_n can be written as a product of at most n-1 permutations.

The m permutations phrase I picked up while trying to get more information about this idea. Maybe it's wrong?

 

[matt grime]

Hmm, what on Earth does it define as "a permutation"?

What you wrote makes no semantic sense to me at all. (Yes, I am a group theorist part of the time).

A permutation is an element of S_n. It is writable as a single permutation: itself. The product of permutations is a permutation, hence the oddity in this question.

Every cycle of length m can be written as a product of m-1 transpositions. Every permutation in S_n can be written as a product if disjoint cycles - at most floor(n/2) of them if we discount trivial cycles, n if we allow trivial cycles and the identity as the permutation in question, and n-1 if we mean a non-trivial permutation and allow trivial cycles in its decomposition.

Is what you've written word for word the exact phrase that appears in the book?

 

[jeannie165]

yep...word for word...now the book defines a transposition as "a cycle of length 2"...so I guess the problem might be saying to show that the most 2-cycles a permutation can have is m-1...is that right?

 

[jeannie165]

oh and the book defines a permutation as a one to one function from a group A onto A.

 

[matt grime]

Hopefully the book actually defines a permutation as a bijection on a *finite* set, and not a group.

The permutations of a set are a group. Compose two permutations and get another one (closure) thus it makes little sense to write "can be written of the product of at most n-1" permutations. It is a permutation itself... I mean it's as silly as asking: show that a number can be written as a product of at most n-1 other numbers.

Here is a question that may make some sense: Show that evey element in S_n can be written as the product of n-1 or fewer transpositions.

Saying "most" really makes little sense: the permutations (12) and (34)(12)(34 are the same - there is no maximum.

 

[jeannie165]

hmmm..ok..that makes a little more sense to me. Maybe I can try to look at this prob again and see what I can get. Thanks for being so patient...this group theory is kicking my b**t ; )