# Permutations and Transpositions

1. Dec 5, 2004

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

Last edited: Dec 5, 2004
2. Dec 5, 2004

### 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.

3. Dec 5, 2004

### 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.

4. Dec 5, 2004

### matt grime

samething there though:

(12)(34)(56)

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

5. Dec 5, 2004

### 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.

6. Dec 5, 2004

### 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.

7. Dec 5, 2004

### 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.

8. Dec 5, 2004

### 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?

9. Dec 5, 2004

### 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?

10. Dec 5, 2004

### jeannie165

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

11. Dec 6, 2004

### 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.

12. Dec 6, 2004

### 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 ; )