Question 2.1. How to present Cayley diagram as a table (matrix)?
Graphical Cayley diagram is good for visualization. However a table is a good tool of exploration and automation of calculations.
Solution
Rows names set (x-axis) will be a set of object states which is a set of all the nodes in Cayley diagram. Columns names set (y-axis) is generators (simplest non-breakable actions).
Let's say we have m generators g1, g2, …, gm. For example as the book author mentions in Section 1.2, Rubik's cube will have 6 generators as we can rotate each of six edges clockwise and it is enough to define all the other actions. Also we have n possible states of the object (s1, s2, ..., sn). In case of Rubik's cube, n is enormous, it should be something around zillion. Then our table will be as follows:
Question 2.2. Can we get from any point to any point in Cayley diagram of a group?
We are given a group and its Cayley diagram. Let's choose its random node (point). Can we make a path via generators actions to any other node? Can there be a node belonging to a group that is not accessible from our chosen node?
Solution
It is assumed that we can get to any target node from so called starting node by applying generators actions. Otherwise we wouldn't include that target node in a group.
E. g. in the Chapter 1 starting node was Rubik's cube with each edge having same color.
According to Definition 1.9, every action is reversible. Hence, we can get from any node to the starting node. In turn supra we noted that we can get from the starting node to any node.
Question 2.3. If we could get from any node to any other node does it mean that every action is reversible?
Say we have a group defined as follows:
Rule 1.5. There is a predefined list of actions that never changes.
Rule extra. We can get from any state (node) to any other node.
Rule 1.7. Every action is deterministic.
Rule 1.8. Any sequence of consecutive actions is also an action.
This is the Definition 1.9 with one rule replaced. We removed Rule 1.6 "Every action is reversible" and we placed Rule extra instead "We can get from any state (node) to any other node". By "node" we understand here any state which is the result of any combination of generators applied to starting point.
Does it mean that Rule 1.6 should follow from these?
Solution
Yes it follows. Let's take 2 random nodes: A and B. Rule extra means that we can always get from A to B and from B to A. Hence, A<->B action is reversible.
Question 2.4. What if we choose another node for start?
Let's change the initial element, so we start from any other node of the Cayley diagram. The diagram per se remains the same.
Will it still be a group? Will we still comply with all the group rules?
Question 2.5 What algorithm can allow us to search for all the possible object states in a given group?
Say we have the following. We have an object and its initial state. Also we have a set of generators. For any given state and generator pair, we know the result, i. e. we know what new state we get by applying given generator to given state. Sow how can we get a set of all possible states?
Solution
E. g. in Section 2.4, the book author provided the following algorithm for the rectangle puzzle: "We branched out from the starting position using each generator, and then branched out from each of those positions using each generator again. If the puzzle had been more complicated, we could have continued this process further, exploring farther and wider until we had found every location in the realm." Let's generalize it for any group. Also let's use table format which is machine friendly, especially for processing large amount of data in case of complex groups like Rubik's cube.
Supra in Question 2.1 we noted that Cayley diagram could be presented as a matrix: states x generators. Let's use this format for finding all the possible states.
Say our initial state is s1. And we have m generators g1, g2, …, gm. Let's apply each of g to s1, then we will get n states, n≤m. Then let's apply each generator to each of states s1, s2, ..., sn, so we get a matrix n by m dimensions.
The matrix body will contain some new states in turn. Some of resulting states will belong to the set {s1, s2, ..., sn} and some will not. Those that do not are {sn+1, sn+2, ..., sn+k}. Let's join sets {s1, s2, ..., sn} and {sn+1, sn+2, ..., sn+k}. Then we get a new set {s1, s2, ..., sn+k}. This set will form a new axis for the next matrix.
Then we fill this matrix again by applying generators to states axis. Say in the body matrix we will have l new states that do now belong to {
s1, s2, ..., sn+k}. Then our next matrix will have axis of {
s1, s2, ..., sn+k+l}. Etc. We will repeat this iteration until we get a situation when applying generators give us no new states.
However one question is still remaining. How do we prove that this algorithm covers absolutely all the states?
Question 2.6. How can we automatically convert Cayley diagram to a matrix from Question 2.1 and back?
What universal algorithm can we use?
Question 2.6. Should Cayley diagram contain generators only or all the possible actions and why?
From the book it follows that the diagram depicts generators only. Can there be a case when depicting all the actions could be useful also?
Answers to the book's exercises
Exercise 2.1
An answer to this exercise is also given in the end of the original book.
We have 2 generators here: horizontal flip and vertical flip. There are two unique actions we can get by combining these generators.
First one is "do nothing". We get it by doing two horizontal flips in a row or two vertical flips in a row. It returns us to the initial state.
The second one is performing two different flips in a row: horizontal and vertical or vertical and horizontal.
All the other actions merely repeat previous mentioned ones.
Exercise 2.2
This is similar to Exercise 2.1.
We have 2 generators here: Flipping the first switch and flipping the second switch. There are two unique actions we can get by combining these generators.
First one is "do nothing". We get it by doing two first switch flips in a row or two second switch flips in a row. It returns us to the initial state.
The second one is performing two different flips in a row: first switch and second switch or second switch and first switch.
All the other actions merely repeat previous mentioned ones.
Exercise 2.3
An answer to this exercise is also given in the end of the original book.
Yes it can. This is "do nothing" action. Here is the group for example.
The object is a light switch. The only generator is flipping it twice.
This generator presents a Cayley diagram arrow pointing the node to itself.
Exercise 2.4
An answer to this exercise is also given in the end of the original book.
The diagram will contain 2 nodes since we have only two possible states. These two nodes will be connected by only one line. This line illustrates initial generator and its reverse action which brings the object to the initial state.
Exercise 2.5
With a reference to Exercise 1.4, we consider only (b) clause of it because only it describes a group.
Let's use the recursive method provided by the book author in Section 2.4: Beginning at any one configuration or situation, explore carefully using each generator, one at a time. Explore thoroughly and carefully, making a map as you go and labeling the transitions between states with the moves that cause them. Continue until your map contains no unanswered questions, as described above.
Let's mark three pictures consequently as 1, 2 and 3. Then the room with walls will be denoted as a three symbols string. First symbol is the picture hanging on the left wall, second symbol is the picture hanging on the middle wall and third symbol is the picture hanging on the right wall. E. g. in the "123" string we have the "1" picture on the left wall, "2" picture on the middle wal and "3" on the right wall.
We denote generators on the diagram as follows. Red arrow is swapping the art on the left wall with the art on the center wall, Blue arrow is swapping the art on the center wall with the art on the right wall. All the arrows have 2 pointers on both sides because they are reversible by executing the same generator again.
Let's deem Exercise 1.13 is about integers not whole numbers. Than Cayley diagram can be presented as follows. We draw an infinite straight (or not straight) line with all the integers marked on it. Each integer will have two outbound and two inbound arrows for the consequent generators. Following Question 2.6 supra, we draw generators only in our diagram. So we don't depict infinitely many arrows for all the possible actions.
In the solution for Exercise 1.13 supra we found that there are only two generators: adding 1 and subtracting 1 from the current number. Let's deem adding 1 is a red arrow and subtracting 1 is a blue arrow. Then the diagram will be depicted as follows.
Exercise 2.7
Say we have a starting node as whole number x. Then we have two possible states: x and -x. Multiplying by one doesn't change the state; and multiplying by minus one changes the state.
Let's denote multiplying by -1 as red arrow. Multiplying by one doesn't change a state so we don't have an arrow notation for it.
So x is not zero. If it would be zero then we have just one state which is starting node, the zero itself. Otherwise, the diagram is as follows.
So if x is zero than the diagram is as follows. Generators don't change the starting node.
Exercise 2.8
An answer to this exercise is also given in the end of the original book. Here is the note about the solution provided by the book author. In the solution picture for Exercise 2.8, there are arrows of only two colors. However the exercise provides three generators. That means, the book author uses only two of them. This is more elegant solution. In the book author's solution picture, red arrow stands for quarter turn and blue arrow stands for one of flips (either horizontal or vertical).
(a)
We have 8 possible states here. One way to calculate their number is as follows. Let's pick one number from one of the corners of the square rectangle. Say it is one. This number can take one of four corners of our square. We can do that by merely rotating the figure. So we already have four possible combinations.
In each of these combinations we can have two possible outcomes. We can switch between them by consequently doing quarter turn and horizontal flip. E. g. when number one is in the top left corner we could have the possible two outcomes:
So in total we have 4*2=8 possible nodes in this group
Another way to find the total quantity of combinations is as follows. First we turn it clockwise four times so then we have four combinations. Then we flip the square paper so it lays down on the table on its another side. Then we turn the square clockwise again four times. And here are another four states. Total is eight.
And we have three generators.
Let's denote the diagram generators as following arrows:
Red arrow: flip vertically. This arrow has pointers on the both sides because this flip is reversible by applying the same flip again.
Blue arrow: flip horizontally. This arrow also has pointers on the both sides because this flip is reversible by applying the same flip again
Black arrow: quarter-turn clockwise. This arrow has a pointer only on one side.
So the diagram is as follows:
(b)
In the rectangle puzzle, the quarter turn changes the shape of space occupied by the figure. However it is not clear why we cannot use turn for rectangle puzzle. In fact we can. Nothing prohibits us to change the final space shape occupied by the figure yet. Especially if we rotate rectangle around the geometric center of the figure. Later in Chapter 3 the book author will impose the restriction on a shape occupied by a figure. However for now we are free to rotate a rectangle as well as a square.
Exercise 2.9
An answer to this exercise is also given in the end of the original book.
On a Cayley diagram, let's denote arrow colors as follows:
Vertical flip - red arrow.
Horizontal flip - blue arrow.
Both flips - black arrow.
(a)
(b)
Hereby, the diagram shows that v and b are sufficient to generate V4 because of the following: we can get from any point to any other point on the diagram with the current arrows only. By the way, see also Question 2.3 supra.
(c)
Hereby, like in (b) supra the diagram shows that h and b are sufficient to generate V4 because of the following: we can get from any point to any other point on the diagram with the current arrows only. See also Question 2.3 supra.
Exercise 2.10
We have a clock hanging on the wall. The only generator is moving clock arrows 12 hours forward. This generator is reversible by itself. By doing this generator two times, we come back to the initial state because we move arrows 24 hours forward.
Exercise 2.11
Before looking for possible examples, let's find out what are common properties of the rectangle Cayley diagram from Figure 2.9. So it would be easier to look for a practice situation if we know its criteria (properties).
We see from the diagram that:
1) There are two generators.
2) If we apply any generator to any node two times we get "do nothing" action.
So we need to model a situation where we have two generators which are reversible by themselves.
Our planet rotates around Sun. At the same time, it rotates around itself (around its own axis). Let first generator be to rotate the planet 180 degree around the sun (make half circle). So the second generator is to rotate the planet 180 degree around its own axis (half circle also). Applying any of these generators two times gives us 360 circle which means "do nothing" action.
Exercise 2.12
An answer to this exercise is also given in the end of the original book.
Like in the solution to Exercise 2.10 supra, we have a clock hanging on the wall. The only generator is moving clock arrows 8 hours forward. So by doing this generator three times, we move arrows 24 hours forward. So we are in the initial state again.
Exercise 2.13
An answer to this exercise is also given in the end of the original book.
Generators are arrows on a Cayley diagram. It seems like we don't show actions on Cayley diagram that are combined of generators. So we show there generators only. See also Question 2.6 supra.
Exercise 2.14
There is a predefined list of arrows (generators) on a Cayley diagram that never changes. For the second part of the exercise we cannot give a clear answer yet. It is not 100 percent clear what does Rule 1.5 really mean, see for details Question 1.10 infra.
Exercise 2.15
Say we can get from A node to B node via some arrow (generator) on the Cayley diagram. This path should be reversible. That means, we should be able to get from B node back to A node via certain path of arrows.
Here is the simplest possible Cayley diagram not satisfying Rule 1.6:
An answer to this exercise is also given in the end of the original book.
Exercise 2.16
Every arrow is univocal, it is determined and it points from one node to only one another node, regardless of random external circumstances. So the arrow behavior is determined and it doesn't depend on external random circumstances.
Let's draw an example not complying with Rule 1.7. Same generator points simultaneously from A node to two other nodes. Every time the choice between two nodes is made on the external random circumstances. Say it is based on the random numbers generator or a side of dropped coin.
Exercise 2.17
An answer to this exercise is also given in the end of the original book.
See also Question 1.6 supra. Every node should have outbound arrows for all the generators. Otherwise, this Cayley diagram is not a group. E. g. like in Exercise 2.15 supra, this diagram is not in compliance with Rule 1.8:
Exercise 2.18
Before coming to the solution, let's define its criteria like in Exercise 2.11
supra. The previous square rectangle game from Exercise 2.8 has the following properties:
(0) Compulsory requirement: generators should form a group as per Rules 1.5-1.8.
(1) Compulsory requirement: Any action should not change the shape of the initial placeholder. After moving, the rectangle should fit the initial placeholder shape again.
(2) If possible, quantity of generators should be minimized. Like the book author did it in his solution for Exercise 2.8. Though there is no official requirement for minimization.
(3) If possible, generators should be defined in the following way. They should cover all the possible combinations of the triangle figure complying with (1) clause supra. Note we can form a group not complying with this optional requirement: say we have a rectangle puzzle from Section 2.2 with only one action of horizontal flip.
All medians of equilateral triangle intersect in the same point called a centroid. We need medians and centroid to define generators for this group. The following possible actions comply with (1):
- Turn the triangle clockwise 120 degree around its centroid.
- Flip the triangle around its any median.
So with just two generators we can generate a group of equilateral triangle. These two could be flips around two different medians. Or they could be the flip around one median and rotation 120 degree around the centroid.
For the map of the group please refer to the book author's diagrams supra in Exercise 2.19(c).
Exercise 2.19
(a)
In both a triangle and a square it was enough to have two generators. So the conjecture is two.
(b)
Let's build bisectors from all of the pentagon corners. Their intersection is the centroid of the pentagon. Like in Exercise 2.18 supra, we take two actions. First is flipping the pentagon around one it's bisectors. Second is rotating the pentagon clockwise 72 degrees.
So our conjecture is confirmed. These two actions are enough to cover all the possible states of this group.
The open question is as follows. Can we use two generators to generate the pentagon group by choosing flips around two different medians (bisectors)? So we don't use 72 degrees rotation at all. We can try it by cutting a piece of pentagon paper and play with it like we did with rectangle square supra (like the book author proposed in Section 2.2). Or we can try to prove this conjecture for the common case which seems like more difficult. Anyway this question is still open..
For the map of the group please refer to the book author's diagrams supra in Exercise 2.19(c).
(c)
Here are the diagrams from the Group Explorer's library.
The equilateral triangle group:
The square group:
The regular pentagon group:
(ii) All the diagrams do support the conjecture of that two generators are enough to generate a group for each case. There are only arrows of two colors on each diagram.
(d)
In the (b) clause supra we considered two cases for the conjecture:
- Generators are flips around two different medians. This should work for a triangle, see Exercise 2.18 supra. However we do not provide a proof for this case hereby. There are some difficulties. There is a situation when a polygon has even number of vertices. E. g. look at the square from Exercise 2.8. Flipping around two medians is not enough to cover all the possible positions of the placeholder shape.
- Generators are a flip around one median and a rotation for 360/n degrees around a centroid where n is a number of polygon vertices. We will provide a proof for this case.
We provide a proof that our conjecture complies with criteria (0)-(3) defined in the solution to Exercise 2.18 supra.
(0) We form a group as per Rules 1.5-1.8:
Rule 1.5 is satisfied. There is a predefined list of actions that never changes. Well yep, there is.
Rule 1.6 is satisfied. Every action is reversible. To reverse a flip we need to do a second flip in a row. To reverse a rotation we need to do another n-1 rotations after that. So we are kind of doing full circle and returning to the initial position. Since generators are reversible, any combined actions are also reversible, see also Question 1.3 supra.
Rule 1.7 is satisfied. Every action is deterministic. Well yep, they are.
Rule 1.8 is satisfied. Any sequence of consecutive actions is also an action. See also Question 1.6 supra. Any generator results in the polygon taking the same shape of the placeholder due to the symmetry of the polygon. So we can apply any generator to this shape again.
(1) Generators do not change the shape of the initial placeholder. Yep, this is due to the symmetry of the polygon.
(2) Quantity of generators is minimized. Currently the quantity is two. With the quantity of one we can still generate a group as per (0) clause supra. However the question is open as whether we are able to generate all the possible positions of the figure in the placeholder shape as as per clause (3) infra. Theoretically we could define a generator as a consequence of IF algorithm statements like for pentagon say: if it is iteration 1 then rotate, if it is iteration 6 then flip etc. However I assume it will violate Rule 1.7 in the book author's meaning. So the question bout compliance with this (2) clause is still open.
(3) Generators cover all the possible combinations of the polygon figure complying with (1) clause supra. Number of states for n-gon equals to 2n. We can get them as follows. By rotating the figure n times by 360/n degrees each time, we get first n positions.
The open question: is 2n the maximum? We can prove that it is using proof to the contrary. Say we have a valid figure position not belonging to our 2n set. At least one of our n-gon corners should lay outside of the n-gon placeholder. This is because our 2n set covers all the cases where figure's corners lay inside the placeholder. However the situation of the corner laying outside the placeholder is impossible because the n-gon should belong to the placeholder and be equal to it as per the (1) clause supra.
Chapter 3. Why study groups?
Questions
Question 3.1. What is the real practical use of groups?
