Any permutation can be written as a product of disjoint cycles. Now each cycle (a1,...,ak) can be decomposed into transpositions. So that completes the proof.
Hi guys (i gotta stop saying that, since we now have JaneBennet ),
ahem, Hi Mathematicians,
Is there anyone familiar with permutations in Abstract Algebra (if you are, skip to the "Problem:" section, the problem is in bold font, if not, you may read through this very brief introduction to permutations). permutations are one-to-one mapping diagrams with the natural numbers as the domain, kind of. for instance,
is an * permutation in which , and
we may also write these as cycles. that is, the above can be written as we omit (3) because it maps to itself and this is understood.
how did we get that form? we did the following.
start with the lowest number in the domain, obviously 1, here
so we write (1
but 1 maps to 2, so we write (1 2
and 2 maps back to 1, this is a cycle, so we close brackets here, because we go back to the beginning. so we have (1 2)
now we start at the next lowest number, 3.
but 3 maps to itself, so we have, (1 2)(3), which we can write as (1 2), because it is understood if any number in the domain is omitted, it maps to itself.
hope that crash course helped someone to understand the problem...
Problem:
I need to show that every element of is a 2-cycle or can be written as a product of 2-cycles. I am given a "suggestion,"
*) we say a permutation is of group if it is of the form
the thing is, i know that. the problem is, those do not appear as theorems or anything in the book. i believe the book mentioned them, or they were mentioned in class, but since it is not a theorem, i think we would be expected to write out why those claims are true. (the professor i have makes us write everything out, once it's not a theorem or definition, or the proof is not in the appendix. he says we should do our work so that your dumbest classmate can follow with ease)
Suppose we have a permutation on it is defined as:
1 --> 5
2 --> 9
3 --> 6
4 --> 2
5 --> 8
6 --> 7
7 --> 1
8 --> 3
9 --> 4
Then let pick the number 1 and see it gets mapped into 5 and 5 gets mapped into 8 and 8 gets mapped into 3 and 3 gets mapped into 6 and 6 gets mapped into 7 and 7 gets mapped into 1 again. The notation (1,5,8,3,6,7) represents the permutation that maps 1->5->8->3->6->7 and leaves everything untouched. Now look at number 2, which was untouched by the permutation. Now 2 gets mapped into 9 and 9 gets mapped into 4 and 4 gets mapped into 2 again. The notation (2,9,4) represents the permutation 2->9->4 and everything else untouched.
Then if you think about it, it should seem clear that . Note it is disjoint so the 3-cycle does not affect the 6-cycle and conversly. But then you can decompose (1,5,8,3,6,7) = (1,5)(5,8)(8,3)(3,6)(6,7) and (2,9,4) = (2,9)(9,4). Thus, . And the same idea works in general.