(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
σ∘τ=τ∘σ.
