Reference no: EM1318738
From this point on we will not concern ourselves with the fact that the set of all permutations over Ω forms a group. We will be focusing on individual permutations.
There is another very useful way to describe permutations. We denote by {a1, a2,.......ak} a cycle of k elements. This cycle defines a permutation ρ{a1} = a1, ρ{a2} = a2,...........,ρ{ak-1} = ak & also ρ{ak} = a1. A product of two cycles corresponding to the composition {as functions} of the two corresponding permutation. For example, consider the permutation ρ = {1 2 3}{2 4}, defined as a composition - apply first the rightmost one - of two cycles. Suppose that we wish to find ρ{4} we have that fist 4 goes to 2 in the right cycles. Then, 2 go to 3. Therefore, ρ{4} = 3. How about ρ{1}? The second cycle is not concerned at all with 1 hence, ρ{1} = 2. As another example consider a permutation defined by the product { 1 2 3 4 X 4 5 6 7}{8 9}. Clearly, every product of one or more cycles defines a permutation. The other direction is also true. Actually, given any permutation can we always write it as a product of disjoint cycles? Two cycles are disjoint if they don't have any common element. Such a thing is called cycle-decomposition of the permutation. One of the first theorems for permutations says that
Theorem: Every permutation r over Ω can be written as a product of disjoint cycles. The main focus of this question is to prove this theorem.
For example, consider the permutation we had before:
Observe that if we start from 1 we can go to 2 and then from 2 we can go back to 1 and this repeats forever. Also, 3 goes to 3 and then again. Hence, we can write r is r = {1 2}{3}. That is, 1,2 appeared only in one cycle, and 3 only in one. Actually, for notational simplicity we can omit cycles that are identities on certain elements, since this is well-understood. Hence, we could about notation and write r = {1 2}. Also note that indeed those cycles are disjoint.
You will prove this theorem by showing that for every permutation given in the input {r{1},........,r{n}} you can construct in the output the cycle-decomposition of this permutation. That is, your proof will give us for free an algorithm to actually solve this problem in practice.
Define the problem where given the permutation we construct cycle decomposition and give at least two examples of input-outputs.