INTRO TO MOD ALGEBRA
INTRO TO MOD ALGEBRA MTHSC 412
Popular in Course
verified elite notetaker
Popular in Mathematics (M)
This 37 page Class Notes was uploaded by Jazmyn Braun on Saturday September 26, 2015. The Class Notes belongs to MTHSC 412 at Clemson University taught by Matthew Macauley in Fall. Since its upload, it has received 27 views. For similar materials see /class/214283/mthsc-412-clemson-university in Mathematics (M) at Clemson University.
Reviews for INTRO TO MOD ALGEBRA
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/26/15
MthSc 412 Abstract Algebra Matthew Macauley Clemson University Department of Mathematical Sciences http www math Clemson edu Nmacaule Fall 2010 M Macauley MLhSc 412 Introduction i 90 O N 9 Welcome to MthSc 412 Fall 2010 lntroductions Discussion of the class and the syllabus Expectations and general game plan My web page httpwwwmathclemsoneduNmacaule Web page for textbooks including errata http web bentley eduemplcncartervgt http abstract ups edu Group Explorer http groupexplorer sourceforge net OK let39s get started M Macauley MLhSc 412 Chapter 1 What is a group Matthew Macauley Clemson University Department of Mathematical Sciences http www math Clemson edu Nmacaule Fall 2010 M Macau ey Chapterl Our introduction to group theory will begin by discussing the famous Rubik39s Cube It was invented in 1974 by Erno Rubik of Budapest Hungary Erno Rubik is a Hungarian inventor sculptor and professor of architecture According to his Wikipedia entry He is known to be a very introverted and hardly accessible person almost impossible to contact or get for autographs M Macauiey Chapterl Not impossible aimost impossible Figure June 2010 in Budapest Hungary M Macaulay Chapter 1 o The cube comes out of the box in the solved position 0 But then we can scramble it up by consecutively rotating one of its 6 faces M Macauley Chapter 1 o The result might look something like this o The goal is to return the cube to its original solved position again by consecutively rotating one of the 6 faces Since Rubik39s Cube does not seem to require any skill with numbers to solve it you may be inclined to think that this puzzle is not mathematical Group theory is not primarily about numbers but rather about patterns and symmetry something the Rubik s Cube possesses in abundance M Macauley Chapter 1 Let39s explore the Rubik39s Cube in more detail In particular let39s see if we can identify some key features that will be recurring themes in our study of patterns and symmetry First some questions to ponder 0 How did we scramble up the cube in the first place How do we go about unscrambling the cube 0 In particular what actions or moves do we need in order to scramble and unscramble the cube There are many correct answers 0 How is Rubik39s Cube different from checkers 0 How is Rubik39s Cube different from poker M Macauley Chapterl Let39s make 4 key observations Observation 11 There is a predefined list of moves that never changes Observation 12 Every move is reversible Observation 13 Every move is deterministic Observation 14 Moves can be combined in any sequence M Macaviey Chapterl We could add more to our list but as we shall see these 4 observations are sufficient to describe the aspects of the mathematical objects that we wish to study Group theory studies the mathematical consequences of these 4 observations which in turn will help us answer interesting questions about symmetrical objects Group theory arises everywhere In puzzles visual arts music nature the physical and life sciences computer science cryptography and of course all throughout mathematics Group theory is arguably one of the most beautiful subjects in all of mathematics M Macauley Chapterl Rules of a group Instead of considering our 4 observations as descriptions of Rubik39s Cube let39s rephrase them as rules axioms that will define the boundaries of our objects of study Advantages of our endeavor 1 We make it clear what it is we want to explore 2 Helps us speak the same language so that we know we are discussing the same ideas and common themes though they may appear in vastly different settings A The rules provide the groundwork for making ogica deductions so that we can discover new facts many of which are surprising M Macauiey Chapterl Our rules Rule 15 There is a predefined list of actions that never changes Rule 16 Every action is reversible Rule 17 Every action is deterministic Rule 18 Any sequence of consecutive actions is also an action M Macaulay Chapterl What changes were made in the rephrasing Comments 0 We swapped the word move for action 0 The usually short list of actions required by Rule 15 is our set of building blocks called the generators 0 Rule 18 tells us that any sequence of the generators is also an action Finally here is our unofficial definition of a group We39ll make things a bit more rigorous later Definition 19 A group is a system or collection of actions satisfying Rules 15 18 M Macauley Chapterl Observations about the Rubik39s Cube group Frequently two sequences of moves will be indistinguishable We will say that two such moves are the same For example rotating a face by 90 once has the same effect as rotating it five times Fact There are 43252003274489856000 distinct configurations of the Rubik39s cube While there are infinitely many possible sequences of moves starting from the solved position there are 43252003274489856000 truly distinct moves All 43 x 1019 moves are generated byjust 6 moves a 90 twist of one of the 6 faces Let39s call these generators a b c d e and 1 Now every word over the alphabet 3 b7 c7 d7 e7 f describes a unique configuration of the cube starting from the solved position M Macauley Chapterl Group Exercises OK let39s explore a few more examples 1 Discuss Exercise 11 see Bob Back of book as a large group 2 In groups of 2 3 complete the following exercises not collected 0 Exercise 13 see Bob 0 Exercise 14 3 I39d like two groups to volunteer to discuss their answers to the two previous exercises 4 Now mix the groups up so that no group stays the same In your new groups complete Exercise 18 I want each group to turn in a complete solution M Macauley Chapterl Potential quiz questions Here are some potential questions that I may ask you on the quiz at the beginning of next class 1 State our unofficial definition of a group by listing the 4 rules 2 Define generators 3 Provide 2 examples of a group In each case describe a set of generators M Macauley Chapterl References I borrowed images and material from the following web pages 0 http oz plymouth eduNdcernst 0 http www cunymath cuny edupagemm 0 http wwwmath cornell eduNmecWinter2009Lipa Puzzleslesson2 html M Macauley Chapterl Chapter 2 What do groups look like Matthew Macauley Clemson University Department of Mathematical Sciences http www math Clemson edu macaule Fall 2010 M Macauley MLhSc 412 A road map for the Rubik s Cube There are several solution techniques for the Rubik39s Cube If you do a quick Google search you39ll find several methods for solving the puzzle These methods describe a sequence of moves to apply relative to some starting position In many situations there may be a shorter sequence of moves that would get you to the solution In fact it was shown in July 2010 that every configuration is at most 20 moves away from the solved position Let39s pretend for a moment that we were interested in writing a complete solutions manual for the Rubik39s Cube Let me be more specific about what I mean M Macaulay MLhSc 412 We39d like our solutions manual to have the following properties 1 M 9quot Given any scrambled configuration of the cube there is a unique page in the manual corresponding to that configuration There is a method for looking up any particular configuration The details of how to do this are unimportant Along with each configuration a list of available moves is included In each case the page number for the outcome of each move is included and information about whether the corresponding move takes us closer to or farther from the solution Let39s call our solutions manual the Big Book See Figure 21 on page 13 for a picture of what a page in the Big Book might look like M Macaulay MLhSc 412 We can think ofthe Big Book as a road map for the Rubik39s Cube Each page says you are here and if you follow this road you39ll end up over there Haw siT N HERE NVU Figure Potential cover and alternative title for the Big Book Maui Ms m Unlike a vintage Choose Your Own Adventure book you39ll additionally know whether over there is where you want to go or not Pros of the Big Book 0 We can solve any scrambled Rubik39s Cube 0 In fact given any configuration every possible sequence of moves for solving the cube is listed in the book long sequences and short sequences 0 The Big Book contains complete data on the moves in the Rubik39s Cube universe and how they combine M Macaulay MLhSc 412 Cons of the Big Book 0 Wejust took all the fun out of the Rubik39s Cube 6 lfwe had such a book using it would be fairly cumbersome 0 We can39t actually make such a book Rubik39s Cube has more than 43 x 1019 configurations The paper required to write the book would cover the Earth many times over The book would require over a billion terabytes of data to store electronically and no computer in existence can store that much data M Macaulay MLhSc 412 Despite the Big Book39s apparent shortcomings it made for a good thought experiment The most important thing to get out of this discussion is that the Big Book is a map of a group We shall not abandon the mapmaking ideas introduced by our discussion of the Big Book simply because the map is too large We can use the same ideas to map out any group In fact we shall frequently do exactly that Let39s try something simpler M Macauley MLhSc 412 The Rectangle Puzzle 0 Take a blank sheet of paper our rectangle and label as follows This is the solved state of our puzzle 0 The idea of the game is to scramble the puzzle and then find a way to return the rectangle to its solved state 0 We are allowed two moves horizontal flip and vertical flip where horizontal and vertical refer to the motion of your hands rather than any reference to an axis of reflection M Macaulay MLhSc 412 We39ll spend some time in Chapter 3 discussing why these two moves and not some others are the ones that make sense for this game However it is worth pointing out that these two moves preserve the footprint of the rectangle Are there any others that preserve its footprint Using only the two valid moves scramble your rectangle Any sequence of horizontal and vertical flips will do but don39t do any other types of moves Now again using only our two valid moves try to return your rectangle to the solved position Observations M Macaulay MLhSc 412 Question Do the moves of the Rectangle Puzzle form a group How can we check For reference here are the rules of a group Rule 15 There is a predefined list of actions that never changes Rule 16 Every action is reversible Rule 17 Every action is deterministic Rule 18 Any sequence of consecutive actions is also an action M Macauley MLhSc 412 OK let39s see if we can make a road map for our newly found group Using our multiple copies of the rectangle some colored yarn and some sticky notes let39s see what we can come up with Someone remind me to take a picture when we are done We39ve just created our first road map of a group Observations What sorts of things does the map tell us about the group We see that o the group has two generators horizontal flip and vertical flip Each generator is represented by the two different colors of yarn o the group has 4 actions the identity action horizontal flip vertical flip and 180 rotation r h o v v o h o the map shows us how to get from any one configuration to any other there may be more than one way to follow the yarn M Macaulay MLhSc 412 It is important to note that how we choose to layout our map is irrelevant What is important is that the connections between the various states are preserved However we will attempt to construct our maps in a pleasing to the eye and symmetrical way The official name of the type of group road map that we have just created is Cayley diagram named after the 19th century British mathematician Arthur Cayley In general a Cayley diagram consists of nodes that are connected by colored or labeled arrows where 0 an arrow of a particular color represents a specific generator 0 each action of the group is represented by a unique node sometimes we will label nodes by the corresponding action 0 all necessary arrows are present more on this later M Macaulay MLhSc 412 More on arrows 0 An arrow corresponding to the generator g from node A to node B means that node B is the result of applying the action g to node A o If the reverse of applying generator g is the same as g this happens with horizontal and vertical flips then we have a 2 way arrow Our convention will be to drop the tips of the arrows on all 2 way arrows Here is one possible representation of the Cayley diagram for our Rectangle Puzzle M Macaulay MLhSc 412 An alternative set of generators for the Retangle Puzzle Observe that horizontal flip and a 180 rotation also generate the Rectangle Puzzle group Let39s build a Cayley graph using these generators What do you notice about the structure of this alternate Cayley graph Both Cayley graphs have the same structure Perhaps surprisingly this might not always be the case Indeed there are more complicated groups for which different generating sets yield Cayley graphs that are structurally different We39ll see examples of this shortly M Macaulay MLhSc 412 The 2 Light Switch Group Let39s map out another group which we39ll call the 2 Light Switch Group Here are the details 0 Consider two light switches side by side that both start in the off position 0 We are allowed 2 actions flip L switch and flip R switch Do these actions generate a group In small groups map out the 2 Light Switch Group using paper and yarn just like we did for the Rectangle Puzzle I suggest using U and D to denote light switch up and light switch down respectively M Macaulay MLhSc 412 Now draw the more abstract version of the Cayley diagram What do you notice What we should notice is that the Cayley diagram for the Rectangle Puzzle and the Cayley diagram for the 2 Light Switch Group are essentially the same The 4 rectangle configurations correspond to the 4 light switch configurations Horizontal flip and vertical flip correspond to flip L switch and flip R switch Although these 2 groups are superficially different the Cayley diagrams help us see that they have the same structure The fancy phrase for this phenomenon is that the two groups are isomorphic more on this later Any group with the same Cayley diagram as the Rectangle Puzzle and the 2 Light Switch Group is called the Klein 4 group and is denoted by V4 for vierergruppe four group in German It is named after the mathematician Felix Klein M Macaulay MLhSc 412 It is important to point out that the number of different types ie colors of arrows is important For example the following Cayley diagram does not represent V4 Think What group has a Cayley graph like the diagram above Question Is is possible for two groups to have different looking Cayley diagrams yet really be the same We39ll talk more about what same means later M Macaulay MLhSc 412 More Group Exercises Let39s explore a few more examples 1 In groups of 2 3 try to mix the groups up again complete the following exercises not collected Exercise 21 see Bob 0 Exercise 23 see Bob Exercise 25 Exercise 28 see Bob 0 Exercise 210 Exercise 213 see Bob 2 I39d like each group to present their solution to one of the problems above 3 Now complete Exercise 218 I want each group to turn in a complete solution M Macaulay MLhSc 412 Properties of Cayley graphs Observe that at every node of a Cayley graph there is exactly one out going edge of each color Question 1 Can an edge in a Cayley graph every connect a node to itself Question 2 Suppose we have an edge corresponding to generator g that connects a node X to itself Does that mean that the edge g connects every node to itself In other words can an action be the identity action when applied to some actions but not to others Visually we39re asking if the following scenerio can ever occur in a Cayley diagram 8 8 Bio M Macaulay MLhSc 412 Perhaps surprisingly the previous situation is impossible Let39s properly formulate and prove this Theorem Suppose an action g has the property that gx X for some other action X Then g is the identity action ie gh h hg for all other actions h Proof The identity action we39ll denote by 1 is simply the action hh l for any other action h If gx X then multipling by X 1 on the right yields g gxx 1 xx 1 1 Thus g is the identity action D This was our first mathematical proof It shows how we can deduce interesting properties about groups from the rules which were not explicitly built into the rules M Macauley MLhSc 412
Are you sure you want to buy this material for
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'