FREE ELECTRONIC LIBRARY - Online materials, documents

Pages:   || 2 |

«Chapter 4 Cayley Diagrams Recall that in the previous chapter we defined a group to be a set of actions that satisfies the following rules. Rule 1. ...»

-- [ Page 1 ] --

Chapter 4

Cayley Diagrams

Recall that in the previous chapter we defined a group to be a set of actions that satisfies

the following rules.

Rule 1. There is a predefined list of actions that never changes.

Rule 2. Every action is reversible.

Rule 3. Every action is deterministic.

Rule 4. Any sequence of consecutive actions is also an action.

It is important to point out that this is an intuitive starting point and does not constitute the o cial definition of a group. We’ll continue to postpone a rigorous definition in this chapter and instead we will focus on developing more intuition about what groups are and what they “look like.” To get started, let’s continue thinking about the game Spinpossible (see Chapter 3).

In Exercise 3.3, we discovered that there are a total of 29 · 9! = 185, 794, 560 possible scrambled Spinpossible boards. Now, imagine we wanted to write a solution manual that would describe how to solve all these boards. There are likely many possible ways to construct such a solution manual, but here is one way.

The manual will consist of 185, 794, 560 pages such that each page lists a unique scrambling of the 3 ⇥ 3 board. Don’t forget that one of these scramblings is the solved board. Let’s make this page 1. Also, imagine that the book is arranged in such a way that it isn’t too di cult to look up a given scrambled board. On each page below the scrambled board is a table that lists all possible spins. Next to each spin, the table indicates whether doing that particular spin will result in a board that is either closer to being solved or farther. In addition, the page number that corresponds to the resulting board is listed next to each spin.

In most cases, there will be many spins that take us closer to the solved board. Given a scrambled board, a solution would consist of following one possible sequence of pages through the book that takes us from the scrambled board to the solved board. There could be many such sequences. If we could construct such a solution manual, we would have an atlas or map for the game Spinpossible. We could always say, “We are here,” and “The solution is down one of these paths.”


Note that even if we make a wrong turn (i.e., follow a page that takes us farther away from the solution), we can still get back on track by following page numbers that take us closer to the solved board. In fact, we can always flip back to the page we were on before taking a wrong turn. This page will be listed on our “wrong turn page” since doing the same spin twice has the net e↵ect of doing nothing. If you were to actually do this, the number of pages we would need to visit would be longer than an optimal solution, but we’d get to the solved board nonetheless.

Let’s get a little more concrete. Consider the game Spinpossible, except let’s simplify it a little. Instead of playing on the 3 ⇥ 3 board, let’s play on a 1 ⇥ 2 board consisting of a single row with tiles labeled 1 and 2. We’ll refer to this simplified game as Spin1⇥2.

The rules of the game are what you would expect we are restricted to spins involving just the tiles in positions 1 and 2 of the original board. A scrambling of Spin1⇥2 consists of any rearrangement of the tiles 1 and 2, where any of the tiles can be right-side-up or up-side-down.

Exercise 4.1. First, convince yourself that Spin1⇥2 satisfies our four rules of a group.

(a) How many scrambled boards are there for Spin1⇥2 ? Don’t forget to include the solved board.

(b) How many possible spins are there for Spin1⇥2 ?

Let’s try to make a map for Spin1⇥2, but instead of writing a solution manual, we will draw a picture of the group called a Cayley diagram. The first thing we’ll do is draw each of the scramblings that we found in the previous exercise. It doesn’t matter how we arrange all of these drawings, as long as there is some space between them. These little drawings will form the vertices of our Cayley diagram. Now, for each scrambling, figure out what happens when we do each of our allowable spins. For each of these spins, we’ll draw an arrow from the initial scrambled board to the resulting board. Don’t worry about whether doing each of these spins is a good idea or not. In fact, figure out what happens when we do our allowable spins to the solved board, as well. In this case, each of our scrambled boards will have 3 arrows heading out towards 3 distinct boards. Do you see why?

In order for us to keep straight what each arrow represents, let’s color our arrows, so that doing a particular type of spin is always the same color. For example, we could color the arrows that toggle the tile in the first position as green. Recall that doing the same spin twice has the net e↵ect of doing nothing, so we should just make all of our arrows point in both directions.

To make sure you are keeping up to speed, consider the following scrambled board.

This board is one of our 8 possible scrambled boards in Spin1⇥2. We have three possible spins we can do to this board: toggle position 1, toggle position 2, or spin the whole board. Each of these spins has a corresponding two-way arrow that takes us to three di↵erent scrambled boards. The figure below depicts the chunk of the Cayley Diagram involved the board above. (I’ll replace my hand drawn version later.)


