Transcript Math 3121 Lecture 9 ppt97

Math 3121
Abstract Algebra I
Lecture 9
Finish Section 10
Section 11
HW Due Today
• Hand in:
Due Tues, Oct 28:
Page 73: 12, 14, 16
Page 84: 18
Pages 94-95: 10, 24, 36
• Do not hand in:
Pages 94-95: 19, 39
Section 10
• Section 10: Cosets and the Theorem of
Lagrange
– Modular relations for a subgroup
– Definition: Coset
– Theorem of Lagrange: For finite groups, the order
of subgroup divides the order of the group.
– Theorem: For finite groups, the order of any
element divides the order of the group
Modulo a Subgroup
Definition: Let H be a subgroup of a group G. Define relations: ~L and ~R by:
x ~L y ⇔ x-1 y in H
x ~R y ⇔ x y-1 in H
We will show that ~L and ~R are equivalence relations on G.
We call ~L left modulo H.
We call ~R right modulo H.
• Note:
x ~L y
x ~R y
⇔ x-1 y = h, for some h in H
⇔ y = x h, for some h in H
⇔ x y-1 = h, for some h in H
⇔ x = h y, for some h in H
Modulo a Subgroup is an
Equivalence Relation
Theorem: Let H be a subgroup of a group G. The relations: ~L and ~R defined by:
x ~L y ⇔ x-1 y in H
x ~R y ⇔ x y-1 in H
are equivalence relations on G.
Proof: We show the three properties for equivalence relations:
1) Reflexive: x-1 x = e is in H. Thus x ~L x.
2) Symmetric: x ~L y ⇒x-1 y in H
⇒ (x-1 y) -1 in H
⇒ y-1 x in H
⇒ y ~L x
3) Transitive: x ~L y and y ~L z ⇒ x-1 y in H and y-1 z in H
⇒ (x-1 y )( y-1 z) in H
⇒ (x-1 z) in H
⇒ x ~L z
Similarly, for x ~R y .
Cosets
• The equivalence classes for these equivalence relations are
called left and right cosets modulo the subgroup.
Recall: x ~L y
⇔ x-1 y = h, for some h in H
⇔ y = x h, for some h in H
• Cosets are defined as follows
Definition: Let H be a subgroup of a group G.
The subset
a H = { a h | h in H }
is called the left coset of H containing a, and the subset
H a= { a h | h in H }
is called the right coset of H containing a.
Examples
• Cosets of nℤ in ℤ are:
nℤ, nℤ+1, nℤ+2, …, nℤ + (n-1)
• For example 2ℤ in ℤ has two cosets.
• Cosets of {0, 3} in ℤ6
• Cosets of {0, 2, 4} in ℤ6
Abelian versus Nonabelian
• Note: In abelian groups the left cosets are the right
cosets. In nonabelian case: left and right don’t
always agree.
• H = {e, μ1} in G = S3 has different left and right cosets.
For left cosets, make a multiplication table G×H. For
right cosets, make a multiplication table H×G. (See
slides after this one).
• H = {ρ0, ρ1, ρ2} in S3 has same left and right cosets.
Multiplication Table for S3
in Cycle Notation
e
(1 2 3)
(1 3 2)
(2 3)
(1 3)
(1 2)
e
e
(1 2 3)
( 13 2)
(2 3)
(1 3)
(1 2)
(1 2 3)
(1 2 3)
(1 3 2)
e
(1 2)
(2 3)
(1 3)
(1 3 2)
(1 3 2)
e
(1 2 3)
(1 3)
(1 2)
(2 3)
(2 3)
(2 3)
(1 3)
(1 2)
e
(1 2 3)
(1 3 2)
(1 3)
(1 3)
(1 2)
(2 3)
(1 3 2)
e
(1 2 3)
(1 2)
(1 2)
(2 3)
(1 3)
(1 2 3)
(1 3 2)
e
Left Cosets for S3
in Cycle Notation
e
(2 3)
e
e
(2 3)
(1 2 3)
(1 2 3)
(1 2)
(1 3 2)
(1 3 2)
(1 3)
(2 3)
(2 3)
e
(1 3)
(1 3)
(1 3 2)
(1 2)
(1 2)
(1 2 3)
Distinct left cosets of H = {e, (2 3)}
{e, (2 3)} = e H = (2 3) H
{(1 2 3), (1 2)} = (1 2 3) H = (1 2) H
{(1 3 2), (1 3)} = (1 3 2) H = (1 3) H
Right Cosets of <(2 3)> for S3
in Cycle Notation
e
(1 2 3)
(1 3 2)
(2 3)
(1 3)
(1 2)
e
e
(1 2 3)
( 13 2)
(2 3)
(1 3)
(1 2)
(2 3)
(2 3)
(1 3)
(1 2)
e
(1 2 3)
(1 3 2)
Distinct right cosets of H = {e, (2 3)}
{e, (2 3)} = H = H (2 3)
{(1 2 3), (1 3)} = H (1 2 3) = H (1 3)
{(1 3 2), (1 2)} = H (1 3 2) = H (1 2)
Counting Cosets
Theorem: For a given subgroup of a group, every coset has
exactly the same number of elements, namely the order of
the subgroup.
Proof: Let H be a subgroup of a group G. Recall the definitions of
the cosets: aH and Ha.
a H = { a h | h in H }
H a= { a h | h in H }
Define a map La from H to aH by the formula La(g) = a g. This is
1-1 and onto.
Define a map Ra from H to Ha by the formula Ra(g) = g a. This
is 1-1 and onto.
Lagrange
Theorem (Lagrange): Let H be a subgroup of a
finite group G. Then the order of H divides
the order of G.
Proof: Let n = number of left cosets of H, and let
m = the number of elements in H. Then m is
the number of elements in any left coset.
Thus n m = the number of elements of G.
Here m is the order of H, and n m is the order
of G.
Orders of Cycles
• The order of an element in a finite group is the
order of the cyclic group it generates. Thus
the order of any element divides the order of
the group.
HW Section 10
• Don’t hand in:
– Pages 101: 3, 6, 9, 15
• Hand in Tues, Nov 4
– Pages 101-102: 6, 8, 10, 36, 40
Section 11 (as time permits)
• Direct Products and Finitely Generated
Abelian Groups
•
•
•
•
•
Cartesian Product of sets
Direct product of groups
Structure of ZnZm
Structure of products of cyclic groups
Next time: Structure of Finitely Generated Abelian
Groups
Cartesian Products
Definition: The Cartesian product of a finite
collection of sets Sk, for k = 1 to n is the set of
all n-tuples (s1, s2, …, sn), with sk in Sk. The
Cartesian product is denoted by
S1 ×S2 × … ×Sn
or by product notations such as
k
k 1, n
S

