Transcript Math 3121 Lecture 7 ppt97

Math 3121
Abstract Algebra I
Lecture 7:
Finish Section 7
Sections 8
Finish Section 7
• Examples in class of Cayley Digraphs
Cayley Diagraph
• For each generating set of a finite group G, we
can draw a graph whose vertices are elements
of G and whose arcs represent right
multiplication by a generator. Each arc is
labeled according to the generator.
• Examples in class: Z6
Properties of Cayley Diagraphs
1.
2.
3.
4.
Can get to any vertex from any other by a path. Reason: Every equation
g x = h has a solution in G and each member of G can be written as a
product of generators and their inverses.
At most one arc goes from any vertex g to a vertex h. Reason: The
solution of g x = h is unique.
Each vertex g has exactly one arc of each type starting at g and exactly
one arc of each type ending at g. Reason: It is constructed this way.
If two different sequences of arc types go from vertex g to vertex h, then
these two sequences applied to any other vertex will go to the same
vertex.
Note: These four properties characterize Cayley diagraphs.
Examples
• Examples:
Write out table of group described by Cayley
diagraph on page 72. Note the inner and outer
squares have different directions.
Try this with triangles - note the directions of inner
and outer triangles have same direction on page
71. Now do them with opposite directions.
What about pentagons?
HW for Section 7
• Don’t hand in:
Pages 72-73: 1, 3, 5, 9
• Hand in (Due Tues, Oct 28):
page 73: 12, 14, 16
Section 8
• Section 8: Groups of Permutations
– Definition and Notation of Permutation
– Theorem: Permutations on a set form a group
with composition as binary operation.
– Definition: Symmetric Group on n letters
– Definition: Dihedral group
– Cayley’s Theorem
Permutations
Definition: A permutation of a set A is a function from A
to A that is one-to-one and onto.
Examples:
1) Let A = {a, b, c} , and let f: A  A such that
f(a) = b
f(b) = c
f(c) = a
2) Let A = the set of real numbers, and let f: A  A such
that f(x) = 2 x. Does this work if A is the set of integers?
Permutation Groups
Theorem: Let A be a nonempty set, and let Perm[A] be the set
of permutations of A. Then Perm[A] is a group with
composition as the binary operation.
Proof: Composition is a well defined binary operation on
Perm[A]. It satisfies: 1) It is associative because composition
is associative.
2) The identity map from A to itself acts as an identity for
composition. Hence Perm[A] has an identity.
3) Every permutation is one-to-one onto, and thus has an
inverse function. The inverse is also a 1-1 function from A
onto itself. Hence Perm[A] is closed under inverses.
Permutation Notation
Write
x2 ... xn 
 x1


 f ( x1 ) f ( x2 ) ... f ( xn ) 
for f: {x1, x2, …, xn}  {x1, x2, …, xn}
Note: Most of the time, the set will be {1, 2, …,n}
Composition in Permutation Notation
• Composition in permutation notation is represented by
multiplicatively. Note the order is right to left in this textbook
(and hence in this class).
x2
... xn  x1
x2
...
 x1


 g ( x1 ) g ( x2 ) ... g ( xn )  f ( x1 ) f ( x2 ) ...
x2
...
xn 
 x1

 
 g ( f ( x1 )) g ( f ( x2 )) ... g ( f ( xn )) 
xn 

f ( xn ) 
Composition in Permutation Notation
Procedure: Fill in each column at a time. For each column of the
result, the top row determines a column of the right system.
In that column, the entry in the second row determines a
column of the left system. In that column, the entry in the
second column determines the entry of the selected column
of the result.
x2
... xn  x1
x2
...
xn 
 x1



 g ( x1 ) g ( x2 ) ... g ( xn )  f ( x1 ) f ( x2 ) ... f ( xn ) 
x2
...
xn 
 x1

 
 g ( f ( x1 )) g ( f ( x2 )) ... g ( f ( xn )) 
Example
• Try
 1 2 3 4  1 2 3 4   1 2 3 4 


  

 2 3 1 4  3 4 1 2  

The Symmetric Group on n Letters
• Sn denotes the permutation group on the set
{1, 2, …, n} and is called the symmetric group
on n letters.
• Note: Sn has n! elements. Why?
• Look at S1, S2 , S3
1
 0  
1
1
1  
2
2 3

2 3
2 3

3 1
1
 2  
3
1
1  
1
2 3

1 2
2 3

3 2
1
 2  
3
1
3  
2
2 3

2 1
2 3