Notice we have three di↵erent colored arrows. Can you see what each of the colors corresponds to? If we include the rest of the scrambled boards and all possible spins, we obtain the complete Cayley diagram for Spin1⇥3. (I’ll replace my hand drawn version later.) In this case, the spins that correspond to the three arrow colors are the generators of Spin1⇥2. What this means is that we can obtain all possible scramblings/unscramblings by using just these 3 spins. In other words, each of the scramblings corresponds to a word in these three spins. The question remains as to whether we want each board to correspond to a word that unscrambles to the solve board or scrambles the solved board. This might seem counter to how you want it to be, but we’ll adopt the convention that each board corresponds to words that scramble the solved board into the desired scrambled board.

Let t1 be the spin that toggles position 1, t2 be the spin that toggles position 2, and s1 be the spin that rotates the full board. Recall that when we write down words, we should apply the actions from right to left (like function composition).

Consider the following scrambled board.


Looking at our Cayley diagram for Spin1⇥2, we see that one way to get to this board from the solved board is to follow a blue arrow followed by a red arrow. This corresponds to the word s1 t2. However, it also corresponds to the word t2 s1 t2 t1 even though this is not an optimal solution.

Exercise 4.2. Given a word that corresponds to a scrambled board in the Cayley diagram for Spin1⇥2, how could we obtain a solution to the scrambled board?

Exercise 4.3. Using the Cayley diagram for Spin1⇥2, find three distinct words that correspond to the following scrambled board. Don’t worry about whether your word is of optimal length or not.

Exercise 4.4. Consider the Cayley diagram for Spin1⇥2, but remove all the red arrows.

This corresponds to forbidding the spin that rotates the full 1 ⇥ 2 board. Can we obtain all of the scrambled boards from the solved board using only blue and green arrows?

Exercise 4.5. Repeat the previous exercise, but this time remove only the green arrows.

What about the blue arrows?

In general, a Cayley diagram for a group G is a digraph having the set of actions of G as its vertices and the directed edges (i.e., arrows) correspond to the generators of the group. Recall that the generators are a potentially smaller set of actions from which you can derive all the actions of the group. The way you can derive new actions is by forming words in the generators. Rule 2 guarantees that every action is reversible, so we also allow the use of a generator’s reversal in our words.

The arrows follow the direction of the action that it corresponds to. If a generator is its own reversal, then the arrows corresponding to that generator are two-way arrows. It is always true that following an arrow backwards corresponds to a generator’s reversal.

We need a way to tell our arrow types apart. One way to do this is to color them. Another way would be to label the arrows by their corresponding generator.

Remember that in any group there is always a do-nothing action. One of the vertices should be labeled as the do-nothing action. From this point forward, unless someone says otherwise, let’s use e to denote our do-nothing action for a group. Each vertex is labeled with a word that corresponds to the sequence of arrows that we can follow from the do-nothing action to the particular vertex. Since there are possibly many sequences of arrows that could take us from the do-nothing vertex to another, each vertex could be labeled with many di↵erent words.

In the Cayley diagram for Spin1⇥2, our vertices were fancy pictures of scrambled 1 ⇥ 2 Spinpossible boards. This wasn’t necessary, but is convenient and appealing for aesthetic reasons. Also, we never actually labeled the vertices with the corresponding words. However, these are easy to obtain by following the sequence of arrows. Of course, in order to


do this, we need to know that the vertex that is the solved board corresponds to the donothing action.

The next two exercises may be too


for you at the moment. Give them a shot and if you can’t do them now, come back to them after you’ve constructed a few Cayley diagrams.

Exercise 4.6. Assume G is a group of actions and S is a set of generators for G. Suppose we draw the Cayley diagram for G using the actions of S as our arrows and we color the arrows according to which generator they correspond to. Assume that each vertex is labeled with a word in the generators or their reversals. If the arrows are not labeled, how can you tell which generator they correspond to?

Exercise 4.7. Assume G is a group. Suppose that S and S 0 are two di↵erent sets that generate G. If you draw the Cayley diagram for G using S and then draw the Cayley diagram for G using S 0, what features of the two graphs are the same and which are potentially di↵erent?

Let’s build a few more Cayley diagrams to further our intuition.

Exercise 4.8. Consider the group consisting of the actions that rearranges two coins, say a penny and a nickel. Let’s assume we start with the penny on the left and the nickel on the right. Let’s call this group S2.

(a) Write down all possible actions using verbal descriptions. Hint: There aren’t that many of them.

(b) Let s be the action that swaps the left and right coins. Does s generate S2 ? That is, can we write all of the actions of S2 as words in s (or its reversal)?

(c) Decide on a simple generating set for S2 and draw a Cayley diagram for S2 using your generating set. Label all the vertices and arrows appropriately. Recall that above we said that we will use e to denote the do-nothing action unless someone says otherwise.

