(5) Permutations to Transpositions Flashcards
Define permutation of a nonempty set A
a function from A to A that is a bijection
T/F. Function composition is a binary operation on the set of permutation of A.
T
The direction of the composition of permutations
Right to left
σ∘τ≠τ∘σ. Why?
composition of permutation is not commutative unless they are disjoint
If |A|=|B|, then
SsubA ≅ SsubB
_____ is the group of permutations of A under composition
Symmetric Group of Degree n, Ssubn
What is D3?
group of symmetries of an equilateral triangle
T/F. If n≥3, then Sn is abelian,
F. non cyclic => not non abelian
State Cayley’s Theorem
Every group is isomorphic to a group of permutation
What is the left regular representation of G?
xxxxxxxxxxxxxxx
What is the right regular representation of G?
xxxxxxxxxxxxxxxxxxx
The relation ∽ defined by x∽y is an equivalence relation on A iff
y=σ^k(x) for some k ∈ Z
Let σ ∈ Ssubn and x ∈ A={1,2,3,…,n}. The orbit σ containing x is
{σ^k(x) | k∈ℤ}
The orbits of σ ∈ Ssubn forms a partition on Set A. Why»
Because ∽ is an equivalence relation
What is a cycle?
A permutation σ ∈ Ssubn if it has at most 1 orbit containing more than one element.
What is the length of a cycle?
number of elements in its largest orbit?
idsubA=?
(1)
T/F. The cycle notation of any permutation is not unique.
T
What is the inverse of a cycle: (a1,a2,a3,…,an)?
(a, an, an-1, an-2,…,a2)
inverse of α∘β?
β^-1∘α^-1
The order of a cycle is its ___
length
Let σ1,σ2,,..,σk be cycles of Ssubn. We say that the cycles are DISJOINT if for all ________ and ________, σi(a)_____ implies that _______.
i ∈ {1,2,3,..,k} and a ∈ A ={1,2,3…,n}
σi(a≠a implies that σj(a)=a for each j ∈ {1,2,3,..,k}{i}
T/F. Any permutation can be written as a cycle but not as a product of disjoint cycles.
F. Both true.
If σ,τ are disjoint cycles then
σ∘τ=τ∘σ.
(12)(34)(56)=(34)(12)(56). Why?
unique up to the arrangement of the factors
The order of σ is the ____ of the disjoint cycles whose product is σ
LCM of the lengths
A cycle of length 2
transposition
T/F. Every permutation σ ∈ Ssubn is a product of transpositions.
F. n≥1
The inverse of a transposition is
itself
The identity permutation is an even permutation. Why>
Because the total number of transpositions of any σ ∈ Ssubn and its inverse is always even.
T/F. A permutation can be written as a product of even number and at the same time odd number of permutations
F
If σ ∈ Ssubn is a cycle of length k, then σ is an even permutation iff
k is odd that is the number of transpositions is k-1
If α,β are even permutations then α∘β must be ____
also even
T/F. The set of even permutations in Ssubn forms a subgroup if Ssubn.
T
subgroup of Ssubn containing all even permutations of Sn
alternating group of degree n, Asubn
The number of even and odd permutations are equal. That is,
|Asubn|=n!/2
