Cyclic Permutation: A permutation f on a set S is called a cyclic permutation of length l if
∃ x1, x2, … , xi ∈ S such that f(x1) = x2, f(x2) = x3, ... , f(xi-1) = xi, f(xi) = x1
and f(x) = x ∀ x ∈ S if x ≠ x1, x2, … , xi
We write it as (x1 x2 … xi-1 xi).
Here the image of each element in the row is the next element and the image of the last of the last element is the first element.
Even Permutation: Even permutations are expressible as a product of an even number of transpositions. Application of an even permutation preserves the parity of an arbitrary list.
Odd Permutation: Odd permutations are expressible as a product of an odd number of transpositions. Application of an odd permutation preserves the parity of an arbitrary list.
Theorem 1: A cyclic permutation of n symbols has order n.
Proof: The corollary follows from
Φn(bi) = bn + i = bi ,
since all subscripts are taken modulo n, and since for
1 ≤ k < n, Φk(bi) = bk + i = bn + i .
By definition, a cyclic permutation leaves unchanged elements that are not contained in it.
For example, (143).2 = 2. Call two permutations disjoint if they have no elements in common. then the composition of two disjoint cyclic permutations is symmetric.
For example,
(04) ∘ (132) = (132) ∘ (04)
(04) ∘ (132).3 = (04).2 = 2
Theorem 2: Any permutation can be written as a composition of disjoint cycles.
Proof: Let Φ be the permutation of a set S.
For element b of S,
Φb = (b Φ.b Φ2.b . . . Φord.b-1.b)
is a cyclic permutation.
Construct the set S:
C = {b | b ∈ S : Φb}
Each element of S appears in exactly one cyclic permutation of C, since cyclic permutations are considered equal up to rotation of the elements.
(for example, (123) = (231)).
Thus, if Φn.b = d, then Φb = Φd .
Construct the composition of the cyclic permutation in C - the order does not matter, since they are pairwise disjoint. this construction yields the desired result.
For example, the identity permutation on the set {0, 1, 2, 3, 4} is a product of five cyclic permutations of order
1 : (0) . (1) . (2) . (3) . (4) . (5).
Theorem 3: The order of any permutation is the least common multiple of the lengths of its disjoint cycles.
Proof: Let Φ = γ1 · . . . · γk be a permutation, where the γi are disjoint cyclic permutations.
Since the composition of two disjoint cyclic permutations is symmetric,
Φn = γ1n · . . . · γkn ,
for all integers n.
Therefore Φn = I (where I is the identity permutation) iff for every i, 1 ≤ i ≤ k, γin is the identity transformation.
By theorem 1, Φn = I iff n is a common multiple of the lengths of the γi.
Fact: A transposition changes the parity of an arbitrary list from odd to even or from even to odd.
We must show that a transposition changes the number of inversions of the list from odd to even or even to odd.
Let m and n be the two distinct numbers that are interchanged;
In other words, the transposition is (m n).
Let L be the arbitrary list.
there are a certain number k ≥ 0 of integers that lie between m and n in the list L.
The transposition (m n) can be achieved by a succession of leaps.
∃ x1, x2, … , xi ∈ S such that f(x1) = x2, f(x2) = x3, ... , f(xi-1) = xi, f(xi) = x1
and f(x) = x ∀ x ∈ S if x ≠ x1, x2, … , xi
We write it as (x1 x2 … xi-1 xi).
Here the image of each element in the row is the next element and the image of the last of the last element is the first element.
Even Permutation: Even permutations are expressible as a product of an even number of transpositions. Application of an even permutation preserves the parity of an arbitrary list.
Odd Permutation: Odd permutations are expressible as a product of an odd number of transpositions. Application of an odd permutation preserves the parity of an arbitrary list.
Theorem 1: A cyclic permutation of n symbols has order n.
Proof: The corollary follows from
Φn(bi) = bn + i = bi ,
since all subscripts are taken modulo n, and since for
1 ≤ k < n, Φk(bi) = bk + i = bn + i .
By definition, a cyclic permutation leaves unchanged elements that are not contained in it.
For example, (143).2 = 2. Call two permutations disjoint if they have no elements in common. then the composition of two disjoint cyclic permutations is symmetric.
For example,
(04) ∘ (132) = (132) ∘ (04)
(04) ∘ (132).3 = (04).2 = 2
Theorem 2: Any permutation can be written as a composition of disjoint cycles.
Proof: Let Φ be the permutation of a set S.
For element b of S,
Φb = (b Φ.b Φ2.b . . . Φord.b-1.b)
is a cyclic permutation.
Construct the set S:
C = {b | b ∈ S : Φb}
Each element of S appears in exactly one cyclic permutation of C, since cyclic permutations are considered equal up to rotation of the elements.
(for example, (123) = (231)).
Thus, if Φn.b = d, then Φb = Φd .
Construct the composition of the cyclic permutation in C - the order does not matter, since they are pairwise disjoint. this construction yields the desired result.
For example, the identity permutation on the set {0, 1, 2, 3, 4} is a product of five cyclic permutations of order
1 : (0) . (1) . (2) . (3) . (4) . (5).
Theorem 3: The order of any permutation is the least common multiple of the lengths of its disjoint cycles.
Proof: Let Φ = γ1 · . . . · γk be a permutation, where the γi are disjoint cyclic permutations.
Since the composition of two disjoint cyclic permutations is symmetric,
Φn = γ1n · . . . · γkn ,
for all integers n.
Therefore Φn = I (where I is the identity permutation) iff for every i, 1 ≤ i ≤ k, γin is the identity transformation.
By theorem 1, Φn = I iff n is a common multiple of the lengths of the γi.
Fact: A transposition changes the parity of an arbitrary list from odd to even or from even to odd.
We must show that a transposition changes the number of inversions of the list from odd to even or even to odd.
Let m and n be the two distinct numbers that are interchanged;
In other words, the transposition is (m n).
Let L be the arbitrary list.
there are a certain number k ≥ 0 of integers that lie between m and n in the list L.
The transposition (m n) can be achieved by a succession of leaps.
- The integer m leaps over each of the k intervening integers between m and n. Each leap changes the parity of the list because it increases or decreases the total number of inversions by 1.
- The integers m and n are now adjacent, Interchange them, thereby changing the parity once again.
- the integer n leaps over the k intervening integers - the same as traversed by m in step 1 but in the opposite direction.
Since there are as many parity changes in the step 3 as in step 1, the total number of parity changes is odd, confirming the assertion of the proportion.
No comments:
Post a Comment