1 3
S3 = Symmetric Group on
3 Letters
ρ0
ρ1
ρ2
μ1
μ2
μ3
ρ0
ρ0
ρ1
ρ2
μ1
μ2
μ3
ρ1
ρ1
ρ2
ρ0
μ3
μ1
μ2
ρ2
ρ2
ρ0
ρ1
μ2
μ3
μ1
μ1
μ1
μ2
μ3
ρ0
ρ1
ρ2
μ2
μ2
μ3
μ1
ρ2
ρ0
ρ1
μ3
μ3
μ1
μ2
ρ1
ρ2
ρ0
Symmetries of the Equilateral Triangle
3
3
3
ρ0
ρ1
ρ2
1
1
2
1
2
1
3
3
3
μ1
μ2
μ3
2
1
2
1
2
2
1
 0  
1
1
1  
2
2 3

2 3
2 3

3 1
1
 2  
3
1
1  
1
2 3

1 2
2 3

3 2
1
 2  
3
1
3  
2
2 3

2 1
2 3

1 3
S3=D3 = 3rd Dihedral
Group
3
2
1
ρ0
ρ1
ρ2
μ1
μ2
μ3
ρ0
ρ0
ρ1
ρ2
μ1
μ2
μ3
ρ1
ρ1
ρ2
ρ0
μ3
μ1
μ2
ρ2
ρ2
ρ0
ρ1
μ2
μ3
μ1
μ1
μ1
μ2
μ3
ρ0
ρ1
ρ2
μ2
μ2
μ3
μ1
ρ2
ρ0
ρ1
μ3
μ3
μ1
μ2
ρ1
ρ2
ρ0
1 2 3 4 

 0  
1 2 3 4 
 1 2 3 4

1  
2
3
4
1


1 2 3 4

 2  
3 4 1 2
1
2
3
1
2
2
1
3
4
4
3
1
2
4

 3  
 4 1 2 3
1  
S4=D4 = Dihedral Group
4

3
 1 2 3 4

 2  
4 3 2 1
1 2 3 4

1  
3 2 1 4
1 2 3 4 

 2  
1 4 3 2 
ρ0
ρ1
ρ2
ρ3
μ1
μ2
δ1
δ2
ρ0
ρ0
ρ1
ρ2
ρ3
μ1
μ2
δ1
δ2
ρ1
ρ1
ρ2
ρ3
ρ0
δ1
δ2
μ2
μ1
ρ2
ρ2
ρ3
ρ0
ρ1
μ2
μ1
δ2
δ1
ρ3
ρ3
ρ0
ρ1
ρ2
δ2
δ1
μ1
μ2
μ1
μ1
δ2
μ2
δ1
ρ0
ρ2
ρ3
ρ1
μ2
μ2
δ1
μ1
δ2
ρ2
ρ0
ρ1
ρ3
δ1
δ1
μ1
δ2
μ2
ρ1
ρ3
ρ0
ρ2
δ2
δ2
μ2
δ1
μ1
ρ3
ρ1
ρ2
ρ0
Symmetries of the Square
4
3
4
3
ρ0
ρ1
1
2
4
3
1
4
1
3
1
4
3
1
2
4
3
δ1
2
1
3
ρ3
2
4
μ2
2
3
ρ2
2
μ1
1
4
δ2
2
1
2
Cayley’s Theorem
Theorem (Cayley’s Theorem): Every group is isomorphic to a group of
permutations.
Proof: Let G be a group. We show that G is isomorphic to a subgroup of the
permutations on the set G. For each a in G, let ρa be the map from G to
itself given by left multiplication by a. That is, ρa(g) = a g. Then ρa is oneto-one and onto. In fact, it has an inverse. So ρa is a permutation of the
set G. The map ρ that takes a to ρa is a homomorphism, because
ρa b(g) = a b g = a ρb(g) = ρa (ρb(g)) = (ρa ρb)(g)
ρ is one-to-one and it is onto its image f[G]. It is straightforward to show
that f[G] is a subgroup of Perm[G]. Thus f induces an isomorphism
between G and f[G].
Right and Left Regular
Representations
• ρx(g) = g x
as in the theorem defined the left
regular representation f of G.
• Multiplication on the right gives the property that is
not homomorphism: μx y = μy μx. This is sometimes
called the antihomomorphism property. The inverse
map reverses the order. So
• μx(g) = g x-1
defines a map that has the correct
order to be a homomorphism. This is called the right
regular representation f of G.
Examples
• Find the left and right representations of Z2 ,
Z 3 , Z4, S3
HW for Section 8
• Don’t hand in: pages 83-84: 1, 3, 5, 7, 9, 11, 13
• Hand in (Due, Tues, Oct 28): Page 84: 18