Exercise 4.9. Consider a square puzzle piece that fits perfectly into a square hole. Let R4 be the group of actions consisting of rotating the square by an appropriate amount so that it fits back into the hole.

(a) Write down all possible actions using verbal descriptions. Are there lots of ways to describe each of your actions?

(b) Let r be the action that rotates the puzzle piece by 90 clockwise. Does r generate R4 ? If so, write down all of the actions of R4 as words in r.

(c) Which of your words above is the reversal of r?

(d) Draw the Cayley diagram for R4 using r as the generator. Be sure to label the vertices and arrows. Are your arrows one-way or two-way arrows?


Exercise 4.10. Consider a puzzle piece like the one in the previous exercise, except this time, let’s assume that the piece and the hole are an equilateral triangle. Let D3 be the group of actions that allow the triangle to fit back in the hole. In addition to rotations, we will also allow the triangle to be flipped over. To give us a common starting point, let’s assume the triangle and hole are positioned so that a base of the triangle is down. Also, let’s label both the points of the hole and the points of the triangle with the numbers 1, 2, and 3. Assume the labeling on the hole starts with 1 on top and then continues around in the obvious way going clockwise. Label the puzzle piece in the same way and let’s assume that the triangle starts in the position that has the labels matching (i.e., the point of the triangle labeled 1 is in the corner of the hole labeled 1, etc.).

(a) How many actions are there? Can you describe them? One way to do this would be to indicate where the labels of the triangle are in the hole.

(b) Let r be rotation by 120 in the clockwise direction. Does r generate D3 ?

(c) What is the reversal of r? Can you write it as a word in r?

(d) Let s be the flip (or we could call it a reflection) that swaps the corners of the puzzle piece that are in the positions of the hole labeled by 2 and 3 (this leaves the corner in position 1 of the hole in the same spot). Does s generate D3 ?

(e) What is the reversal of s? Can you write it as a word?

(f) Can we generate all of D3 using both r and s? If so, write all the actions of D3 as words in r and s (or their reversals).

(g) Draw the Cayley diagram for D3 using r and s as your arrows. Hints: One of your arrow types is one-way and the other is two-way. I suggest putting half the vertices in a circle and then the other half in a concentric circle outside your first half. Label one of the vertices on the inner circle as e and first think about applying consecutive actions of r. Try to stay on the inner circle of vertices as you do this. Now, starting at e, apply s and go to one of the vertices in the outer circle. Try to label the remaining vertices using both r and s. There are multiple ways to do it.

Pages:   || 2 |

Similar works:

«SECURITIES AND EXCHANGE COMMISSION (Release No. 34-61107; File No. SR-FINRA-2009-070) December 3, 2009 Self-Regulatory Organizations; Financial Industry Regulatory Authority, Inc.; Notice of Filing of Proposed Rule Change to Adopt NASD Interpretive Material 2210-2 into the Consolidated Rulebook as FINRA Rule 2211 Pursuant to Section 19(b)(1) of the Securities Exchange Act of 1934 (“Act”) 1 and Rule 19b-4 thereunder, 2 notice is hereby given that on October 20, 2009, Financial Industry...»

«SARCOIDOSIS OF THE SPLEEN REPORT OF FOUR CASES TWENTY-THREE YEAR FOLLOW-UP WITH A ONE CASE * IN SAuL KAY, MD.t (From the Department of Surgery, CoUege of Physicians and Surgeons, Columbia University, New York, N.Y.) This paper presents 4 cases of marked splenomegaly due to Boeck's sarcoid in which the diagnosis was not made until after splenectomy. In one case the diagnosis was suspected after an axillary lymph node had been removed and sectioned. It is intended to call attention to sarcoid as...»

«FOR MONDAY 27 OCTOBER 2008 EVERY TUESDAY AND THURSDAY NIGHTS 9.00 P.M. THE CARL FOMBRUN SHOW ISLAND TV www.islandtv.tv/live 24 hours in the air.THE FOUR EYES by Haitian National Artist Hersza Barjon NON STOP SONGS ON CARL’S CORNER RADIO: http://www.pandora.com/ http://radio.batanga.com/es/radio/boleros carl@fombrun.com carlfombrun@yahoo.com carlfombrun@mindspring.com www.fombrun.com Phone: 305.271.2748 WORDCOUNT: 5,314 CARL’S CORNER’s Webmaster: pbushan@gmail.com PLEASE NOTE The link to...»