Projection Maps
• The map pi: S1 ×S2 × … ×Sn  Si that takes the
n-tuple s = (s1, s2, …, sn) to its ith component si
is called the ith projection map.
• In other words: For any s in S1 ×S2 × … ×Sn the
result of applying the ith projection map to s is
called the ith component of s and denoted by
si .
• Note: Two elements a and b of the product
are equal if and only if ai = bi, for all i = 1,…,n.
Direct Product of Groups
Theorem: Let G1, G2, …, Gn be groups with multiplicative
notation. Define a binary operation on the Cartesian product
G1×G2×… ×Gn by (a1, a2, …, an)(b1, b2, …, bn) = (a1 b1, a2 b2, …, an
bn), then G1×G2×… ×Gn is a group with this binary operation.
The set G1×G2×… ×Gn with this binary operation is called the
direct product of the groups G1, G2, …, Gn.
Proof: Note that the binary operation is defined componentwise. That is, if a and b are in the product, then (a b)i = ai bi.
1) Associativity follows because each component binary
operation is associative. 2) The identity is e the n-tuple e = (e1,
e2, …, en), where each ei is the identity of its own component
group Gi. 3) For each a = (a1, a2, …, an) in the product, the ntuple a-1 = ((a1)-1, (a2)-1, …, (an)-1) is the inverse of a.
Direct Sums of Groups
• Sometimes we call the direct product a direct sum,
especially if we use additive notation.
• A direct product is characterized by its projection
maps. These turn out to be homomorphisms.
• On the other hand, the direct sum is characterized by
injection maps ji: Gi  G1×G2×… ×Gn that each take ai
in Gi to the n-tuple (e1, e2, …, ai, …, en) that has
identities in all components except for the ith, which
has ai. These also turn out to be homomorphisms.
Examples
•
•
•
•
•
•
ℤ2×ℤ3
ℤ3×ℤ5
ℤ2×ℤ2
ℤ3×ℤ3
ℤ2×ℤ6
ℤ9×ℤ6
Internal Products
• Each component group of a direct product can
also be considered a subgroup by injection.
All of these subgroups commute with each
other. Thus any element g of the product
G1×G2×… ×Gn can be uniquely written in the
form g = g1 g2 … gn with gi in Gi. When this
happens, G is said to be an internal product of
the subgroups Gi.
LCM and GCD of two numbers
• Let x and y be integers, then
• LCM(x, y) is the least multiple of x and y:
LCM(x, y) = min{ m in ℤ+ | m is a multiple of x and m
is a multiple of y}
• GCD(x, y) is the greatest common divisor of x
and y:
GCD(x, y) = max{ m in ℤ+ | m divides x and m divides
y}
• LCM(x, y) = x y /GCD(x, y).
Methods of finding LCM and GCD
• Euclidean Algorithm to find GCD in the form a
x + b y: Start with positive integers x and y.
Set r0 = x, r1 = y. Given rk-1 and rk, find qk and
rk+1 such that: rk-1 = qk rk + rk+1, with 0 ≤ rk+1 <
rk. Continue until rk+1 = 0. Then GCD(x, y) = rk.
Then work backward to write GCD in the form
a x + b y.
• Example: Find GCD of 64 and 58.
• For small numbers use prime factorization.