New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Adam Crona


Adam Crona
GPA 3.73

N. Donaldson

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

N. Donaldson
Class Notes
25 ?




Popular in Course

Popular in Mathematics (M)

This 48 page Class Notes was uploaded by Adam Crona on Saturday September 12, 2015. The Class Notes belongs to Math 120 at University of California - Irvine taught by N. Donaldson in Fall. Since its upload, it has received 15 views. For similar materials see /class/201863/math-120-university-of-california-irvine in Mathematics (M) at University of California - Irvine.

Similar to Math 120 at UCI

Popular in Mathematics (M)




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/12/15
Math 120A An Introduction to Group Theory Neil Donaldson Spring 2009 Text 0 An Introduction to Abstract Algebra John Fraleigh 7th Ed 2003 Adison Wesley optional 0 Also check the library for entries under quotGroup Theoryquot and Abstract Algebra There have been a plethora of textbooks written for Undergraduate group theory courses and the first few chapters of most of them will cover similar ground to the core text 1 Introduction Alongside discussions of Continuity and abstract Calculus Group Theory is usually the first serious taste an Undergraduate gets of Pure mathematics It introduces the idea of axiomatic mathematics a collection of rules and definitions are given and we prove theorems entirely derived from those rules As a result group theory can seem daunting and difficult to the uninitiated Perseverance is the key Usually proofs are not as difficult as they first seem there are relatively few rules governing groups so there is often little choice in how you approach a proof Why study Groups Here are two possible answers Firstly groups are incredibly useful Groups are largely about sym metries and patterns and much of mathematics involves looking for these For example a square has symmetries rotations and re ections these symmetries form a group Here are some further examples of where groups play a role Geometry A large part of modern Geometry involves the study of groups surfaces polyhedra the set of lines in a vector space these sets have many different groups associated to them which help the geometer describe and classify them Combinatorics When studying collections of objects groups of permutations reorderings of sets are widely used Galois Theory Groups describe the roots of polynomial equations Chemistry Groups are used to describe the symmetries of molecules and of crystalline substances Physics Materials science sees group theory in a similar way to Chemistry while modern theories of the nature of the Universe eg string theory rely heavily on groups The second reason to study groups is that they are relatively easy yes really A group is a set with just one operation like the real numbers lR with you are already familiar with objects far more complicated than this eg lR with two operations is a field an is a vector space so it makes sense to begin the study of abstract mathematics at the level of groups Motivational example What do an equilateral triangle and an arbitrary collection 1 2 3 of 3 objects have in common Not much at first glance but both objects have symmetries rotations and re ections of the triangle and permutations of 123 In fact these symmetries are the some The permutations of 123 can be written in cycle notation eg 12 swaps 1 and 2 and leaves 3 alone 123 sends 1 to 2 2 to 3 and 3 to 1 There are 6 permutations Identity Swap 2 Move all3 e 1 23 p1 123 2 13 P2 132 43 12 The permutations interact by composition For instance p1 opz 23132 12 p3 The full list of compositions of the symmetries is shown below left column first then top 8 8 43 3 1 2 p1 pz 8 M1 1 2 2 Now label the vertices of an equilateral triangle 123 The above permutations correspond to symmetries of the triangle phpz are rotations counter clock and clockwise while p is re ection in the altitude through the point i The two sets of symmetries are the same Group theory is about ideas like the above the symmetries and patterns associated to an ob ject are often more important and interesting than the object itself and can lead to unexpected con nections In group notation we have shown that the symmetric group on 3 letters 53 permutations of 123 and the Dihedrol group of order 6 D3 the symmetries of the triangle are isomorphic1 53 E D3 The following sections roughly resemble their counterparts in Fraleigh s book We will sometimes use different notation however eg Fraleigh calls a set S in a definition while we use X Don t let this fox you problems in the exam and in later life are unlikely to use precisely the same notation so make sure you learn the corlcepts rather than photographically memorizing the definitions 1We will explain both examples more fully later and terms such as isomorphic At the moment it is enough to say that isomorphic means the same in a specific way 2 Binary relations De nition 21 A binary relation on a set X is a map X x X a X which is de nedfar all pairs of elements in X We say that X is Closed under Examples 1 Usual multiplication and addition are binary relations on any of the sets R C Q Z lRJ 12 2 and many more The sets R Q C Z with subtraction Any vector space eg Rquot or Cquot has the usual as a binary relation pmm R3 with cross vector product gtlt functions V gt V where V is any space and gtk o composition of functions C with the Hermitian product 2 w 2 8 lN 2 with the least common multiple eg 4 5 20 9 N with the highest common prime factor eg 65 20 5 O The set A 0 123 with a b ab mod 4 ie the remainder upon dividing ab by 4 Remarks There is no requirement for a binary relation on X to have an image that is all of X ie X X need not be all of X see example 8 where a b is always prime The only thing that matters is that the relation is defined everywhere The following is therefore NOT an example Q with pmb ab a 0 is undefined for all a Binary relations on finite sets can be written in multiplication tables Example 9 above can be written where we find a b by taking a in the left column and I along the top WNH096 ooooo WNHOH NONON HNWOU De nition 22 If Y C X is a proper subset and X has a binary relation then we can restrict to Y If Y gtk Y C Y we say that Y is Closed under Otherwise said restricted to Y is a binary relation on Y Examples 1 The negative integers Z are closed under but not under 2 Let Y C Z be the set of integers whose remainder is 1 when divided by 3 ie Y 1 3n n E Z 1471013 72 75 78 ls Y closed under Or Under 1 3n 1 3m 2 3m n has remainder 2 so Y is not closed Under 1 371 1 3m 1 371 3m 9mn 1 3m n 31ml has remainder 1 so Y is closed De nition 23 A binary relation on X is associative if a b c a b c Va b c E X If is associative then the writing a1 a2 an is unambiguous Examples 135789 in the first list in this section are associative De nition 24 A binary relation is commutative on X if a b b a Va b E X Original examples 13789 are commutative Remarks Some algebraists will use for any commutative binary relation While this reminds us of the common addition of numbers which is commutative it can be confusing do not assume that every time you see a in a book that it means addition Observe that the multiplication table of a commutative binary relation has a diagonal symmetry For example our earlier table is symmetric about the principal diagonal Conversely non commutative relations have non symmetric tables 0 l 2 3 a b c d 0 0 0 0 0 a d c d c l 0 l 2 3 b a b a d 2 0 2 0 2 c a c a b 21 3 0 3 2 l d c c a c A commutative relation ex 9 A non commutative relation Observe that the second table is not associative for a b c c c a while a b c a a 01 There are two important examples that it is worth proving the associativity and non commutativity of functions with composition and matrix multiplication Note the similarity of the two proofs Proposition 25 Composition of functions f g V a V is associative where V is any set If V has at least 2 elements V 2 2 then composition is nonicommutative Proof For the first claim we must see that fog ohx f0 go hx VX E V Now fog 01006 foghx fghx and f0 gohx fg0hx fghx Thus 0 is associative To see that o is non commutative we have to exhibit a counter example for any V with at least two elements Leta 7 b be two elements in V and define fg V gt be a gx b VX E V Then f0g2Xgt gtfb g0f2Xl gtg b o is therefore non commutative I Remarks You may think it is enough to choose a specific space say V lR in which to exhibit a counter example but the proof really requires the abstractness It may amuse you to construct pairs of non commuting functions f g lR gt lR There are many large sets of functions that do commute for example in a vector space V the set of scalings fA V gt V X gt gt AX where A E lR form a commuting set Composition of functions between arbitrary sets is actually associative the proof is almost identical but composition only gives a binary relation when maps are from a set to itself Corollary 26 Matrix multiplication of square matrices is associative Proof We will provide three proofs of this fact choose your favourite Using Proposition 25 You may have proved in a linear algebra course that matrix multiplication corresponds to linear transformations of a vector space ie square matrices can be viewed as functions V gt V and multiplication is composition of functions Armed with this knowledge Proposition 25 gives the result straightaway Directly Suppose that A B C are rl gtlt rl matrices Recall that if A has entries aij ith row jth column etc then AB has ikth entry rt ABik Z lyl jk j1 Therefore ABCa lt2m agt Ck Zigwa39bjk kt J r Similarly ABC39 2a El jka Z ijbjkckl f k M These are equal by the associativity of lR For Physicists If you are lucky enough to understand the Einstein Summation Convention observe that the direct proof can be written ABC ijbjk kl ijbjk kl ABC where we have used associativity of multiplication of real complex numbers for the middle ste p I Matrix multiplication is similarly non commutative for example A 3 1 and B 1 3 don t commute We will often ignore associativity and just assume it is true As you can see above it often involves a messy calculation We will certainly never prove associativity for functional composition again any time an example appears we will quote Proposition 25 Make sure you remember what associativity means and that it holds for functions Many binary operations that are not obviously functional composition can be viewed as such when thought about in the correct way so Proposition 25 is extremely useful 3 Morphisms A morphism is simply a function from one set to another often a morphism has a prefix such as homo or iso Recall the following definitions from previous classes De nition 31 Let X Y be sets A function or morphism f X gt Y is said to be 171 iffx fy i x yforallxy E X onto iffX Y Otherwise said f is 1 1 iff each element in the image of f comes from exactly one element of X f is onto iff everything in Y is in the image of f f is a bijectian if it is both 1 1 and onto De nition 32 Let XY be sets with binary relations X y A map 4 X a Y is a homomorphism2 of binary structures ifzpa X b 4101 y 111k Va E X A homomorphism pulls back the structure on Y the binary relation to that on X De nition 33 Ahomomorphism 4 X X a Y y is an isomorphism3 if 4 X a Y is 1 1 and onto We write X E Y or occasionally 4 X E Y 4 X gtY or X g Y Some books eg Fraleigh use X 2 Y Remarks Recall the motivational example where we discussed the symmetries of the equilateral triangle D3 and the permutations of 123 With both sets of transformations labelled the way they are we have an isomorphism 53 E D3 with binary operation of composition on each side Synonyms A 1 1 map is often referred to by the noun injection and adjective injective An onto map is surjective or a surjectian A map that is both 1 1 and onto is a bijectian or a bijective map An isomorphism is therefore a bijective homomorphism We will use bijection but none of the others All are in common usage however so you should be aware of them Remark Given a bijection 4 X gt Y and a binary relation on Y you can always define a relation 9 on X by pulling back to X x1322 zp 1zpx 4X V393 E X Example The map 4 lRJr gt lRJr X gt gt X2 is a bijection Suppose we want 4 to be an isomorphism 4 lRJr gt lRJr Then we must define by x y 4f1lt4gtltxgt w 41408 y2 ixz y2 ZThe prefix homo means similar 3 lso means same Showing Isomorphicity When asked to demonstrate that two structures are isomorphic eg that X E Y you should follow the steps given below 0 Define a function 4 X gt Y 0 Check that 4 is a homomorphism 41X y 1X 1 My 0 Check 4 is 1 14X y x y 0 Check 4 is onto Vz E Y 3X E X such thatz You can perform the final three steps in any order you like but it is often easiest to check the ho momorphism property first as part of the definition This is since you will usually have the homo morphism property at the back of your mind when trying to define 4 in general there are a huge number of functions X gt Y so you need some inspiration in order to pick the right one Sometimes of course the homomorphism property is the hardest one to check Remark Another method to show isomorphisms of finite sets is to write out the multiplication ta bles for each binary relation and compare this is not easy as you will probably have to relabel the elements and swap rows and columns in order to get the two tables to look alike Two tables that look different are not automatically non isomorphic Examples 1 22 E 32 with the binary relation of addition For n E 2 712 nz z E 2 is the set of integers divisible by De ne 4 Let 4 22 a 32 Zm gt gt 3m ie 41x gx Homomorphism 41X y X y gx y 4100 y and so 4 is ahomomorphism 11 4100 470 s x g1 xx ysozpis1 1 Onto An arbitrary element of 32 is y 3m where m E 2 But 3m 412m so 4 is onto 4 is therefore an isomorphism 4 22 E 32 2 22 E 32 with respect to the binary relations x ZZ y xy on 22 and x 32 y xy on 32 and 1X gx 4 is 1 1 and onto by example 1 and is a homomorphism because 412x ZZ 2y 412xy 3xy 3x 32 3y 412x 32 412y 011 E SH Onthe LHS 01 x E R 0 g x lt 1 and x1y Lxyj fractional part of X y ie 03 1 09 L12 02 On the RHS S1 is the unit circle in the complex plane S1 z E C z 1 and is standard multiplication of complex numbers Recall that 2 w 2 MI for any complex numbers 2 w and so is a binary relation on 51 9 4 Z I 51 I I a 42 1 I I i VV I lt15 I O Geometrically we are stretching and then wrapping the interval 01 around the unit circle with thejoin at 1 E C De ne 4 Let 4 01 gt S1 X gt gt 82mquot recall that 82 quot COS27 L39X isin27IX which has modulus cos2 sin2 1 1 1 41X 41y i 82 quot 82 i 82quotix y1 i X E y E Z But Xy E 01so we must have X y 4 is therefore 1 1 Onto An arbitrary element of S1 is z 819 where 0 g 6 lt 27139 is the argument of 2 But 819 ez li39 Now E 01 and so 4 is onto Homomorph X1y LXyD 82nixyj 82nixy 82nix82m39y X 4 y and so 4 is a homomorphism Remember that 82 quot 1 for rl E Z so EMMHW EZMHW Showing nonisomorphicity This is tricky in general you can t try every map X gt Y except for very small sets X Y in order to check that there are no isomorphisms so you have to be a little more cunning and consider various properties that are preserved by isomorphism De nition 34 A structural property of X is a property which is preserved under isomorphisms ie if 4 X gtk gt Y is an isomorphism then X and Y 9K have the same structural proper ties The following are examples of structural properties suppose 4 X gt Y is an isomor phism throughout 0 The elements of X Y are in a pairing X and so the size cardinality of the sets must be the same this is true even for infinite sets 2 Q N0 g 2 lR there are therefore no isomorphisms between Q and lR no matter what binary relations you have 0 Any special elements in X must correspond to special elements in Y eg idempotents if X X X in X then under an isomorphism we must have 41X 9quot 41X 41X in Y Thus if idempotents exist in X but don t in Y there can be no isomorphism o Commutativity amp Associativity If X or Y has one of these properties then so must the other A set with a commutative or associative relation is never isomorphic to a set with a non commutative or non associative relation 0 Identity if X has an identity element 8 e X X e X VX E X then under an isomor phism 4 Y has an identity 418 0 Solutions of equations if a X b has a solution X E X then in the presence of an isomor phism a similar equation must have a solution in Y This example is important and tricky to know when to use There are a couple of examples of this in action below There are many other things that must be preserved by an isomorphism far too many to list The more structure a set and its binary operators get the more properties there are to consider Disprov ing isomorphisms is somewhat of an Art as you will sometimes have to think very hard or have a ash of inspiration in order to think of the correct structural property Note that there are many concepts that are not necessarily preserved by an isomorphism the type of element a number a matrix etc the type of binary operation in the 01 1 E 51 we saw that addition can become multiplication under an isomorphism Again there are others en gage your brain when asking yourself if something is a structural property is the property eXtrinsic depends on how you write down the set and the binary relation or intrinsic independent of how you write things down A loose definition of two binary structures being isomorphic is exactly that one is a relabelling of the other Examples 1 The two binary relations defined by the multiplication tables in 21 are non isomorphic because the first is commutative while the second is not N lR3 SE lR3 gtlt cross product because is commutative and associative while X is nei ther U N0 SE N since lNo contains the additive identity 0 while lN does not Q Recall the 01 S1 example from earlier 01 1 SE lR One reason is because there are two solutions to X 1 X 0 in 01 namely X 0 while there is only one solution to the corresponding equation y y c in lR for any c if 4 01 gt lR was an isomorphism then X 1 X 0 w 41X 41X 410 which is an equation of the form y y c Actually you could assume that c 0 because 0 is the additive identity on both sides U I Q SE Q since yz 2 has no solution in Q but the corresponding equation X X c has a solution in Q for any c 4 Groups De nition 41 A Group is a set G together with an operation G X G gt G which together satisfy the following axioms Closure G is closed under ie is a binary relation on G Associativity is associative Identity 3 identity e E G such that e g g e g Vg E G Inverse Every element has an inverse Vg E G Eg l E G such thatg g 1 g l g e De nition 42 A group G is Abelian if the group operation is commutative4 Remarks You should remember the axioms in the order they are written down so that when you are asked to prove that something is a group you can deal with one property after another Examples of this are given below Although a group is often written as a pair G it is conventional to drop the operation symbol and refer to the group G if there is no ambiguity about the operation Be careful though for sometimes the is needed dropping when multiplying real numbers creates nonsense 3 4 12 becomes the 4After Niels Abel one of the Godfathers of pure mathematics meaningless 34 12 For Abelian groups the operation is often denoted even when it does not denote an addition In such cases we use minus 7 for the inverse Examples 1 Sets such as lRZ Q rl E Z rl even are Abelian groups under addition Check All are closed by assumption Addition is associative 0 is the additive identity 0 rl rl 0 rl The inverse 0er is in E Z N The non zero elements in lR C Q form Abelian groups under multiplication Check Closure ub 7E 0 i uh 7E 0 Multiplication of numbers is associative 1 E Q C lR C C is the multiplicative identity 1 rl rl 1 rl The inverse of rl is rl 1 1 rl which is in lRC Q if rl is These groups are often denoted lRgtltCXQgtlt or lRCQ etc The has a separate meaning recall linear algebra where lR is the alqu space to lR the set of linear maps lR gt lR so in this class we will always use the X notation U Vector spaces any vector space is an Abelian group under addition Note that this includes the set of m X rl matrices under addition as menlR lRm gtlt lRquot g Let P be a regular rl gon Then P has symmetries rotations and re ections The set of symme tries forms a non Abelian group under composition These are the Dihedrul Groups Dn which we will think more in section 9 U1 Permutation groups the symmetric group 5 is the group of rearrangements of the set 1 2 rl for example the element 12 which swaps 1 and 2 is in Sn These groups will also be studied in section 9 O Matrix groups We will later discuss several examples of groups of matrices under multiplicui tiarl Some you will have thought about before like the Orthogonal Group Orl of transfor mations of lRquot which preserve lengths and angles between vectors We have seen the messy calculation that matrix multiplication is associative so the issue with matrix groups is to see that inverses exist and that the set is Closed The matrix with 1 s down its diagonal and 0 s every where else is the multiplicative iderltity matrix and often written In or just I There are many more groups than just these but we shall mostly use the above and subsets of the above as our examples Things that are not groups There are a number of things that can go wrong when trying to make a set into a group even if you overcome the biggest hurdle and start with an associative operation Mostly people forget to check closure and inverses o The set of all real numbers lR as opposed to lRgtlt lR does not form a group under multiplication lR is closed associative and has the identity element 1 but the single element Ohasno inverse Er E leuch that0 r r 0 1 10 The same is true for the other multiplicative sets Q and C are not groups because of the non invertibility of 0 The set of functions f V gt V does not form a group under composition when V has at least two elements We have closure associativity Proposition 25 and an identity map f X gt gt X but in general we have no inverses For example the map f X constant VX E V has no inverse However if the space V is itself a group then the set of maps f X gt V from any set into V forms a group under the operation of V on values for example f X gt lRquot forms a group under addition on lRquot gX gX The set of functions f lR gt lR is not a group under multiplication Any function f which has a 1 zero at any point X has no inverse for m is undefined Remarks A multiplicative group is a group where the operation is written multiplicatively g li gh This is the most common form of notation because we can be maximally lazy in our writing The adjective multiplicative is dangerous however as it doesn t refer to any intrinsic property of the group only in how we write it down Notational laziness goes further for we will often use shorthands uquot Q u and ifquot u 1quot uquot 1 Exponents follow the usual additive law unum WMquot We w mimes also write uo 8 Basic theorems for groups Theorem 43 In it group G identities and inverses are unique Proof Assume 8 7E r are identities Then viewing 8 as an identity we have 8 6 while viewing r as an identity yields 8 8 Therefore 8 r and we have a contradiction Similarly let ghave inverses hl 7E hz Then ghl gh2 8 Thus Mghl h1gh2 li1gh1 h1gl12 by associativity gt8l11 ehz since h is an inverse of g gtl11 hz Again we have a contradiction I Observe that we could have used either hl or hz as the inverse of choice in the second part of the proof Corollary 44 Cancellation laws amp lnverses u ggl ggz i g1 g2 l1 gig gzg i 31 g2 C ghf1 h lg l Proof The first two statements are immediate just multiply on the left resp right by g l For part c note that h lg 1gli h 1g 1gh h leh h lh 8 Thus h lg l is an inverse of gh But inverses are unique by Theorem 43 11 De nition 45 Two groups G H are isomorphic if the group operations on the sets G H are isomor phic binary structures We write G E H Written multiplicatively G E H ltgt 34 G gt H such that 4 is 1 1 and onto and a homomor phism 41glg2 41g14gtg2 Group tables for nite groups Just as for binary relations on finite sets it can be useful to write a group in a multiplication table There are a few rules for group tables however which do not apply to general binary relations In the row and column of the identity e everything remains unchanged You can always start by writing down a group table with the first row and column filled out abc abc w m9 mw mm Lemma 46 Magic square lemma In every row and column each element appears exactly once Proof Suppose element X appears twice in row a Then 31 7E c such that X ab ac But Corollary 44 implies l1 c a contradiction Considering column a is similar Since no element can appear twice we must have all elements appearing exactly once I Any table satisfying the identity and magic square rules defines a binary relation with identity and unique inverses ie the Closure Identity amp Inverse axioms are satisfied The only thing left to check is associativity Unfortunately this is a messy business to see directly from the table and diminishes the use of tables as a good method of defining groups Moreover it is common for people to fail to spot when two tables are isomorphic when the two are identical up to a relabelling of the group elements For larger groups this can be very difficult to spot and you may therefore think that two tables which describe the same group actually describe different groups Group tables for low order groups De nition 47 The order of a group G is the number of elements in G Order 1 in Only 1 group 21 W gtllt 8 J Order 2 g Only 1 group 22 a a m Order 3 Group 23 NWW w mm mw What are 21 2223 Theorem 48 The set 2 012 n 7 1 E Z is un Abeliun group under addition modulo n u 7 I z u b mod We call Zn 11 the cyclic group of order n Proof Let s check the axioms Closure u h mod n E 2 is clear as 2 is the set of all remainders modulo n Associativity u 7 I n c u b n c u b c mod This is symmetric in ubc and therefore n is associative Identity 0 E 2 is the additive identity Inverse 7u E n 7 u mod Thus n 7 u is the inverse of u Zn is therefore a group is moreover commutative since is and so 2 is Abelian Corollary 49 There exists it group of every finite order Le for every positive integer n E 2 there exists at least on group with n elements namely 2 For most orders there are u lot more than just one group 5 Subgroups De nition 51 Let G be a group and H C G a subset H is a subgroup of G if H is a group in its own right A proper subgroup is a subgroup H 7 G e is the trivial subgroup of G for any G All other subgroups are non7triviul We write H g G or H lt G if we want to stress that H is a proper subgroup The very compact definition of subgroup contains several points In particular if H is a subgroup of G then the following are true 0 H C G as sets 0 The operation on G restricts to a binary operation on H H is closed under o The identity e E G is in H o H is closed under inverses h 1 E H Vh E H A priori we only have that h 1 E G for h E H so this really is a condition Examples 1 Z lt Q lt R lt C 2 QX lt lRX lt CX 3 e g Gand G g Gforuny G 4 Rquot lt Cquot 5 Rquot g lRm ifm g rt 6 Zm g 2 if mlrl proof to come later section 7 Sm g 5 if m g rl permutation groups section 9 8 Dm g Dn if mlrl Dihedral groups section 9 9 Sl lt CX recall S1 z E C lzl 1 is the unit circle 10 ClR lt C1lR all differentiable functions are continuous You don t have to check all the axioms of a group to see that a subset is a subgroup indeed you have to check very little as the following two results make clear Don t make the mistake of thinking that Proposition 53 is as useful as it first appears calculating xy l is often more difficult than proving things directly Theorem 52 A subset H of G is u subgroup if H is Closed under the group operutiorl urld inverses Proof If H is closed under the group operation on G and inverses then H satisfies the closure and inverse axioms of a group Moreover we now have that hh l E H for all Ii E H since inverses and products are in H and so the identity 8G is in H Finally H is associative because the group operation is already associative on G and H is just a subset of G H is therefore a subgroup I You should remember the Proposition when showing that a subset is a subgroup it is not required to check the associativity and identity axioms A good exercise is to show directly that examples 1 to 5 on the previous page are subgroups using the Theorem it is very quick Proposition 53 H C G is u subgroup i xy 1 E H Vxy E H Proof i is straightforward since H is a group For we first let X E H But then xx l e E H so that H contains the identity We therefore have ey l y 1 E H Vy E H so that H is closed under inverses Finally xy xy 1 1 E H and so H is closed under products Since the operation restricted to H is automatically associative because it is associative on G we have that H is a group and therefore a subgroup I Subgroups of low order groups Recall the groups 21 2223 under modulo addition It is straightforward to check that the only sub groups these groups have are the identity group 8 E 21 and themselves They are not therefore very interesting groups Only when we reach order 4 do interesting things start to happen It is an exercise to see that the only two groups of order 4 have tables as follows e u b C e u b C e e u b C e e u b C u u b C e u u e C b b b C e u b b C e u C C e u b C C b u e The cycl c group Z4 The llein 4 group V The Klein 4 group can be viewed as the symmetries of a regular rhombus choose one of a b C to be rotation through 180 degrees and the remaining two to be the two re ections across diagonals of the rhombus a D b Observe that V S Z4 since the equation X2 8 has 4 solutions in V while having only 2 solutions in Z4 recall that the existence of solutions to such an equation are a structural property of a group if V and Z4 were isomorphic then both must have the same number of solutions There are many other reasons why V S Z4 but this is one of simplest to exhibit Observe that Z4 has three subgroups Z4 024 E Z2 0 E Z1 02 is a subgroup because 2 4 2 0 E 02 and 2 is its own inverse Note that if we try to make a subgroup out of say 03 then we see that 3 4 3 2 8 03 and so we don t have closure V by contrast has five subgroups V 8 a 8 b 8 C 8 E Z1 the middle three are isomor phic to Z2 Each two element set is a subgroup because all elements of V are their own inverse Conversely if we tried to make a group out of 8 b then we get ab C e 8 b so 8 ab is not closed and not a group Subgroup diagrams We can draw subgroup relations This can be useful in analysing the structure of a group because it makes it extremely easy to see the differences between groups A line in a diagram means that the lower group is a subgroup of the upper 21 22 23 Z4 02 EZZ 8 8b 8C 0 0 0 e 6 Matrix groups We have seen that the groups GLnlR GLnC of matrices with non zero determinant are groups under multiplication There are lots of subgroups of these all of which have some geometric signifi cance 5Most of these groups are for your information only you won t be expected to remember anything about any matrix groups other than GLnlR SLnlR and OnlR for any exam Special linear group 5L 1R A E M7101 detA l the set of determinant 1 matrices forms the special linear group Recall the relation detAB detA detB This says that the product of two determinant 1 matrices also has determinant l and so SLnOR is closed under multiplication Since detA 1 1 detA we also have that inverses have determinant 1 SLnOR is therefore a group as claimed The geometry of SI 1R comes from the fact that an element of determinant l preserves volumes Recall that the signed area 2 dimensional volume of a parallelogram in R2 spanned by vectors uv is Allv u M sin 0W where 0W is the angle between the vectors6 It is an easy calculation to see that if A is a matrix then the signed area of the parallelogram spanned by Au Av is AreaAuAv detA u M sin 0W detAAreauv The area therefore scales by the determinant We can play the same game in R3 Here the signed volume of the parallelepiped spanned by u vw is the triple scalar product uvw Again check that AuAvAw detAuvw VA E M3lR SL3R is therefore the set of signed volume preserving transformations Volumes of parallelepipeds That determinants are related to volume should not be a total surprise if you remember integra tion in several variable calculus you should recall that changing the variables of integration requires you to insert a factor of the determinant of the Iacobian of the transformation into the integral The Orthogonal group The orthogonal group is the set of matrices 01011 A e MnOR ATA In where In is the n X 71 identity matrix diagl 1 By Theorem 7 we need only check that AB 1 ABT E OnlR for A B orthogonal But ABTTABT BTTATABT BET 1 since B 1 BT 0101 is therefore a subgroup of GLn To see the geometry of OnlR recall the standard inner product of vectors on Rquot uv uTv Observe that AuAv AuTAv uTATAv uTv uv 6This is almost the norm of the cross product if the plane R2 is embedded in R3 16 Indeed an alternative definition of the orthogonal matrices is that they are exactly those which pre serve the inner product OnlR A E MnlR AuAv uvVuv E an 61 Theorem 61 OnR is the set of length and angle preserving linear transformations of R Proof Recall that the cosine of the angle between two vectors uv is related to the inner product by uv lul lvlcose Supposing that A E MnlR preserves the lengths of vectors and the angles between them we imme diately have that AuAv uv and so A E OnlR Conversely if A is orthogonal then lAul2 lulz and AuAv 7 uv PM PM T W cos QAUIAV cos Quiv Thus A preserves lengths and angles The Special orthogonal group SOnOR OnlR SLnlR is the subset of determinant 1 orthogonal matrices Taking determinants of ATA I gives detA detAT detA2 1 i detA i1 Thus SOnOR consists of exactly half the orthogonal group Example When n 2 the group SOZOR consists of the rotations around the origin det 1 while 020R is the set of re ections across lines through the origin det 71 Pseudoorthogonal groups The inner product Definition 61 of OnlR can be extended Suppose you put a different non positive definite inner product on lRquot for example 1 0 0 uvuT 0 71 0 v 0 0 71 on lR3 The group which preserves this inner product is the pseudo orthogonal group 01 2 This is not just abstract mathematical nonsense the study of relativity in Physics requires the Lorentz group O31 where the inner product on spacetime lR4 has 3 positive space directions and one negative time direction The Unitary group The unitary group is constructed similarly to the orthogonal group This time we take the Hermitian inner product on Cquot uv uv Tv Then Un A E GLnC ltAuAv uv The special unitary group SUn is the set of determinant 1 unitary matrices that is SUn Un SLnC Remark U1 51 is the unit circle in Cgtlt under multiplication U1 is the set of 1 X 1 complex matrices ie numbers 2 E C which satisfy 22 1 Thus lzl 1 i z E 51 Conversely all numbers on the circle have the form 819 for some 9 E 0271 from which we see that 819 819 8719819 1 A discrete matrix group Not all matrix groups must be continuous like the above The set SLMZ A E SLnlR all entries are integers is a group It is clearly a subset of SLnGR and it is easy to see that the product of two matrices with integer entries has integer entries so it remains to check inverses Recall from linear algebra the formula 1 71 7 T A MAM where adjA is the adjoint of A formed by taking positive and negative multiples of determinant minors of A Observe that if A E SLMZ then adj has integer entries and so therefore has its trans pose Since detA 1 it follows that the inverse not only has determinant 1 but has integer entries 51412 is therefore a group A subgroup diagram for matrix groups For reference the subgroup relations between the various groups are summarised in the following table The complex orthogonal groups are defined exactly as the real orthogonal groups just allow complex matrices with ATA I There are many many more matrix groups that we haven t men tioned Gum GL1R 0C 5Lc U 5L 112 0012 5002 5U sum 50010 7 Cyclic groups Cyclic groups are a very basic class of groups we have already seen some such as Zn 71 Theorem 48 Cyclic groups are relatively easy to work with since their structure is easy to describe The approach in this section is typical of pure mathematics in thatwe prove theorems based on an abstract definition before classifying what it is that we have just defined in this case all cyclic groups This approach may seem bizarre to the uninitiated but it has its logic Thusfar we have been deliberately relaxed about what a group is For example the definition in Theorem 48 of the cyclic group 2 as the set 01 n 7 1 under addition modulo n is not 18 strictly correct If this really was Zn then what would we call the group 0 2 4 2rl 7 1 under addition modulo 2n This new group has the same structure as Zn it is isomorphic so what should we do Which is the cyclic group of order r1 The answer is that both are the group itself is an abstract concept the above two descriptions are simply that they are ways of writing down the group The cyclic group of order rl knows nothing about numbers or sets it just is Any structure it has that is truly intrinsic that comes from the group and not from how we look at it should be discernable without making any choices on how to write it down7 De nition 71 Let G be a group written multiplicatively and X E G The cyclic subgroup of G generated by X is the subgroup X X11 rl E Z The order of an element X E G is the order X of the subgroup generated by X G is a cyclic group iff 3X E G such that G Remarks The groups Zm n and Z are cyclic Both are generated by the element 1 We shall see shortly that up to isomorphism these are the only cyclic groups However we do not need to know this to understand many things about cyclic groups Writing our cyclic groups multiplicatively rather than additively is good practice in thinking abstractly We now have two concepts of order The order of a group is the number of elements in that group while the order of an element is the number of elements in the cyclic group generated by that element It follows that cyclic groups are the only finite groups containing elements having the same order as that of the group Lemma 72 Suppose that G X has order r1 Therl Xk e ltgt k qufor some 11 E Z Proof Divide kby rl with remainder Thus k qr r where qr E Z and 0 g r lt rl Then 8 xk ertr X71qu X7 If r gt 0 this says that the order of X is at most r which is strictly less than rl a contradiction Hence r 0 and k qu l Lemma 73 Every cyclic group is Abeliurl Proof Let G Then any two elements of G can be written Xk X for some kl E Z But then xkxl Xkl Xlk Xlxkl and so G is Abelian I Theorem 74 All subgroups of u cyclic group are cyclic Proof Let G X and let H g G Let rl E ZJr be the smallest positive integer such that Xquot E H Claim H X71 For this let Xm E H be a general element of H But then we may divide m by rl so that there exist integers qr E Z 0 g r lt rl such that m qr r 7This is no different to the use of numbers do you think that 21 cares if it written 10101 or 25 or 15 binary octal or hex notation or in any of the many forms u 39 invented y 39 quot39 39 21 is a concept that transcends notation So it is with the cyclic group of order n Therefore xm 367quot x 7x7 E H But Xquot E H i Xquot 7 E H and so therefore x7 x 7xm E H i r 0 since 0 g r lt n and n E ZJr is smallest such that Xquot E H In summary xm Xquot 7 E Xquot and we are done I Theorem 75 All cyclic groups are isomorphic to one of Zn n or Z Proof Let G There are two possibilities either G n lt 00 or G has infinite order Treat the latter case first Case 1 G 2 N0 Define a map 4 G gt Z by 41Xquot n This is well defined because Xquot xm i JCan e i m n otherwise G would have finite order g m 7 We check that 4 is an isomorphism 1 1 41xm 41xquot i m n i xm xquot onto m 41xm Homomorphism 41xmxquot 410W m 71 41xm 41xquot 4 is therefore an isomorphism 4 G E Z Case 2 G n lt 00 Define a map 4 G gt Zn by 41Xm m mod Wellde ned xk x7 i xk e i k El qn for some 11 E Z by Lemma 72 But then wk W 1 41x 41x 7 i p E 11 mod n i x 7 x i onto 11 41x i Homomorphism 41067367 4106 p 11 mod n p 71 11 zpx 7nzpx 7 4 G E Zn is an isomorphism I The only real difference in the arguments for finite and infinite orders is the extra care that must be taken over well definition in the finite order case Wellde nition as a concept The concept of well definition appears in the above proof for the first time Essentially something is well defined if it makes sense Most times you have written down a function it is completely obvious that you really have defined a function for example f Z gt Z given by f z z2 7 3 is clearly a function However in abstract mathematics you are often asked to define a function from a set for which you haven t got a complete intuitive description For example we know that all the elements in the above cyclic group G X have the form xm for some integer in but it may be that the same element can be written in multiple ways for example X2 38quot 38 quot etc The map f G gt Z given by f Xm in when Xquot e is not well defined since the same element X2 38quot X244quot is mapped to multiple targets 22 712 271 You should get into the habit of checking well definition as the first step of any proof which requires you to construct a function The above example is easy to check but later examples will be less so It is often extremely easy to write down something that looks like a function but fails to be so Subgroups of cyclic groups Since subgroups of cyclic groups are cyclic we know that any H g Z has a generator rl Hence H rlZ Note that H E Z if rl 7E 0 and that by isomorphism it follows that the only non trivial subgroups of an infinite order cyclic group are isomorphic to the group itself8 Having completely described the subgroup of infinite cyclic groups we now consider finite cyclic groups Theorem 76 Let G x E Zn The subgroup of G gerleruted by the element y XS is isomorphic to Znd where d gcd51 l Proof We know that y is a cyclic group of finite order as it is a subgroup of G E Zn It is enough to check therefore that yk e ltgt k E 0 mod rld Clearly ifk 11 then yk 05 3 en i e since 3 E Z Conversely ykeExSkeExSke E sk am for some 0c E Z Lemma 72 s E ah 0c since 01 d1v1des srl E d 7 39 i E E k 0 mod rld s1nce gcd d d E 1 Therefore y E Znd Corollary 77 Zn has exactly one subgroup Z M for each divisor d of rt Proof Let d be a divisor of rl Then by the Theorem 01 E Znd Z d A gc r1 Conversely suppose that gcdurl d Then firstly u Ad for some A E Z so that u E d and so u g Secondly by the Euclidean Algorithm9 3A4 E Z such that Au url d and so Au E 01 mod Thus 01 E u and so at lt ii In conclusion if gcdurl 01 then ltagt on e 2m Remark The above Corollary can be phrased in terms of a general cyclic group of finite order If G X rl then the subgroups ltXjgt xkgt are the same iff gcdjrl gcdkrl Examples 1 Z8 0 123 4 5 67 is generated by 135 7 eg 5 52741630 28 The order10 of 6 is 4 8 gcd86 which is exactly what we see 6 6420 8This is a semmingly paradoxical property of infinite sets you can throw away half or more of the set and still have the same number of elements 939You don t need to know what this is for this class 10Recall Definition 71 for the order of an element 2 Find all the subgroups of 230 Note that 30 2 3 5 We list all the numbers in 230 their greatest common divisor with 30 and the subgroup generates recall that 230 has exactly one subgroup for each divisor of 30 Remember each subgroup in the right column is generated by any of the numbers in the left column X gcd30x 30 gcd30x subgroup generated 030 030 1 21 15 15 2 22 1020 10 3 23 6121824 6 5 Z5 525 6 26 392127 3 10 1210 24 81416222628 2 15 1215 17111317192329 1 30 1230 Here is the subgroup diagram for 230 with the obvious generator chosen for each subgroup 230 1 215 2 210 1 3 26 5 25 6 23 lt10 22 lt15 21 1 lt0 8 Generating sets De nition 81 If X C G is a subset of a group G then the subgroup of G generated by X is the subgroup of all combinations and inverses of elements in X G is nitely generated if there exists a finite subset X C G which generates G Remarks The subgroup of G generated by X really is a subgroup it is a subset so we need only check that it is closed under multiplication and inverses but the definition says that we keep throw ing things into the subgroup so that it satisfies precisely these conditions The notation for cyclic groups will be extended for generating sets le the subgroup of G generated by X will be denoted X E X Examples 1 Z 1 23 since the inverse of2 72 E 23 i 3 7 2 1 E 23 2 In general if mn E Z then the subgroup mn Am nn A44 E Z is d all where d gcdmn 3 Q 1 n n E 2 Q is not finitely generated there exists no finite subset which generates Q To see this suppose X piqi1 it is impossible to generate 11 from X if q is any number relatively prime to all the qi this argument is very similar to that of there being an infinite number of primes 9 Permutation groups De nition 91 A permutation of a set A is a bijection 4 A 7 A Theorem 92 The set of permutations S A of any set A forms it group under composition Proof Closure If p 1p are bijective then so is the composition p 0 1p Associativity Permutations are functions the composition of which we know is associative Propo sition 25 Identity ldA x gt gt X is a permutation Inverse If p is a permutation then it is a bijection and so p l exists and is also a bijection S A is therefore a group under composition De nition 93 The symmetric group on n7letters Sn is the group of permutations of 12 rl Proposition 94 Sn hus rt elements unlike Zn where the subscript is the order of the group Proof This is just counting If U E Sn then there are rl choices for the value of 71 Choosing one leaves rt 7 1 choices for 72 since 7 is a bijection lterating this argument we get 2 choices for 0rl 7 l and only 1 possibility for 7rl We therefore have rlrl 7 1 2 1 rt possibilities in total I Permutation groups are fundamental The following Theorem says that in fact all groups are permutation groups Sadly this result is not as useful as it might sound Theorem 95 Cayley s theorem Every group G is isomorphic to u group of permutations Proof Fix it E G and let p11 G 7 G be the map p11 x gt ux ie left multiplication by u Each p11 is a bijection lo1400 u lx and is therefore a permutation of G that is p11 E SG We claim that the set of all such maps under composition forms a group isomorphic to G M to E Go 2 Gly For this define the map 4 G 7 p11 by 1X px Observe that all the p11 are distinct p11 p1 i ux bx VX i u b and so 4 is 1 1 and therefore abijection Moreover 41W ny px Opy 41000 My since pxyz xyz pxyz pxpyz Therefore 4 is a homomorphism and being bijective is an isomorphism I Two notations Standard notation Suppose o E S4 is the following map 3 72 gt gt 1 2 3 4 4 2 We would then write 0 i 1 2 3 4 T 3 1 4 2 where you read columns to find where 7 maps an element Composition is read in the usual way for functions do the right permutation first Thus if 71234th 771234123471234 9 1432 en9 31421432 3241 Writing 7 as a map on the vector 123 4T suggests another method of writing Sn as matrices 0 07 1 T 0 H000 0H00 1 0 0 0 0 is a permutation matrix it swaps the entries of vectors An rl gtlt rl matrix with exactly one entry of 1 in each row and column and the remaining entries 0 is a permutation matrix the set of such forms a group under multiplication isomorphic to Sn Indeed we have proved Proposition 96 Everyfirlite group of permutations is isomorphic to u group of matrices Cyclic notation The above 7 can be more compactly written as o 1 3 4 2 We read from left to right looping back to 1 at the end the next entry telling us where the previous entry is mapped to by 7 Thus 1 3 4 2 maps 1gt gt3gt gt4gt gt2gt gt1 We have shorter cycles if some of the elements are fixed for example in our two notations 1 2 3 4 5 13lt3 2 1 4 5gtESS qutaposition is used for composition lt1342gtlt24gti i i G 13343234134 Remember that multiplication of cycles is really composition of functions thus although each cycle is read from left to right when determining how it acts on elements of 12 rl we multiply cycles by considering the rightmost cycle first For example 1354234 13254 24 is calculated by considering first that 1 is mapped to 3 by 234 followed by 1 354 Then 3 is mapped to 4 by 234 and then 4 is sent to 1 by 1 354 Hence the composition sends 1 to 3 and 3 to 1 yielding the 2 cycle 1 3 The remaining 3 cycle appears similarly It is not always possible to write an element as a single cycle eg the Klein 4 group V can be written in terms of cyclzes if we label the corners of a rhombus 1 D V e132 41324 4 De nition 97 A kecycle is an element a1 a2 wk E Sn k g 71 Two cycles a1 wk and b1 11 are disjoint if no element appears in both cycles11 1 k b1b Dihedral groups De nition 98 The nth Dihedral group Dn is the group of symmetries of the regular n gon regular polygon with n sides Group Now that we have defined permutation groups it is easy to see that the Dihedral groups are indeed groups doing this directly is much harder Observe that a symmetry can be viewed as a permutation of the corners of the n gon so that neighbourliness is preserved For example if we label the corners of the regular hexagon as 123456 then we see that D6 is the set of U E 56 such that 71 is always next to 76 and 72 etc Dn C 56 is a subset To see that D6 is a subgroup note that the composition of two neighbour preserving transforms also preserves neighbours as does the inverse of such a 5 6 map Elements of Du The regular n gon has 271 distinct symmetries and so Dn 271 These consist of n rotations Let p be rotation counter clockwise by radians where 0 n 7 1 n re ections Let y be re ection across the line making angle with the positive X axis make sure you put one of the corners of the n gon on the X axisl Remarks Some authors write D271 instead of Du precisely because Dn 271 we will always have Dn meaning the symmetries of the n gon Note that every Dn is a discrete finite subgroup of the orthogonal group 02lR of length and angle preserving matrices The correspondence is coslt2jgt isinlt27njgt coslt27 jgt sinlt27njgt 39 It is a good exercise to convince yourself that these matrices really do correspond to the rotations and re ections claimed In particular multiply any two of them together and see what you get 11Later we will say that their orbits are disjoint Examples D3 is the group of symmetries of the equilateral triangle See the introduction for the multiplication table Here we write all the elements in permutation notation and exhibit all the subgroups their generators and the subgroup diagram Element Standard notation Cyclic notation 5 1 2 3 a 90 1 2 3 8 o 1 2 3 14 3 41 2 3 1 123 1 quot396 m 1 2 3 p2 lt3 1 2 132 1 2 3 3 M a 1 lt1 3 2 23 p0 identity g 1 2 3 13 p1 rotate counter clockwise by 2713 1 2 3 2 1 p2 rotate clockw1seby 2713 Q 3 1 2 3 12 2 1 3 D3 23 22 22 22 N4 H D3 53 and D4 is the group of symmetries of the square otherwise known as the attic group D4 consists of 4 rotations and 4 re ections the notation 5f for re ection across a diagonal is used rather than calling all re ections m Element Standard notation Cyclic notation 1 2 3 4 8 9 1 2 3 4 m 1 2 3 4 5 pl lt2 3 4 1 1234 g 1 2 3 4 g pz 3 4 1 2 W24 1 2 3 4 p3 lt4 1 2 3 1432 1 2 3 4 141 2 1 4 3 lt12gtlt34gt p0 identity 2 42 1 2 3 4 1423 9 4 3 2 1 p1 rotate counter clockw1se by 712 395 m l 2 3 4 p2 rotate by 71 lg 51 1 4 3 2 24 p3 rotate clockwise by 712 m 6 1 2 3 4 13 2 3 2 1 4 26 D4 VZk 2222 my V D4 where i Subgroup relations 0 Sm g Sn ltgt m g n For example fix the final n E m elements of l n so that Sm oESnoi i Vigtrn In fact Sm is a subgroup of Sn in precisely different way each copy of Sm comes from fixing n E m elements of 1 n and there are ways of choosing these fixed elements C Dm g Dn ltgt Join every nrnth vertex of the regular n gon to get a regular m gon For example the diagram shows that every element of D8 which preserves the dashed square is a subgroup But this subgroup is D4 10 Aside Equivalence relations De nition 10 An equivalence relation on a set A is a binary condition12 which satisfies Re exivity x N x Symmetry x N y i y N x Transitivity x N y amp y N z i x N z The set x y E A y N x is the equivalence class ofx The set of equivalence classes is written A read A mod twiddles or tilde if you prefer We may therefore write X E X E A N This is not paradoxial X is an element of the equivalence class X which in turn is an element of the set of equivalence classes Theorem 102 An equivalence relation on A partitions A into distinct subsets Conversely if A Uid Ai is any partition Ai Aj if i 73 j where I is some possibly infinite indexing set then de ned on A such that x N y ltgt 3i E Isuch thatxy E A is an equivalence relation 12Either x N y x is related to y or x no y x is not related to y This is not a binary relation x N y is either true or false not an element of the set A Proof Suppose we are given an equivalence relation N Observe first that X N X i X E X so that every element is in some equivalence class Now suppose X N y We want to show that X We do this in two stages 1 Let a E Then a N X but by transitivity a N X amp X N y i a N y Therefore a E y and we have X C 2 Now let a E Thus a N y But now by symmetry we have y N X and so transitivity says ayampyX aXThusa E Xandsoy C Since X C y and y C X we conclude that X y and we re done The converse is straightforward X N y ltgt X y in the same Ai is obviously an equivalence relation with all three conditions being clear I 11 Orbits De nition 111 The orbit of o E 5 containingj E 12 n is the set OrbjW 0139 k E Z C 12n Remark Observe that orb7k0o orbjo for any k E Z Be careful each orbit is a subset of the set 12 n not of the group Sn We are really looking at the orbits of the action of 7 on the set 1 2 Group actions will be considered further in section 18 Proposition 112 The orbits ofo partition 12 n Proof Define X N y ltgt y E orbxo ltgt y UkX for some k E Z We claim that N is an equivalence relation Re exivity X N X since X 00X Symmetry X N y i y UkX for some k E Z But then X o ky i y N X Transitivity X N y amp y N z i y UkX amp z 07y for some kl E Z Thus 2 ok X and so X N z l Recall Definition 97 of a cycle Observe that o E 5 is a cycle if it has at most one orbit with more than one element Cycle notation therefore records orbits the cycles are disjoint for example Orbits of 134 E S5 are 134 2 5 Orbits of 1245 E S5 are 12 3 45 Theorem 113 Every permutation can be written as a product of disjoint cycles Proof Write out each of the orbits of o E 5 in order putting each orbit in parentheses Since the orbits of o partition 12 n the cycles obtained are disjoint I If you mechanically follow the algorithm for multiplying cycles together you will automatically end up with a product of disjoint cycles Examples 1 13234 1342 2 13241234 1423 Disjoint cycles commute Eg l423 23l4 Theorem 114 The order of a pennutiztion o is the least common multiple of the lengths of its disjoint cycles Proof A k cycle clearly has order k the least positive integer l such that ill ilk e Suppose the orbits of U have size 0939 E 2 Writing 7 as a product of disjoint cycles 7 71 Um we have that aquot 71 all since disjoint cycles commute All these factors must be the identity for Uquot to be the identity Thus 7quot e ltgt 7 e Vj Thus n is a multiple of 0939 for all The least such n is clearly lCl 1 10 39 I Examples 1 The order OfU l45362789 E 59 is lcm342 12 2 We can easily calculate 03465 for the above 7 Since 3465 12 288 9 we have 03465 01528809 a9 145936279899 362789 since 145 3627 and 89 have orders 3 4 and 2 respectively Transpositions 2 cycles lung are also known as transpositions since they swap two elements of l2n and leave the rest untouched Proposition 115 Every 0 E 5 is the product of transpositions Proof There are many many ways to write out a single permutation An easy one to remember is to first write 7 as a product of disjoint cycles then write each cycle as follows 11 39 k l k 1tlk71quot39 l 2 Just look carefully to see that this works Example 17645 15l416l7 De nition 116 7 E 5 is even odd if it can be written as the product of an even odd number of transpositions Proposition 117 The concept of evennessoddness is wellide ned Proof Recall that any permutation U E 5 can be written as an n X n permutation matrix A 2 cycle is a permutation matrix which swaps two rows it therefore differs from the n X n identity matrix only in that two of its columns are swapped For example 24gt 000DA H000 0H00 00H0 From linear algebra we have that swapping two columns of a matrix changes the sign of its determi nant Hence det2 cycle 71 It follows that d tar 1 if U is the product of an even number of 2 cycles e 71 if U is the product of an odd number of 2 cycles In particular 7 cannot be both odd and even De nition 118 The alternating group An n 2 2 is the group of even permutations in Sn Proposition 119 An has exactly half the elements of Sn that is An Proof Since n 2 2 we have 12 E Sn Define 4 An gt odd permutations by 410 12 o 7 We claim that this is a bijection 1 1 410 41T i 12o 12T i 711 onto If p is an odd permutation then 12 o p is even and so in An Therefore p 4112 o p Since 4 is a bijection it follows that there are exactly the same number of even and odd permutations in Sn Exactly half of them are therefore even I 12 Cosets 8 Lagrange s theorem Take a look at any of the subgroup relations in the notes and observe that the order of every subgroup is a divisor of the order of its parent group This is a general theorem Theorem 121 Lagrange The order of a subgroup H g G divides the order of G Otherwise said H g G gt HlG We will prove this shortly Remarks A similar statement to Lagrange s Theorem is the following the order of an element di vides the order of the group This is really only a statement about the cyclic subgroups of a group G and is not as general as Lagrange proper Lagrange s Theorem only makes complete sense for finite groups as any finite number is a divisor of infinity For such a simple result Lagrange is extremely powerful You may have observed that there is only one group structure of order 2 3 5 and 7 This is a general result Corollary 122 There is only one group up to isomorphism of each prime order p namely 2 Proof Let G p and choose X E G e Then X g G Lagrange tells us that the subgroup X has order that divides p But p is prime and X has at least 2 elements since X 7E e and so X p Therefore G I De nition 123 Let H g G and fix u E G The subsets qu uhzh E H Hu huzh E H are respectively the left and right cosets of H containing u Lemma 124 IfG is art Ahelum group therl the left and right cosets ofurly subgroup H g G are identical Le uH Hu Vu E G For rlorliAheliurl groups this is generally not true Examples 1 The left cosets of the subgroup 23 E 4 g Zn are as follows we write these cosets additively since the group operation is additive 0 4 048 4 1 4 159 24 2610 34 3711 Observe that the right cosets of 4 are the same as the left cosets Here we have an Abelian group and so left and right cosets are always the same 2 Recall the multiplication table for 53 given in the introduction The left and right cosets of the subgroup H e m are as follows Left cosets l Right cosets eHu1HHeu1 l HeHu1Heu1 91H rsH pirs l Hm H142 pir2 PzH th P2442 l HPZ Hhs P1443 The left and right cosets of H are different this time Theorem 125 The left cosets of H purtitiorl G Proof Define by x N y ltgt x ly E H First observe that x N y ltgt x and y are in the same left coset of H For this suppose that Xy E uH Then u lxhl ly E H and so X lu E H Since H is a group we have x luu ly x ly E H Conversely if x ly E H then y E xH Butx E XH so that Xy are in the same left coset We claim that N is an equivalence relation Re exivity x N x since x lx e E H Symmetry x N y i x ly E H x 1y 1 y lx E H i y N X Transitivity x N y amp y N z i x ly ampy 1z E H Therefore x lyy lz x lz E H i x N z The equivalence classes of the left cosets of H thus partition the group G Theorem 102 Remark The right cosets of a subgroup H also partition G In general Lemma 124 they do this is a di ererlt way to the left cosets Observe the earlier example of the cosets of the subgroup e m g 53 Observe that each of the three conditions on N being an equivalence relation corresponds to one of the three properties that characterises H as being a subgroup of G re exivity says that H contains the identity symmetry says that H is closed under inverses and transitivity says that H is closed under composition It is exactly the property that H is a subgroup that guarantees partition if H is only a subset we do not get a partition For example consider the subset 01 C 23 its left cosets are 0 01 01 1 01 12 2 01 21 which are certainly not disjoint ProofofLugmnge s Theorem The map 4 H a uH given by 41h uh is a bijection13 It follows that every left coset of H has the same cardinality as H Therefore G number of left cosets of H H Thus H divides G I Remarks Again we can argue with right cosets there is no difference In particular we see that H has exactly the same number of left and right cosets The argument of the Theorem also holds for infinite groups cosets of subgroups of infinite groups also have the same cardinality De nition 126 If H g G then G H is the number of left or right cosets of H in G G H is the index of H in G Remark If G is a finite group it is immediate that G H This is not true for infinite groups as infinite cardinals do not divide For example it can be shown that 0012 50011 2 and Q Z N0 where all 4 groups listed have the same cardinality N0 Theorem 127 IfK g H g G is u sequence ofsubgroups such that H K 8 G H are both nite then GzK G By the above remark the argument would be trivial if all threee groups were finite Proof Let G H p and H K q where 1111 lt 00 Then 3 distinct g E G such that the left cosets of H in G are ngg2H ng Similarly 3 distinct h E G such that the left cosets of K in H are thh2K h1K Claim that the cosets ofK in G are given by gith where i 1 p and 1 q 13Argument exactly like that in Proposition 119 1 Every X E giH for some i since the left cosets of H partition G Therefore gle E H However every 11 E H is in some th for some j thus 3ij such that X E gith Every X E G is therefore in one of the claimed cosets of K N Now suppose X E givth gah K for some ijtx Then in particular X E giH gaH i X i since the left cosets of H partition G But then gi lX E th h K i since the left cosets of K in H partition H It follows that givth gah K unless 0c i and 8 By 1 amp 2 the sets givth partition G and each is a coset thus they are the cosets of K in G It is clear that there are exactly pg of them I 13 Direct products De nition 131 Let G1 Gn be any groups The direct product of G1 Gn is the group 1 l l H GiG1gtltgtltGn under elementwise multiplication The elements of the direct product are written like vectors g1 gn E G1 gtlt gtlt Gn where each g E G By counting elements it is straightforward to see that the cardinality of a direct product is given by 7t 71 G G1 Gn HGv i1 i1 There is still something important to check Lemma 132 The above de nition really de nes a group Proof Multiplication in 111 G is defined as follows let m b E G for each i then d1 n 171 bn Q1171 nbn We now check the group axioms Closure Since each ibi E Gi this is immediate Associativity Each G is associative it is a short calculation to see that the associativity condition on the whole direct product is equivalent to each individual Gi being associative Identity lf ei is the identity in G then e1 en is the identity in the direct product Inverse d1dn 1 df1d1 I Remarks Really the proof uses nothing but the fact that each factor G is a group in its own right this should not be surprising as we have no other information to work with In particular you should note that the individual groups have no effect on each other all group operations are carried out at the level of the factors This is very similar to thinking about a direct sum of vector space W U 63 V without further information about where U and V sit inside W we can only view U and V as separate 33 spaces Indeed the direct sum of vector spaces is a perfect example of a direct product of groups when the groups G are written additively we usually use the direct sum notation 7i GiG1 Gn i1 For example 71 RquotRRR i1 Examples 1 22 X 23 000102101112 under addition 23 Ob serve that if we choose a 11 then the group can be written in the above order as 6a4o 2o3o a 5d Thus 22 X 23 is generated by a and is therefore cyclic Having order 6 we necessarily have 22 X 23 E 26 N 22 X 22 00 0 1 10 1 Notice that all elements are their own inverses since this is a group of order 4 we see that 22 X 22 E V is the Klein 4 group Remember this definition many people see V for the first time defined this way and are less happy thinking about it as the symmetries of the rhombus or indeed written in permutation notation as in section 9 The point to take from the above two examples is that the direct product of two cyclic groups is sometimes cyclic example 1 and sometimes not example 2 There is a general Theorem to tell you when Theorem 133 Zm X 2 E Zmn ltgt gcdmn 1 Since Zm X 2 automatically has order mn the Theorem can be rephrased to say thath X 2 is cyclic ltgt gcdmn 1 Proof Suppose first that gcdmn 1 Consider the order of 11 E Zm gtlt Zn k11 k k is the identity 00 iff k E 0 mod m and k E 0 mod But then a Am pn for some integers A44 However gcdmn 1 E m divides p and n divides A In particular a is divisible by the product mn Moreover mn11 mnmn is indeed the identity 00 Thus mo 00 ltgt o is a multiple of mn which is the same as saying that a has order mn i1 therefore generates Zm X 2 which is then cyclic Conversely suppose gcdmn d 2 2 Then is an integer divisible by both m and n Hence 7 Q m 7 d 7 lt d ml d n 7 010 for any pq E Zm X 2 since g are integers No element of Zm X 2 has order mn and so Zm X 2 is not cyclic l Corollary 134 The previous proof can be modified to show that 1 l l H Zm E Zmlmn ltgt gcdmvmj 1 Vi 7 1 Moreover if n p11 p is the prime decomposition of an integer n into powers of distinct primes then anqumxzyk 1 17k 17 34 Example Is 25 X Zn gtlt Z43 cyclic By the Corollary we can say yes since no pair of the numbers 51243 have any common factors Indeed there are 15 different ways up to reordering 22580 g 23 X 2860 g Z4 X 2645 g ZS gtlt Z516 g Z43 X 260 g 212 X Z215 g Z15 gtlt Z172 g 220 X Z129 23 X24 X2215 23 X25 X2172 23 X220 X243 24 X25 X2129 24 X215 X243 25 XleXZ43 23 XZ4XZ5 X243 Theorem 135 Suppose u E G has order r for each i Then u1un E G1 gtlt X G has order lcmr1rn Proof The argument is similar to part of the previous Theorem uh unk 0111 u is the identity iff r divides k for every i Thus k is a multiple of all the r the smallest such is the order of u1 won but this is the definition of lcmr1 rn I Example What is the order of 14 32 E Z4 gtlt Z7 gtlt Z5 X 220 Recalling that the order of X E 2 is n gcdxn we see that the above elements have orders 475 amp 10 respectively Thus the order of l432 is lcm47510 140 14 Finitely generated Abelian groups Theorem 141 Fundamental Theorem of finitely generated Abelian groups Every nitely generated Abelian group is isomorphic to u group of the form Zp31gtltgtltZpLKgtltZgtltgtltZ where the p are not necessarily distinct primes the r are positive integers and there are u finite number of factors of Z The proof is far too difficult for this course or indeed most group theory courses Its purpose here is to allow us to classify finite Abelian groups up to isomorphism and we ll do an example of this below Remember Definition 81 for what finitely generated means it is not the same as finite The above direct product is only a finite group if it has no factors of Z Example Find up to isomorphism all Abelian groups of order 450 First note that 450 2 32 52 Now apply the fundamental theorem to see that the complete list is 1 Z450 g 22 X 1232 X 252 2 22 X 23 X 23 X 252 3 22 X 1232 x25 X 25 4 22x23x23x25x25 Since writing a group as a direct product is common we have a name for groups that can be written in such a way De nition 142 G is decomposable if there exists proper subgroups HK lt G such that G E H X K Otherwise G is said to be indecomposable Example V E 22 X 22 is decomposable but Z4 is indecomposable Corollary 143 If G is finite Abelian and indecomposable then G E an for some prime p any positive integer n Proof By the fundamental theorem such an indecomposable G can have only one factor an l Recall Lagrange s Theorem 121 and how it doesn t have a general converse if miG then we cannot in general claim that G has a subgroup of order m The smallest group for which this is evident is A4 which though it has order 12 has no subgroup of order 6 When G has certain special forms however we can find partial converses to Lagrange for example Corollary 77 shows that if G is cyclic then G has exactly one subgroup for every integer dividing G The next Theorem illustrates what happens for finite Abelian groups Theorem 144 Let G befinite Abelian Then G has it subgroup of order rn for every divisor rn of G Proof G is finite Abelian and is therefore isomorphic to some 2 7 X X Z The order of G is p11 p1 Let rn pii pfquot for some integers s g r14 Recall that the cyclic subgroup of va generated by X has order p gcdp x Thus the sub group generated by pg is has order p gcdp pi Ts p The direct product of all such sub groups is then a group of order m ltp117s1gt X X ltp2ws gt gzpil X X Z Bnut this is a subgroup of 2 7 X X Z and is therefore isomorphic to a subgroup of G of order I Theorem 145 If rn is u square free integer Ek E Zgt1 such that kzirn then there is only one Abelian group of order rn up to isomorphism Proof By the fundamental theorem such a group G must be isomorphic to some val X gtlt me 1 n with rn p11 p1quot But rn being square free implies that every s is equal to 1 and all the primes p are distinct By Corollary 134 we have G E 2m Zm I Example As examples of the above we list all the groups of orders 1 through 15 and the Abelian groups of order 16 The Fundamental Theorem gives us all the Abelian groups In particular observe where Theorem 145 applies There are only two new groups we haven t seen before the Quuternion group Q8 and the Dieyelie group Dng look these up on Wikipedia or Q8 on page 226 of Fraleigh if you re interested These groups are definitely non examinable There are 9 non Abelian groups of order 16 up to isomorphism at least 5 of which we have no notation for hence we omit them You may be suspicious from looking at the table that there are no non Abelian groups of any odd order This is not so but you need to go to order 21 before you find one Note that even though the pi do not have to be distinct we still write m in the above manner and distinguish between exponents sisj even if pi pf 36 Order Abelian Non Abelian 1 21 2 22 g 52 3 23 4 Z4 V g 22 X 22 5 Z5 6 Z gsz23 D3 Sg 7 Z7 8 Zg 22 X Z4 22 X 22 X 22 D4 Q8 g DiCz 9 29 23 X 23 10 210 g 22 X Z5 D5 11 Zn 12 Zn g 23 X Z4 22 X Z g 22 X 22 X 23 D6 A4 Dng 13 1213 14 214 g 22 X Z7 D7 15 215 g 23 X Z5 16 216 Z4 X Z4 Zz X Zg Zz X Zz X Z4 Zz X Zz X Zz X Zz Many 15 Homomorphisms 8 Normal subgroups Recall Definition 32 of a homomorphism of binary relations Even though we have been using this definition when the binary relations are group operations we restate for convenience if G1 and G2 are multiplicative groups then a map 4 G1 gt G2 is a homomorphism if 41ab zpazpb Vab E G1 Homomorphisms of groups are far more interesting than those of general binary structures Before we see why it is necessary to formalise some notation for functions and sets De nition 151 Let 4 G1 gt G2 be a function between for the moment sets G1 G2 The image of a subset A C G1 is the subset 47A 47g E Gztg E A C C32 The image of G1 itself is written Im 41 41G1 Given a subset B C G2 the inverse image of B is the subset 1Bg e 61244506 B c Gl If G2 happens to have a well defined zero or identity eG2 for example if G2 is a group then the inverse image of eG2 is the kernel of 4 kart 4771862 g E G1ltPg 862 C G1 Remark The image and inverse image of a set make sense for any functions and sets the kernel of a function only makes sense if the target space has an identity Theorem 152 Let 4 G1 a G2 be a homomorphism of groups Then 1 8G1 EGz39 2 4101 W 3 H g G1 x 4H G2 4 K g G2 x 4r11lt G11 By choosing H 8G1 g G1 and K 8G2 g G2 we immediately see that the image and kernel of a homomorphism are subgroups of the domain and target groups respectively Corollary 153 If 4 G1 a G2 is u homomorphism of groups then ker 4 g G1 and Im 41 g G2 ProofofTheorem 1 Choose any g E G1 Then zpeG1zpg 418G1g 41g Since 418G1 fixes an element of G2 it is therefore the identity 8G2 1 WWW 47861 HGT Thus 4701 470W Let H g G1 be a subgroup and h1h2 E H Since zph1zph2 1h1h2 E we have that is closed under multiplication By 2 we see that zph1 1 41h1 1 E 41H thus is closed under inverses Since 41H is a subset of a group G2 it follows that 41H is a subgroup Of 8G2 RN 5 LetK g 8G2 be a subgroup and k1k2 E 1K C G1 Firstly 1k1k2 1k1zpk2 E K so 1K is closed under multiplication By 2 we have 1kfl 1k1 1 E K and so 1K is also closed under inverses 1K is therefore a subgroup of G1 I De nition 154 A subgroup H g G is normal if its left and right cosets are identical uH Hu Vu E G We write H lt1 G Lemma 155 All subgroups of un Abelian group are normal Conversely we have already seen section 12 that the left and right cosets of H p0 m lt D3 are different this H is not a normal subgroup However D3 does have the subgroup of rotations p0p1p2 g 23 which is normal Theorem 156 Let 4 G1 a G2 be u homomorphism of groups Then ker 4 lt1 G1 is normal Proof We must show that u ker 4 ker 4 u for all u E G However x E it kerzp ltgt u lx E kerzp ltgt 41u 1x 8G2 4gtlta1gt4gtltxgt 8G2 Marlon ea ltgt 470 470 The left coset of ker 4 containing u is therefore the set of elements X E G1 such that 1X 4101 The mirror argument shows that this is also the characterisation of the right coset containing ii We are therefore done I Examples 1 Recall that the trace function tr MnR gt lR is a homomorphism of additive groups These are Abelian groups and so the kernel of tr is automatically normal without needing the above Theorem The additive group of trace free matrices15 is a normal subgroup of MnlR kertr A E M7101 trA 0 4MnlR 2 4 236 gt 220 defined by 4n mod 24 The kernel of 4 is the subgroup kerzp n 4n E 0 mod 24 0612182430lt1236 is isomorphic to 26 1 if 7 even 71 if 7 odd groups Since the identity in the target space is 1 we have ker sgn An the alternating group of even permutations in Sn Indeed An 4 Sn 0 The map sgn 5 gt 1 71 E 22 given by sgnU is a homomorphism of g det GLnlR gt lRgtlt is a homomorphism and so ker det SLnlR is a normal subgroup SLnlR 4 GLnlR Compare this with example 1 U1 7r G1 gtlt Gn gt G defined as projection onto the ith factor 7rg1 gn g is ahomomor phism Therefore ker7IG1gtltgtltG391gtlt8XG1gtltgtltGn4G1gtltgtltGn If we are willing to abuse notation we can say that ker 7r G1 gtlt gtlt Giel X G X gtlt Gn is a normal subgroup of the whole direct product Indeed any combination of projections is a homomorphism eg 711 714 715 G1 gtlt X G gt G1 gtlt G4 gtlt G5 and so we can say that 71 HGj4HGi for any subsetl C 1n jel i1 All these examples should suggest an idea to you Not only are all kernels of homomorphisms normal subgroups the converse is also true any normal subgroup is in fact the kernel of some homo morphism of groups This loosely is the 1st isomorphism Theorem which we will come to shortly For the present it is helpful to record three criteria whereby we can determine if a subgroup is normal since check individual cosets is often tiresome Proposition 157 The following are equivalent 1 H 4 G is a normal subgroup 2i gH Hg VgE G 3 ghg l E H VgE G h E Hi 4 gHg 1 H Vg E G 15This kernel is often written 7013 for the specialilinear algebra and is very much related to the special linear group SLnlR the expression det 8A 8 shows that matrix exponentiation is a map exp 5nlR gt SLnlR This is the beginning of the theory of Lie groups and their Lie algebras 39 Only the last requires any comment the third is equivalent to gHg 1 C H but the map h gt gt ghg 1 is a bijection gHg 1 gt H and thus onto so we have equality we will prove this shortly The final Theorem in this section appears obvious but is actually very useful in determining what can possibly be a homomorphism Theorem 158 Let 4 G1 a G2 be u homomorphism 1 If G1 is u finite group then lmzp is u finite subgroup of G2 and its order divides that of G1 More succinctly G1 lt 00 i lmzplG1 2 Moreover Gz lt 00 i lmzplG2 Note that we are only assuming one of the groups to be finite in each case Proof 1 Recall from the proof of Theorem 156 that 1g 41h ltgt g kerzp h kerzp ie gh E G1 have the same image under 4 iff their left cosets with ker 4 are the same There are therefore exactly as many distinct elements of lmzp as there are left cosets of kerzp Thus lmzp G1 kerzp the index of kerzp in G1 Recall Definition 126 where we saw that G1 lt 00 i G1 ker 4 G1llter 4 This is clearly finite and divides G1 2 This is immediate from Lagrange s Theorem and Theorem 152 lm 4 is a subgroup of a finite group G2 and so the order of lm 4 divides the order of G2 I Examples 1 How many homomorphisms are there 4 Zm gt 2 when gcdmn 1 Suppose that 4 were a homomorphism then the Theorem says that lm 4 divides both m and n But the only integer dividing m and n is 1 therefore lm 4 0 lt 2 the image of a homomorphism always contains the identity In particular 4 must be the function 4 z gt gt 0 V2 E Zm There is therefore only one homomorphism The Proposition below gives the details when gcdmn 3A 1 How many homomorphisms are there 4 Z4 gt 53 Again the Theorem tells us that lmzp divides 4 24 and 6 532 thus lm 4 is either 1 or 2 If lm 4 2 then lm 4 is a subgroup of order 2 of 53 There are exactly 3 of these e u for each i 123 Since a homomorphism must map the identity to the identity we therefore have the homomorphisms N 4110123eu1eu1 4120123eu2eu2 IP3012138i43181i43 Finally if lm 4 has one element then 4 is the trivial homomorphism 412 e Vz E Z4 There are therefore 4 distinct homomorphisms Proposition 159 There are exactly at gcdmn distinct homomorphisms 4 Zm a Zn de ned by 41x igx mod n wherei 0d7 1 Proof Suppose thatzp1 X Then 1X xx mod n sincezp is ahomomorphism This completely determines 4 and it remains only to show which choices of 0c give well defined functions 4 is well defined iff 41X km 1X for all k E Z This is iff xx ukm E xx mod n ltgt ukm E 0 mod nfor all k E Z 40 ltgt am An for some EZ ltgt amiAn d7 a As in Theorem 76 g g have no common factors so this implies that X i g for some i E Z However 0c i kd i kn E i mod n so that onlyi 0 d 7 1 give distinct homomorphisms Conversely if X i then ma ign E 0 mod n and 4 is well defined The homomorphisms 4 Zm gt 2 are thus defined by pix igx fori 0 d 7 1 Example The only homomorphisms 4 Zn gt 216 are 410x 0 411x 4x mod 16 412x 8x mod 16 413x 12x mod 16 while the only homomorphisms 1p 216 gt Zn are 0x 0 1x 3x mod 12 Ipzx 6x mod 12 3x 9x mod 12 16 Centers and automorphisms In this section we describe some groups associated to any group which will give us further examples of homomorphisms and normal subgroups De nition 16 Let G be any group g1g2 E G We say that g1 is conjugate to g2 if 3h E G such that liglli 1 g2 Note that this is exactly the same definition you have already seen for two matrices being conju gate Proposition 162 Conjugacy is an equivalence relation Le de ned by g1 g2 ltgt g1 conjugate to g2 Proof Re exivitiy egle 1 g1 i g1 g1 Symmetry g1 g2 i Eli E G such that lig1li 1 g2 But this implies that h lgzh g1 and so g2 N g1 Transitivity Suppose g1 g2 and g2 g3 Then 3hk E G such that liglli 1 g2 and kgzk 1 g3 But then g3 khg1kli 1 and so g1 g3 I De nition 163 We call the equivalence classes of the conjugacy classes of G Note in particular that elements in the same conjugacy class have the same order hgh 1i ligjh 1 e ltgt V e The converse is not true however in A4 the elements 123 and 132 have the same order 3 but are not conjugate However they are conjugate in S4 since 23123231 132 Examples 1 If G is Abelian then every conjugacy class contains only one element This is since g1 g2 ltgt liglli 1 g2 for some li E G but by commutativity this reads g1 g2 41 2 The conjugacy classes of D3 E 53 are 8 V11 V2 V3 plP2 Theorem 164 The conjugacy Classes of Sn are the cycle types The concept of cycle type sounds vague for example 12345 has the same cycle type as 15623 but not the same as 1234 Just write an element of Sn as a product of disjoint cycles then its cycle type is obvious Proof Suppose ill uk E Sn is a k cycle and p E Sn is any element It is immediate that 1011 WW4 7011 470110 is also a k cycle Let T E Sn be written as the product of disjoint cycles T T1 17 Then pm pTlp 1psz 1New which has the same cycle type as T Conversely let 7 71 7 and T T1 17 be elements of Sn with the same cycle type that is 7139 and Ti are k cycles for the some k Define the permutation 7T by writing 7 and T one on top of the other 7Tlt71 72 7 T1 T2 T where each 7139 is the elements of the cycle 7139 written out in a row Then 7T0 T7T if Tiff is the jth element of the orbit Ti then 7TU7T 1TM 711707 moiH1 quotTiH1 TTvj Example The permutations 145 627 and 165 234 in S7 are conjugate by the permutation 1456273 1234567 lt1652347gtlt1376524gt2374639 7T1456277T 1 23746145627 26473 165234 There are many other possible choice of 7T for example by writing the orbits in different orders De nition 165 An uutomorphism Aut G of a group G is an isomorphism of G with itself The irmer automorphisms Inn G of G are the conjugations lnnG Cg G a Gwhere Cgh ghg l Proposition 166 Both the set of automorphisms Aut G and the irmer automorphisms Inn G form groups under composition Proof We do Aut G first Closure Composition of isomorphisms is an isomorphism this is since the composition of two bi jection is a bijection and the composition of two homomorphisms is also a homomorphism For the latter let 4 1p G gt G be homomorphisms then 47 0 1Pgh WWW g h g h 47 0 1Pg47 0 1PM WM 6 G 42 Associativity Aut G consists of functions under composition this is associative by Proposition 25 Identity Id g gt gt g is clearly an automorphism and moreover 1p 0 Id 1p Inverse If 4 E Aut G then 41 1 is a well defined function since 4 is a bijection Moreover the inverse of an isomorphism is also an isomorphism 4f1lt4gtltggt4gtltmgt 4f1lt4gtltghgtgt gh 4f1lt4gtltggtgt4f1lt4gtlthgtgt thus 41 1 E AutG For Inn G note that each Cg is a homomorphism MUM Mbgb l l abuzwa1 cug It also has inverse U C il since C 71C g u lugu lu g Thus each Cg is an automorphism of G and moreover Inn G is closed under composition and inverses Inn G is therefore a subgroup of Aut G 1 In fact Inn G is a subgroup of Aut G Instead of checking this explicitly we get it for free from the next Theorem Theorem 167 Inn G lt1 Aut G Proof Let T E Aut G Cg E Inn G By Proposition 157 it is enough to see that T o Cg o T 1 E Inn G For this let 1 E G then T 0 Cg 0 TAM TCgT 1h T8T 1hg 1 TgTT 1hTg 1 TghTg 1 since T is an homomorphism W901 1 Therefore T o Cg o T CTg which is in Inn G since Tg E G Example Since conjugation by an element g E G is an automorphism of G conjugation must map subgroups of G to isomorphic subgroups For example let H p0 ul g D3 Then le pinfl papuma par2 Both H and Cle are isomorphic to 22 We say that H Cle are conjugate subgroups The center of a group When a group is non Abelian there are several notions of what constitutes a maximally sized Abelian subset One of these is the center of a group De nition 168 The center of a group G is the subgroup ZGgEGguugVuEGgG The center is the set of elements of G which commute with everything in G As such the center is certamly Abelian even though we ve not shown it is a group yet this will be remedied in Proposi tion 169 Moreover Z G G ltgt G is Abelian itself Examples 1 ZDg e 2 In general ZDZnH e and ZDZn ep2 3 ZGLnlR Aln A E RX 4 ZOnlR iln It is often very difficult to calculate the centers of groups as there are a lot of calculations to check An example argument for the above example 3 runs as follows Let A E GL1 lR be a matrix with only one eigenvector v such A exist just extend v to a basis vvz vn then in this basis A having all entries on or above the leading diagonal equal to 1 and the rest 0 is such a matrix and let Z E ZGLnlR Then AZv ZAv AZv so that Zv is an eigenvector of A and so Zv is parallel to v In particular Zv must be parallel to v for every possible choice of v The only possible such matrices are multiples of the identity Proposition 169 ZG 4 G Le the center ofa group is a normal subgroup in particular it is a subgroup Proof There are two methods at our disposal to prove this Theorem firstly one can check the indi vidual group axioms to see that Z G is a subgroup of G then it is easy to see that its left and right cosets are identical gZG ZGg for any g E G since ZG commutes with everything in G Instead we will prove the Proposition by exhibiting Z G as the kernel of a homomorphism 4 We have already done most of the work Define 4 G gt Inn G by 41g Cg Thus each element 41g is the function conjugation by g The argument given in Proposition 166 shows that 4 is a homomor phism Moreover 4 has kernel ZG since ker39ygEGCgldgE GZCgIi IiVIiEG but CgIi Ii ltgt ing 1 Ii ltgt in Iig Proposition 157 tells us that kerzp ZG 4 G 17 Factor groups As the name suggests factor groups indicate a type of division in group theory The problem with dividing say g by IL is that we don t know whether to multiply by Ii on the left or the right in an Abelian group we have no problem but in general we re stuck It turns out that a sensible notion of division exists when we have normal subgroups we don t divide individual elements we work with their cosets De nition 17 Let H 4 G be normal The cosets16 of H form the factor group written GHgHgE G and where the group operation is defined by aH bH abH 16Since H is normal it is unambiguous whether we mean left or right We will tend to write left cosets 44 Ignore for the moment the problem of whether the group operation is well defined and let us check the group axioms Closure H bH abH E GH is acoset Associativity H bH CH H bCH obcH Similarly H bH CH obCH By the associatiVity of G these are identical Identity 8H H eoH H therefore 8H H is the identity Inverse o lH H o loH 8H H therefore L1H 1 o lH Why do we need H normal In the definition of a factor group we made a definition of the group operation but the definition is not independent of choices H th for any 111 E H thus the multiplication is well defined iff h1H l1th H bH for all hhhz E H ml 6 G Lemma 172 The group operation on G H is wellede 39ned if H 4 G Proof We must see that H bH th bth According to the definition this is iff obH ohlbth ltgt abrlahlbhz e H ltgt b lo lohlb e H 4 14111 6 H V111 e H b e G But this is the definition of H being a normal subgroup of G I Examples 1 mZ is a subgroup of Z and since Z is Abelian mZ is normal Write the cosets of mZ as ZmZ 0 m1 mm71 Addition in Z mZ is then H 7 0 7 i H ltmgt But this is simply addition modulo m Indeed j gt gt mod m is an isomorphism Z mZ E Zm N We can do a similar thing with 271 4 lR Then lR 271 E 0271 2 Recall example 3 of section 3 that this is isomorphic to the circle S1 lt CX U It can be seen that the Klein 4 group V is a normal subgroup of A4 Actually A4 V E Z3 g Writing the cosets of Z4 E 5 in Z20 we get Z2024 0 lt5gt11 lt5gt12 lt5gt13 lt5gtI4 lt5gt1 which is isomorphic to Z5 01 We saw before that G1 4 G1 gtlt G2 Thus G1 gtlt G2G1 is a factor group The map g1g2G1 X 82 gt gt g2 is an isomorphism G1 gtlt G2G1 E G2 45 6 Recall Propositions 166 and 169 where we saw that ZG 4 G by viewing ZG as the kernel of a homomorphism 4 G gt Inn G Thus GZG is a group WIn fact we will see in the next Theorem that GZG E Inn G ie G ker 4 E lmzp 7 We also saw that Inn G is a normal subgroup of Aut G The outer automorphism group of a group G is defined to be the factor group Aut G Inn G Remark lNarningl It may be tempting to take the idea of division of groups too far For example suppose we are given that H 4 G Since we have the concept of direct product it might be reasonable to guess that H X G H E G That life isn t as simple as this is clear from the following example ZS Zz E Z4 but 22 X ZS Zz E 22 X Z4 S Zg Compare this with example 5 above G1 gtlt G2 N G g T1 E G2 is true but H X H E G is false We have seen that all kernels of group homomorphisms are normal subgroups In fact all normal subgroups are the kernel of some homomorphism We state this as a 2 part Theorem Theorem 173 1st lsomorphism Theorem a Let H 4 G Then 7 G a GH de ned by 7g gH is u homomorphism with ker 39y H b Ifq G a G is u homomorphism with kernel H therl u GH 4 Im 41 de ned by ugH 41g is or isomorphism The Theorem can be summarised by the following formula G ker 4 E Im 11 Alternatively we say that the following diagram commutes ie 4 u o 39y GLMG lmzp g G 7 GH De nition 174 Given a normal subgroup H 4 G the homomorphism 39y G gt G H defined above is the canonical homomorphism Proof of Theorem We need to check that the two functions 39y and u defined in the Theorem have the properties we claim a Let H 4 G and define 39y G gt G H by 7g gH This is certainly a well defined function so we need only check that it is a homomorphism with ker 39y H But rg1rg2 ng ng g1g2H glgz by the definition of multiplication in a factor group Thus 39y is indeed a homomorphism More over 39yg gH H ltgt g E H thus the kernel of 39y is H as claimed b Suppose 4 G gt G is a homomorphism with kernel H then H is a normal subgroup of G and hence the factor group G H is well defined We need to check that u G H gt lm 4 defined by ugH 1g is an isomorphism Wellde ned There are choices in the definition of y gH th for any h E H However yth 1gh zpgzph 41g since 4 is ahomomorphism and h E H kerzp Homomorphism ngi4ng 4102047022 41glg2 glng thus l4 is a homomor phism 11 ng ng 3 41g1 41g2 3 gz 1g1 8c and SO gilgl E kerrp H In particular ng ng thus y is 1 1 Onto Every element of lm 4 has the form 1g for some g E G But 41g ygH so y is onto y is a well defined bijective homomorphism and thus an isomorphism y G H E Im 11 Here are several examples where we can calculate all the pieces in the Theorem Examples 1 Let 4 Z10 gt Z20 be the homomorphism with 411 4 Then by the homomor phism property 4n mod 20 In particular kerzp n E Z10 2471 E 0 mod 20 05 and lmzp 41Z10 4n mod 20 n E Z10 0481216 Observe that ker 4 5 lt Z10 is isomorphic to Z2 under addition modulo 10 and 41Z10 4 lt Z20 is isomorphic to Z5 under addition modulo 20 The cosets of ker 4 are as follows Z10kerzp kerzp16273849 The function 05 0 16 4 y Z10kerzp gt 41Z10 27 gt gt 8 38 12 49 16 is the isomorphism from the Theorem N Classify the factor group Z4 gtlt Z8 01 in terms of the Fundamental Theorem 141 of finitely generated Abelian groups le the factor group is a finite Abelian group so we must be able to write it as a direct product of Zi s The cyclic subgroup 0 1 has order 8 and its cosets are Z4 X 200011 00 lt01gt1110 lt01gt1210 lt01gt1310 01gt There are no further cosets either observe that a non zero entry in the Z8 part of i can be subtracted away by an element in the cyclic group 01 or count elements via the index of 01 there are Z4 gtlt Z8 01 488 4 cosets It is clear that the operation 1300011 j10lt01gt ij mod 40 0011 makes the factor group into a copy of Z4 Thus y ik 01 gt gt i mod 4 is an iso morphism Z4 gtlt Z8 01 E Z4 lfzp Z4 gtlt Z8 gt Z4 is the map zpik i then 4 is a homomorphism and y is the corresponding isomorphism in the 1St isomorphism Theorem 47


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.