«Wattle Grove Public School Newsletter Thursday 17th March 2016 Term 1 Issue 4 Website: www.wattlegrov-p.schools.nsw.edu.au Phone: 02 9731-1355 Email: wattlegrov-p.school@det.nsw.edu.au Fax: 02 9731-1377 Dear Parents Diary Dates Term 1, 2016 P&C EXECUTIVE 2016 The Wattle Grove Public School Parents & Citizens Association (P&C) held th Thursday 17 March its Annual General Meeting (AGM) last night Wednesday 16th March 2016. • 3/6 Assembly Following on from elections, it gives me great pleasure...»

«Workforce Timekeeper™ v6.2 Timekeeper Upgrade Guide for Hourly Employees The information in this document is subject to change without notice and should not be construed as a commitment by Kronos Incorporated. Kronos Incorporated assumes no responsibility for any errors that may appear in this manual. This document is for the use of the intended recipient, and it may not be reproduced in whole or in part or used for any other purpose than that for which it was provided without the prior...»

«Blemished Offerings Mal 1:6-8 6 'A son honors his father, and a servant his master. Then if I am a father, where is My honor? And if I am a master, where is My respect?' says the Lord of hosts to you, O priests who despise My name. But you say, 'How have we despised Your name?' 7 You are presenting defiled food upon My altar. But you say, 'How have we defiled You?' In that you say, 'The table of the Lord is to be despised.' 8 But when you present the blind for sacrifice, is it not evil? And...»

«Haworth, Cross Roads & Stanbury Parish Council Margaret Smith, Acting Clerk to the Parish Council 28 Changegate, Haworth, BD22 8DY. Telephone: 01535 644001 Email: clerk@haworthparishcouncil.gov.uk Haworth, Cross Roads & Stanbury Parish Council Minutes Parish Council Meeting held on Monday 19 January 2015, 7.00pm at West Lane Baptist Church, Haworth Present: Councillor John Huxley, Chairman Councillor Nikki Carroll; Councillor Peter Hill; Councillor Mike Holdsworth Councillor Gary Swallow;...»

«UNREVISED PROOF COPY Ev 1 HOUSE OF LORDS MINUTES OF EVIDENCE TAKEN BEFORE THE SELECT COMMITTEE ON THE EUROPEAN UNION TUESDAY 22 MARCH 2005 MR JARI VILÉN, MS HEIDI HAUTALA, MS MIAPETRA KUMPULA, MR TIMO SOINI and MR PETER SARAMO Evidence heard in Public Questions 1 17 USE OF THE TRANSCRIPT 1. This is an uncorrected transcript of evidence taken in public and reported to the House. The transcript has been placed on the internet on the authority of the Committee. 2. Any public use of, or reference...»

«File: 06.Mallory Final revised Created on: 11/9/2006 1:39:00 PM Last Printed: 11/10/2006 1:16:00 PM COMMENTS “An Officer of the House Which Chooses Him, and Nothing More”: How Should Marsh v Chambers Apply to Rotating Chaplains? Jeremy G. Mallory† INTRODUCTION The occasions for legislative prayer include the everyday, the farcical, and the momentous. The people delivering legislative prayers have ranged from the traitorous Jacob Duché to the stirring Peter Marshall (who became a...»

«1 ENTERTAINING ANGELS Sermon preached by Rev. Sarah Segal McCaslin September 2, 2007 Jeremiah 2:4-13, Hebrews 13:1-8, 15-16 Our Second Lesson this morning comes from the Letter to the Hebrews. I’ll be reading from chapter 13. The bulletin notes that the reading includes verses 1-8 and 15-16, but I am going to shorten the passage a bit. There are many images to explore, and I would like to concentrate the imagery to a slightly more manageable degree. Listen now for God’s Word: Let mutual...»

«Pye, C., Loeb, D. F., Redmond, S. & Richardson, L. Z. 1995. When Do Children Acquire Verbs? In E. V. Clark (Ed.), The Proceedings of the Twenty-sixth Annual Child Language Research Forum, pp. 60-70. Stanford: Center for the Study of Language and Information. When Do Children Acquire Verbs? Clifton Pye, Diane Frome Loeb Sean Redmond & Lori Zobel Richardson The University of Kansas Acknowledgements This research is part of a larger study supported by funds from NIH 1 RO3 DC 01735-01 to the first...»

«Volume VI, Issue 1 February 2014 Domestic Violence Review Office of the State Courts Administrator Office of Court Improvement Contents Domestic Violence Review Virtual Court Available for Continuing Education Credits News from the Office of Court Improvement Upcoming Projects and Events BIP Graduation Letter Caselaw Corner Monitoring Batterers’ Intervention Programs: An Ongoing Issue Office of Court Improvement Helpful Web Resources Domestic Violence Staff Family Courts Rose Patterson, Chief...»

<<  HOME   |    CONTACTS
2017 www.thesis.dislib.info - Online materials, documents

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.