4.5 Exercises#
4.5.1 Basics#
Exercise 4.1#
Consider the lightswitch group shown in Figure 2.8. Let \(L\) stand for the action of flipping the left switch and \(R\) stand for the action of flipping the right switch.
(a) Which of the following equations are true and which are false in this group?
\(LRRRR = RRL\)
True, cancel all the \(R\).
\(LR = RLRLRL\)
True, because the group is commutative.
\(L = RR\)
False
\(R^8 = R^{100}\)
True
(b) Let N stand for the non-action (leaving the switches untouched). Which of the following equations are true?
\({(LNR)}^2 = LNR\)
False
\(NN = N\)
True
\(RL = N\)
False
\(R^4 = N\)
True
\({(LNR)}^3 = R^3 L^3 \)
True
\(LRLR = N\)
True
(c) What is the smallest positive power of R that equals N ?
\(R^2\)
(d) What is the smallest positive power of L that equals N ?
\(L^2\)
(e) What is the smallest positive power of RL that equals N ?
\({(RL)}^2\)
(f) What is the smallest positive power of LR that equals N?
\({(LR)}^2\)
Exercise 4.2#
(a) Apply the transformation in Definition 4.1 to the lightswitch Cayley diagram in Figure 2.8.
(b) Create a multiplication table for the lightswitch group.
We’ll use a permutation library to avoid doing too much manual work on some of these questions. See Permutations - SymPy documentation and Permutations and Symmetric groups · AbstractAlgebra.jl for two options.
import numpy as np
from sympy.combinatorics import Permutation
e = Permutation([0, 1, 2, 3])
l = Permutation([2, 1, 0, 3]) # Left light switch
r = Permutation([0, 3, 2, 1]) # Right light switch
permutation = {
"E": e,
"L": l,
"R": r,
"LR": l*r,
}
action = {v: k for k, v in permutation.items()}
x = np.array(list(permutation.values()))
rank_v = np.vectorize(action.get)
actions = rank_v(x)
See also Broadcasting — NumPy Manual.
import pandas as pd
pd.DataFrame(rank_v(x[...,np.newaxis] * x), index=actions, columns=actions)
| E | L | R | LR | |
|---|---|---|---|---|
| E | E | L | R | LR |
| L | L | E | LR | R |
| R | R | LR | E | L |
| LR | LR | R | L | E |
Exercise 4.3#
Each part below describes a set with a binary operation on it. For each one, determine whether it is commutative and whether it is associative.
(a) the addition operation on the set of all whole numbers
Commutative, associative
(b) the subtraction operation on the set of all whole numbers
Not commutative, not associative
(c) the multiplication operation on the set of positive real numbers
Commutative, associative
(d) the division operation on the set of positive real numbers
Not commutative, not associative (try 2/3/2)
(e) the exponentiation operation on the set of positive whole numbers (that is, the operation written \(a^b\), but typed a^b on many calculators)
Not commutative, not associative (try 2^3^2)
4.5.2 Creating tables#
Exercise 4.4 (⚠)#
The Cayley diagrams for two groups are shown here, the cyclic group \(C_5\) on the left and the Quaternion group \(Q_4\) on the right.
See comments in the errata. The author’s replacement drawing strangely uses red for \(j\) and green for \(i\), which seems odd given that red is normally the first color in all these examples. We’ll using a variation on File:Cayley graph Q8.svg here and going forward, with green replaced with blue.
(a) The red arrow in the diagram for \(C_5\) represents multiplication by what element?
\(a\)
(b) What is \(a^3 · a\) in \(C_5\)?
\(a^4\)
(c) What is \(a^3 · a · a\) in \(C_5\)?
\(e\)
(d) If 1 is the identity element, then what do red arrows in the diagram for \(Q_4\) represent? What do the blue arrows represent?
\(i\) and \(j\)
(e) What is \(i^2\)? What is \(j·i\)?
\(-1\) and \(-k\)
(f) What is \(i·j·j\)?
\(-i\)
Exercise 4.5 (📑)#
Using the Cayley diagrams from Exercise 4.4, answer the following questions.
(a) How do you use the diagram of \(C_5\) to multiply \(x·a^2\) in \(C_5\), for any element \(x\)?
First you go to \(x\), then you follow two red arrows.
(b) How do you use the diagram of \(Q_4\) to multiply \(x·k\) in \(Q_4\), for any element \(x\)?
First you go to \(x\), then you follow a red and then a blue arrow (because \(k\) is equivalent to \(ij\)).
The author’s answer, based on the original/incorrect quaternion group drawing:
(a) Beginning at the element x in the diagram, follow a red arrow twice. Each red arrow represents one multiplication on the right by a, so this computes \(x · a · a\), or \(x · a^2\).
(b) From Exercise 4.4 we learned that \(k = j · i\), which is performed by following the \(j\) arrow (blue) and then the \(i\) arrow (red). So to multiply \(x · k\), begin at the node for \(x\) and follow a blue arrow and then a red one.
Exercise 4.6 (⚠)#
Create a multiplication table for each of the following Cayley diagrams.
(a) \(C_5\), as shown on the left of Exercise 4.4. Use the template given here.
import numpy as np
from sympy.combinatorics import Permutation
e = Permutation([0, 1, 2, 3, 4])
a = Permutation([4, 0, 1, 2, 3])
permutation = {
"e": e,
"a": a,
"a²": a*a,
"a³": a*a*a,
"a⁴": a*a*a*a,
}
action = {v: k for k, v in permutation.items()}
x = np.array(list(permutation.values()))
rank_v = np.vectorize(action.get)
actions = rank_v(x)
import pandas as pd
pd.DataFrame(rank_v(x[...,np.newaxis] * x), index=actions, columns=actions)
| e | a | a² | a³ | a⁴ | |
|---|---|---|---|---|---|
| e | e | a | a² | a³ | a⁴ |
| a | a | a² | a³ | a⁴ | e |
| a² | a² | a³ | a⁴ | e | a |
| a³ | a³ | a⁴ | e | a | a² |
| a⁴ | a⁴ | e | a | a² | a³ |
(b) \(Q_4\), the quaternion group with eight elements, as shown on the right of Exercise 4.4. Use the template given here.
See the multiplication tables in either Groupprops - Quaternion group or Quaternion group.
(c) \(A_4\), the alternating group with twelve elements:
Based on the errata we’ll inspect a different version of \(A_4\):
It’s not clear how the author intended readers to do this without a library; for a student to manually fill this 144-entry table would not be a good use of time.
from sympy.combinatorics.named_groups import AlternatingGroup
G = AlternatingGroup(4)
permutations = list(G.generate_dimino())
indexes = {perm: idx for idx, perm in enumerate(permutations)}
indexes
{Permutation(3): 0,
Permutation(3)(0, 1, 2): 1,
Permutation(3)(0, 2, 1): 2,
Permutation(1, 2, 3): 3,
Permutation(0, 1)(2, 3): 4,
Permutation(0, 2, 3): 5,
Permutation(0, 2)(1, 3): 6,
Permutation(1, 3, 2): 7,
Permutation(0, 1, 3): 8,
Permutation(0, 3, 1): 9,
Permutation(0, 3, 2): 10,
Permutation(0, 3)(1, 2): 11}
How do we relate these permutations to the names the author would like us to use? To start we’ll pick out some “natural” permutations to use for the generators, though these choices are somewhat arbitrary:
permutation = {
"e": permutations[0],
"x": permutations[4],
"z": permutations[6],
"a": permutations[1],
}
From the generators we should be able to define all other actions:
permutation["y"] = permutation["x"]*permutation["z"]
permutation["a²"] = permutation["a"]*permutation["a"]
permutation["b"] = permutation["x"]*permutation["a"]
permutation["b²"] = permutation["b"]*permutation["b"]
permutation["c"] = permutation["z"]*permutation["a"]
permutation["c²"] = permutation["c"]*permutation["c"]
permutation["d"] = permutation["y"]*permutation["a"]
permutation["d²"] = permutation["d"]*permutation["d"]
permutation
{'e': Permutation(3),
'x': Permutation(0, 1)(2, 3),
'z': Permutation(0, 2)(1, 3),
'a': Permutation(3)(0, 1, 2),
'y': Permutation(0, 3)(1, 2),
'a²': Permutation(3)(0, 2, 1),
'b': Permutation(0, 2, 3),
'b²': Permutation(0, 3, 2),
'c': Permutation(1, 3, 2),
'c²': Permutation(1, 2, 3),
'd': Permutation(0, 3, 1),
'd²': Permutation(0, 1, 3)}
import numpy as np
action = {v: k for k, v in permutation.items()}
name_v = np.vectorize(action.get)
x = np.array(list(permutation.values()))
import pandas as pd
import seaborn as sns
from sympy.combinatorics import Permutation
y = x[...,np.newaxis] * x
df = pd.DataFrame(name_v(y), index=name_v(x), columns=name_v(x))
index_v = np.vectorize(indexes.get)
cm = sns.color_palette("Paired", as_cmap=True)
df.style.background_gradient(axis=None, cmap=cm, gmap=index_v(y))
| e | x | z | a | y | a² | b | b² | c | c² | d | d² | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| e | e | x | z | a | y | a² | b | b² | c | c² | d | d² |
| x | x | e | y | b | z | c² | a | d² | d | a² | c | b² |
| z | z | y | e | c | x | d² | d | c² | a | b² | b | a² |
| a | a | c | d | a² | b | e | d² | x | b² | z | c² | y |
| y | y | z | x | d | e | b² | c | a² | b | d² | a | c² |
| a² | a² | b² | c² | e | d² | a | y | c | x | d | z | b |
| b | b | d | c | c² | a | x | b² | e | d² | y | a² | z |
| b² | b² | a² | d² | y | c² | d | e | b | z | a | x | c |
| c | c | a | b | d² | d | z | a² | y | c² | e | b² | x |
| c² | c² | d² | a² | x | b² | b | z | d | e | c | y | a |
| d | d | b | a | b² | c | y | c² | z | a² | x | d² | e |
| d² | d² | c² | b² | z | a² | c | x | a | y | b | e | d |
Exercise 4.7#
It is possible to suggest the full multiplication table for an infinite group by showing just part of it. Fill in the following partial table for the operation of addition on the set of all whole numbers; the ellipses indicate the table continues infinitely in all directions.
Exercise 4.8#
Exercises 2.4 through 2.8 of Chapter 2 asked you to draw Cayley diagrams for three groups. Use the diagrams you drew to make multiplication tables for those same groups. Note that if your diagram is not yet a diagram of actions, you may need to apply the transformation in Definition 4.1.
Here are possible answers for Exercise 2.4 through Exercise 2.7; see the next question for Exercise 2.8 (which is \(D_4\)).
Exercise 4.9#
Exercises 2.18 and 2.19 of Chapter 2 asked you to find the pattern describing the sequence of Cayley diagrams for the “n-gon puzzle.” I mentioned in that exercise that the family of groups describing such puzzles are called the dihedral groups. You will study them in detail in Chapter 5, and this exercise previews some of that material.
Find the pattern describing the sequence of multiplication tables for those same groups. You might consider the following steps.
(a) Create multiplication tables from the Cayley diagrams for triangle, square, and regular pentagon puzzles.
from sympy.combinatorics.named_groups import DihedralGroup
G = DihedralGroup(3)
permutations = list(G.generate_dimino())
indexes = {perm: idx for idx, perm in enumerate(permutations)}
indexes
{Permutation(2): 0,
Permutation(0, 1, 2): 1,
Permutation(0, 2, 1): 2,
Permutation(0, 2): 3,
Permutation(1, 2): 4,
Permutation(2)(0, 1): 5}
permutation = {
"e": permutations[0],
"r": permutations[1],
"f": permutations[3],
}
permutation["r²"] = permutation["r"]*permutation["r"]
permutation["rf"] = permutation["r"]*permutation["f"]
permutation["fr"] = permutation["f"]*permutation["r"]
permutation
{'e': Permutation(2),
'r': Permutation(0, 1, 2),
'f': Permutation(0, 2),
'r²': Permutation(0, 2, 1),
'rf': Permutation(2)(0, 1),
'fr': Permutation(1, 2)}
import numpy as np
action = {v: k for k, v in permutation.items()}
name_v = np.vectorize(action.get)
x = np.array(list(permutation.values()))
import pandas as pd
import seaborn as sns
from sympy.combinatorics import Permutation
y = x[...,np.newaxis] * x
df = pd.DataFrame(name_v(y), index=name_v(x), columns=name_v(x))
index_v = np.vectorize(indexes.get)
cm = sns.color_palette("Paired", as_cmap=True)
df.style.background_gradient(axis=None, cmap=cm, gmap=index_v(y))
| e | r | f | r² | rf | fr | |
|---|---|---|---|---|---|---|
| e | e | r | f | r² | rf | fr |
| r | r | r² | rf | e | fr | f |
| f | f | fr | e | rf | r² | r |
| r² | r² | e | fr | r | f | rf |
| rf | rf | f | r | fr | e | r² |
| fr | fr | rf | r² | f | r | e |
from sympy.combinatorics.named_groups import DihedralGroup
G = DihedralGroup(4)
permutations = list(G.generate_dimino())
indexes = {perm: idx for idx, perm in enumerate(permutations)}
indexes
{Permutation(3): 0,
Permutation(0, 1, 2, 3): 1,
Permutation(0, 2)(1, 3): 2,
Permutation(0, 3, 2, 1): 3,
Permutation(0, 3)(1, 2): 4,
Permutation(1, 3): 5,
Permutation(0, 1)(2, 3): 6,
Permutation(3)(0, 2): 7}
permutation = {
"e": permutations[0],
"r": permutations[1],
"f": permutations[4],
}
permutation["r²"] = permutation["r"]*permutation["r"]
permutation["r³"] = permutation["r"]*permutation["r"]*permutation["r"]
permutation["rf"] = permutation["r"]*permutation["f"]
permutation["fr"] = permutation["f"]*permutation["r"]
permutation["r²f"] = permutation["r"]*permutation["r"]*permutation["f"]
permutation
{'e': Permutation(3),
'r': Permutation(0, 1, 2, 3),
'f': Permutation(0, 3)(1, 2),
'r²': Permutation(0, 2)(1, 3),
'r³': Permutation(0, 3, 2, 1),
'rf': Permutation(3)(0, 2),
'fr': Permutation(1, 3),
'r²f': Permutation(0, 1)(2, 3)}
import numpy as np
action = {v: k for k, v in permutation.items()}
name_v = np.vectorize(action.get)
x = np.array(list(permutation.values()))
import pandas as pd
import seaborn as sns
from sympy.combinatorics import Permutation
y = x[...,np.newaxis] * x
df = pd.DataFrame(name_v(y), index=name_v(x), columns=name_v(x))
index_v = np.vectorize(indexes.get)
cm = sns.color_palette("Paired", as_cmap=True)
df.style.background_gradient(axis=None, cmap=cm, gmap=index_v(y))
| e | r | f | r² | r³ | rf | fr | r²f | |
|---|---|---|---|---|---|---|---|---|
| e | e | r | f | r² | r³ | rf | fr | r²f |
| r | r | r² | rf | r³ | e | r²f | f | fr |
| f | f | fr | e | r²f | rf | r³ | r | r² |
| r² | r² | r³ | r²f | e | r | fr | rf | f |
| r³ | r³ | e | fr | r | r² | f | r²f | rf |
| rf | rf | f | r | fr | r²f | e | r² | r³ |
| fr | fr | r²f | r³ | rf | f | r² | e | r |
| r²f | r²f | rf | r² | f | fr | r | r³ | e |
from sympy.combinatorics.named_groups import DihedralGroup
G = DihedralGroup(5)
permutations = list(G.generate_dimino())
indexes = {perm: idx for idx, perm in enumerate(permutations)}
indexes
{Permutation(4): 0,
Permutation(0, 1, 2, 3, 4): 1,
Permutation(0, 2, 4, 1, 3): 2,
Permutation(0, 3, 1, 4, 2): 3,
Permutation(0, 4, 3, 2, 1): 4,
Permutation(0, 4)(1, 3): 5,
Permutation(1, 4)(2, 3): 6,
Permutation(0, 1)(2, 4): 7,
Permutation(0, 2)(3, 4): 8,
Permutation(4)(0, 3)(1, 2): 9}
permutation = {
"e": permutations[0],
"r": permutations[1],
"f": permutations[5],
}
permutation["r²"] = permutation["r"]*permutation["r"]
permutation["r³"] = permutation["r"]*permutation["r"]*permutation["r"]
permutation["r⁴"] = permutation["r"]*permutation["r"]*permutation["r"]*permutation["r"]
permutation["rf"] = permutation["r"]*permutation["f"]
permutation["fr"] = permutation["f"]*permutation["r"]
permutation["r²f"] = permutation["r"]*permutation["r"]*permutation["f"]
permutation["fr²"] = permutation["f"]*permutation["r"]*permutation["r"]
permutation
{'e': Permutation(4),
'r': Permutation(0, 1, 2, 3, 4),
'f': Permutation(0, 4)(1, 3),
'r²': Permutation(0, 2, 4, 1, 3),
'r³': Permutation(0, 3, 1, 4, 2),
'r⁴': Permutation(0, 4, 3, 2, 1),
'rf': Permutation(4)(0, 3)(1, 2),
'fr': Permutation(1, 4)(2, 3),
'r²f': Permutation(0, 2)(3, 4),
'fr²': Permutation(0, 1)(2, 4)}
import numpy as np
action = {v: k for k, v in permutation.items()}
name_v = np.vectorize(action.get)
x = np.array(list(permutation.values()))
import pandas as pd
import seaborn as sns
from sympy.combinatorics import Permutation
y = x[...,np.newaxis] * x
df = pd.DataFrame(name_v(y), index=name_v(x), columns=name_v(x))
index_v = np.vectorize(indexes.get)
cm = sns.color_palette("Paired", as_cmap=True)
df.style.background_gradient(axis=None, cmap=cm, gmap=index_v(y))
| e | r | f | r² | r³ | r⁴ | rf | fr | r²f | fr² | |
|---|---|---|---|---|---|---|---|---|---|---|
| e | e | r | f | r² | r³ | r⁴ | rf | fr | r²f | fr² |
| r | r | r² | rf | r³ | r⁴ | e | r²f | f | fr² | fr |
| f | f | fr | e | fr² | r²f | rf | r⁴ | r | r³ | r² |
| r² | r² | r³ | r²f | r⁴ | e | r | fr² | rf | fr | f |
| r³ | r³ | r⁴ | fr² | e | r | r² | fr | r²f | f | rf |
| r⁴ | r⁴ | e | fr | r | r² | r³ | f | fr² | rf | r²f |
| rf | rf | f | r | fr | fr² | r²f | e | r² | r⁴ | r³ |
| fr | fr | fr² | r⁴ | r²f | rf | f | r³ | e | r² | r |
| r²f | r²f | rf | r² | f | fr | fr² | r | r³ | e | r⁴ |
| fr² | fr² | r²f | r³ | rf | f | fr | r² | r⁴ | r | e |
(b) Discern a pattern and describe it. This will be your conjecture about n-gons for n > 5.
Each dihedral group has a “sub-multiplication table” within each of the four quadrants of the table.
(c) Return to the group library in Group Explorer and investigate the same groups as in Exercise 2.19. (If you do not remember which ones they are, you can use the search feature again and look up “triangle,” “square,” etc.)
(i) Do your multiplication tables from part (a) agree with those in Group Explorer? Note that Group Explorer may have used different names for the elements of the group than you did, and may have chosen a different order for the rows and columns, but the pattern in the table should be the same. You can rename elements and reorder the rows and columns in Group Explorer’s multiplication tables to help with the comparison.
Yes, they seem to match.
(ii) Does your conjecture about the pattern of multiplication tables for n-gons with n > 5 hold up against all the data you can find in Group Explorer? (This includes groups other than the three you just examined.)
Yes, there are similar patterns in those tables.
(d) Can you give a convincing reason why the conjecture you made ought to be true?
In the top-left quadrant we have the table for when we never flip the \(n\)-gon (limit ourselves to rotations, this is essentially the table for a cyclic group). The bottom-left and top-right quadrants are associated with a single flip, and the bottom-right with two flips.
4.5.3 Almost tables#
Exercise 4.10 (📑)#
Consider the following multiplication table that displays a binary operation.
(a) Explain succinctly why the binary operation is not associative. Can you write your answer as one equation?
We could directly search for a counter-example, but we’ll use Light’s associativity test to generate more than one counterexample. The two tables produced by the test process:
We can see the tables disagree on two cells, corresponding to:
The author’s answer:
Hint: Check associativity of \(A·A·B\).
This answer is fine, but it takes as an assumption that \(A ≠ B\). If we let \(A = B\) then this table (redundantly) represents a group with only 2 distinct elements (\(e\) and \(A = B\)).
(b) Does the operation have inverses?
Yes, each element is its own inverse, and \(A\) and \(B\) are also inverses of each other. Notice that \(e\) shows up twice in the row for \(A\), meaning we can conclude:
Lacking associativity, nothing about the previous statement can be reduced and there’s little we can do to manipulate it further in an interesting way. If we assume associativity, this leads to \(A = B\).
Assuming \(A ≠ B\) we can’t even call this algebraic structure a Quasigroup because it doesn’t obey the Latin square property.
Exercise 4.11#
Consider the following multiplication table that displays a binary operation.
(a) Explain succinctly why the binary operation does not have inverses. Can you write your answer as one equation?
See Inverse element; we can’t have inverses without an identity (or identities). Since this operation is total, we can have only identity and in this cases it’s \(3\) because it is the only element where the row and column associated with it equals the row and column labels. We don’t have all inverses, however, because \(2\) does not have one. We can see \(2\) doesn’t have an inverse because there’s no element in the row/column associated with this element that’s equal to \(3\) (similarly, it’s quick to see that \(1\) doesn’t have an inverse).
(b) Is the operation associative?
An operation is associative if a term reduces to the same regardless of where you put parentheses. If any term based on this algebra has a \(1\) in it, then the term will be a \(1\) regardless of the placement of parentheses. Similarly, if it has a \(2\) in it then it will be a \(2\) and if it only has \(1\) in it it’ll reduce to \(1\) (again, regardless of parentheses). Since parentheses don’t matter, this table is associative.
We’d call this algebraic structure a Monoid (because it has associativity and identity, but not invertibility), specifically a commutative monoid.
Exercise 4.12#
Consider the following multiplication table that displays a binary operation.
(a) Does this operation have inverses? Justify your answer.
The identity is clearly \(1\), using similar reasoning to the last question. It doesn’t have inverses because e.g. there’s no \(1\) in the row/column for \(x\).
(b) Is the operation associative? Justify your answer.
Yes, because terms will evaluate the same regardless of parentheses. If a term has a \(y\) it will always reduce to a \(y\). Otherwise, a term has a single \(x\) and only \(1\) it will reduce to \(x\); if it has two \(x\) and only \(1\) it will reduce to \(y\). Otherwise, the term will reduce to \(1\).
We’d call this algebraic structure a Monoid (because it has associativity and identity, but not invertibility), specifically a commutative monoid.
Exercise 4.13 (📑)#
For each multiplication table below, explain why it does not depict a group.
Notice two \(3\) in the row for \(3\), implying it has two inverses (which should be unique). That row is specifically claiming there are two identities:
We know we can’t have two identities, and we specifically know that \(4\) is not an identity because the row/column associated with it is not equal the identity permutation. Therefore we can use the left inverse of \(3\) to come up with a contradiction based on it:
That is, the algebra/table is not associative (we can change the result based on where we put parentheses).
Here’s an alternative approach. Assuming associativity and using the row for \(4\), we would similarly conclude that \(1 = 3\):
The rows/columns for these two elements are clearly different, so we should question the assumption of associativity. Indeed, we can verify it doesn’t hold in one of the places we assumed it:
The author’s answer:
The operator is not associative, as the following computation demonstrates:
\(4·(3·2) = 4·1 = 2 ≠ 4 = 2·2 = (4·3)·2\)
It does not have inverses; notice the row for \(a\) does not have an \(e\) in it.
Notice two \(b\) in the row for \(b\), implying it has two inverses (which should be unique). Based on logic similar to above we can find a counterexample to the claim of associativity:
It lacks an identity.
Exercise 4.14 (📑)#
The following multiplication table does not depict a binary operation on the set \(\{e, x, y\}\). The reason is part of the definition of a binary operation; we would say that this binary operation lacks closure. Can you spot the problem and explain it in your own words?
The \(s\) entry is not an element of \(\{e,x,y\}\).
The author’s answer:
The element \(s\) appears in the table, but is not in the row or column headings. Is it in the group or isn’t it?
Exercise 4.15#
Why can the same element not appear twice in any row of a group’s multiplication table? Does this restriction also apply to columns?
Let’s say the row \(a\) contained two elements \(x\) and \(y\) that both equal some third element \(z\):
Assuming inverses and associativity, we could conclude:
This would require us to conclude that \(x = y\), which is typically not going to be possible. We must more likely give up either the assumption of (1) inverses or (2) associativity; but to give up either would be to concede that we’re not looking at a group. Notice we’re trying to avoid an appeal to the Law of excluded middle.
A similar argument would apply to columns.
Exercise 4.16#
Exercises 2.14 through 2.17 on page 24 asked you to translate the rules from Definition 1.9 into criteria about diagrams. The goal was to create criteria for judging whether a diagram was a Cayley diagram - i.e., whether it represented a group.
This exercise will show that the answers to Exercises 2.14 through 2.17 are not sufficiently restrictive. That is, there are diagrams that satisfy those criteria but are not Cayley diagrams for any group. Consider the two diagrams shown below, neither of which is a valid Cayley diagram.
(a) Does each diagram meet all the criteria that were your answers to Exercises 2.14 through 2.17?
There’s a predefined list of 2 generators (red and blue, which we’ll call \(a\) and \(b\)).
Every action can be undone in one way or another. Every generator comes into every node, so it can in theory be followed backwards assuming inverses.
There’s no sense of probability or chance in the actions.
The two generators are available coming out of every node.
(b) Try to convert each of these diagrams into a multiplication table. What problem arises in each case?
How should we choose what element to label \(e\) in the diagrams above, and on unlabeled Cayley diagrams in general? There’s no rule regarding which element to label as the identity, so ultimately this must be an arbitrary choice. In this sense a group has no “bottom” on which all other elements rest, because with a different selection the labels would have all ended up different but you’d still have the “same” group (really, an isomorphic group). Let’s put \(e\) in the top left (reading order) and see what we come up with for both diagrams:
In both these examples we run into an issue with the same element appearing twice on one row:
As discussed in Exercise 4.15 this implies we’ve made an incorrect assumption somewhere. If we assume we have inverses and associativity, then we’ll find that we don’t have distinct elements:
Since actions are equivalent to elements, another way to put this is that we don’t have distinct actions. That is, what \(e\) does (as an action) is sometimes the same as what \(a²\) does (as an action) and sometimes not. That is, in some places in the second diagram we have \(a²\) acting as an identity, and in other places (namely, starting from \(e\)) it doesn’t.
(c) Can you explain what is wrong with these diagrams that caused the problems you encountered in part (b)?
In short, these diagrams are not symmetrical. We should be able to put \(e\) on any node in the diagram and get the same list of actions. Consider for example the Symmetric group S₃, another version of which you can find in Cayley Diagram for S³. With the second version’s generators, notice that \(frf = r^2 = r^{-1}\) no matter where you start from, i.e. where you put \(e\). With the first version’s generators, you should similarly see that it’s always the case that \(aba = bab\).
Another way to put this is that what actions are equivalent should not be stateful i.e. depend on your current location on the map. If you discover that \(ab = ba\) in one part of a diagram (i.e. with a particular selection of \(e\)), it should also be the case that \(ab = ba\) in another part of the diagram (i.e. with another selection of \(e\)). If we call the node representing the second selection of \(e\) something like \(c\), then we’re saying it should be the case that \(cab = cba\). That is, we should be able to left-multiply and get another true statement.
It may help to rely on your sense of symmetry to quickly show that a particular diagram does not represent group. For example, we can see that moving \(e\) down to \(b\) in the left example won’t help show that \(ab ≠ ba\) because the diagram has reflectional symmetry in that direction. If we instead move \(e\) to \(a\) then we’ll be able to show that \(ab ≠ ba\) starting from that new position.
(d) Create another diagram satisfying the criteria of Exercises 2.14 through Exercises 2.17, yet having the same problem as the two diagrams above.
Although we informally specified that groups that are “non-symmetrical” will fail to satisfy all the axioms of the group, it’s not hard to accidentally draw what is really a group in a non-symmetrical way. Consider the following example; the non-symmetrical Cayley diagram on the left is actually hiding \(Z_4\):
If we allow self-loops (i.e. competing identities) then we can create a rather minimal example of a Cayley diagram satisyfing the 4 action-based requirements that also does not represent a group:
We show the action of \(e\) on all the nodes for completeness (in green). We clearly have that \(ae = ab\), which assuming inverses implies \(e = b\) (a competing identity). In fact this equation is not universal in the diagram; starting from \(e\) we have that \(e ≠ b\).
An arguably more interesting example without self-loops:
This exercise shows a slight discrepancy between the actions-based definition of group (Definition 1.9, illustrated using Cayley diagrams) and my algebraic one (Definition 4.2, illustrated using multiplication tables). This discrepancy will be cleared up in Section 6.1.
Exercise 4.18 (⚠, 📑)#
The errata suggests working on 4.18 before 4.17:
These exercises should be in the other order, since 4.18 asks you why there is only one identity element in a group, and the answer to 4.17 requires you to use the fact that there is only one identity element in a group.
When creating a multiplication table for a group, if you try to include two different identity elements, what goes wrong? What does this lead you to conclude about groups?
If you have two columns that are both for identity elements \(e\) and \(f\), then in every row you’ll repeat the elements in those two columns. For example, in the row for \(a\) you’ll have entries for \(ae\) and \(af\), which will both be equal \(a\). If \(ae = af\) then \(e = f\) given invertibility.
The author’s answer:
It leads you to conclude that a group can have only one identity element.
Exercise 4.17 (⚠, 📑)#
Explain why a Cayley diagram must be connected. That is, why must there be a path from every node to every other node?
There should be at least one path to every node \(a\) from the starting node, or the node \(a\) wouldn’t be a part of the group. If there’s a path from the starting node to every node \(a\) then one could also take the inverse \(a^{-1}\) to get back to the starting node and then to any other node \(b\).
The author’s answer:
Hint: It may help to consider a specific example. Why can the following two-piece diagram not be viewed as one Cayley diagram for an eight-element group? Which part of Definition 4.2 would be violated?
(Note that you could add arrows to make it a Cayley diagram, but as is, it is not one.)
Consider part 3. of the definition, which requires that \(eg = g\) for every element in the group. One can read this as saying that every element is both an action and an element; it’s an action that takes the current state (system state, i.e. the argument to \(g\)) from the starting node \(e\) to the named node (element) \(g\). If we take \(a\) as the identity element in the Cayley diagram above, there’s no action to get to e.g. \(f\) (so it’s only an element, not an action that’s always available). We interpret “action” to mean an active transformation in the sense of Active and passive transformation.
This makes “travel” in a Cayley diagram for a group easy if you know the name of where you want to go relative to the starting point; you can always take the inverse of your current location and then the action \(g\) to get to the node \(g\).
4.5.4 Small groups#
Exercise 4.19#
Complete each of the following multiplication tables so that it depicts a group. There is only one way to do so, if we require that 0 be the identity element in each table. Then search Group Explorer’s group library to determine the names for the groups the tables represent.
pd.DataFrame([
[0, 1],
[1, 0],
], index=[0, 1], columns=[0, 1])
| 0 | 1 | |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
See Group Explorer · Z₂.
pd.DataFrame([
[0, 1, 2],
[1, 2, 0],
[2, 0, 1],
], index=[0, 1, 2], columns=[0, 1, 2])
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 0 |
| 2 | 2 | 0 | 1 |
See Group Explorer · Z₃.
pd.DataFrame([
[0],
], index=[0], columns=[0])
| 0 | |
|---|---|
| 0 | 0 |
See Group Explorer · Z₁.
pd.DataFrame([
[0, 1, 2, 3],
[1, 2, 3, 0],
[2, 3, 0, 1],
[3, 0, 1, 2],
], index=[0, 1, 2, 3], columns=[0, 1, 2, 3])
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 2 | 3 | 0 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 0 | 1 | 2 |
See Group Explorer · Z₄.
pd.DataFrame([
[0, 1, 2, 3],
[1, 3, 0, 2],
[2, 0, 3, 1],
[3, 2, 1, 0],
], index=[0, 1, 2, 3], columns=[0, 1, 2, 3])
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 3 | 0 | 2 |
| 2 | 2 | 0 | 3 | 1 |
| 3 | 3 | 2 | 1 | 0 |
See Group Explorer · Z₄ with:
\(0 = e\)
\(1 = a\)
\(3 = a²\)
\(2 = a³\)
Shift-click on columns in Group Explorer to move them and make the multiplication tables match.
The author’s answer:
Hint: For this exercise and those that follow it, use the fact from Exercise 4.15 liberally.
Exercise 4.20#
The following table can be completed in more than one way, and still have the result depict a group. Find all possible such completions of the table, again using 0 as the identity element. How many did you find? Search Group Explorer’s group library to determine the names for the groups each of your resulting tables represents.
pd.DataFrame([
[0, 1, 2, 3],
[1, 0, 3, 2],
[2, 3, 0, 1],
[3, 2, 1, 0],
], index=[0, 1, 2, 3], columns=[0, 1, 2, 3])
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 0 | 3 | 2 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 2 | 1 | 0 |
See Group Explorer · V₄ with:
\(0 = e\)
\(1 = h\)
\(3 = v\)
\(2 = hv\)
pd.DataFrame([
[0, 1, 2, 3],
[1, 0, 3, 2],
[2, 3, 1, 0],
[3, 2, 0, 1],
], index=[0, 1, 2, 3], columns=[0, 1, 2, 3])
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 0 | 3 | 2 |
| 2 | 2 | 3 | 1 | 0 |
| 3 | 3 | 2 | 0 | 1 |
See Group Explorer · Z₄ with:
\(0 = e\)
\(1 = a²\)
\(2 = a\)
\(3 = a³\)
Exercise 4.21#
From Exercise 4.19 part (a) you can conclude that there is only one pattern for a group containing two elements. This is because the only difference between the multiplication table you computed and that of any other group with two elements will be the names of those elements. So the pattern of interactions among elements (or colors if we were to color the cells of the table) would be no different. (a) How many patterns are there for groups containing three elements?
One, for the same reasons.
(b) Containing one element?
One, for the same reasons.
(c) Containing four elements?
Two, based on the last two parts of Exercise 4.19 and Exercise 4.20.
Chapter 9 attacks the general question, “How many groups there are with n elements?”
4.5.5 Table patterns#
These exercises preview Section 5.2, about an important family of groups called the abelian groups.
Exercise 4.22 (📑)#
We saw earlier in this chapter that in the group \(V_4\), the equation \(RB = BR\) is true. In fact, for any two elements \(a, b ∈ V_4\), the equation \(ab = ba\) is true. That is, the order in which you combine elements does not matter. Consider each group whose multiplication table appears in Figure 4.7 (except \(A_5\), whose details are too small to see). For which of those groups does the order of combining elements matter?
The symmetric group \(S_3\) and the quasihedral group with 16 elements.
The author’s answer:
Order matters in \(S_3\), and the two groups shown in the bottom row, but order does not matter in the other three groups shown in that figure.
Exercise 4.23 (📑)#
Groups in which the order of multiplication of elements does not matter are called commutative or abelian. Look through the groups in Group Explorer’s group library, starting with the smallest, until you find one that is noncommutative. What is the name of the smallest noncommutative group?
The symmetric group \(S_3\).
Exercise 4.24 (📑)#
What visual pattern do the multiplication tables of commutative groups exhibit?
The colors reflect across the diagonal.
4.5.6 Algebra#
Exercise 4.25#
To go along with the other algebraic notation we’ve seen in this chapter, there is also an algebraic notation for generators. For instance, the group \(C_5\), which appears in the first few exercises of this chapter, is generated by the element \(a\). The standard notation for this is \(C_5 = 〈a〉\). The 〈a〉 means “what you can generate from a,” and so the equation \(C_5 = 〈a〉\) is saying \(C_5\) is the group generated from a.” From Figure 4.3, we can write \(V_4 = 〈R, B〉\), saying that \(R\) and \(B\) together generate \(V_4\).
Show your understanding of this new notation by filling in the blanks below using however many elements are necessary to generate the group. Use as few elements as possible.
(a) From the Cayley diagram in Exercise 4.4, we see that \(Q_4 = 〈 \underline{ } 〉\)
\(Q_4 = 〈i,j〉\)
(b) From the Cayley diagram in part (c) of Exercise 4.6, we see that \(A_4 = 〈\underline{ }〉\).
\(A_4 = 〈 a,x 〉\)
(c) There is more than one way to generate most groups. Find a different (yet still correct) answer to each of the previous two questions.
\(Q_4 = 〈i,k〉\) because \(k = ji\) so that \(j = ki^{-1}\).
\(A_4 = 〈 a²,x 〉\) because \(a² = aa\) so that \(a = a²a^{-1}\).
Exercise 4.26 (⚠, 📑)#
Use the multiplication tables you constructed in Exercise 4.6 to determine the inverses for each element of each of the three groups from that problem.
(a) In the cyclic group \(C_5\), the inverses are:
(b) In the quaternion group \(Q_4\), the inverses are:
See the multiplication table in Quaternion group, where what the author calls \(Q_4\) is called \(Q_8\).
(c) In the alternating group \(A_4\), the inverses are:
Skipping; this answer would be straightforward but time-consuming.
(d) In general, how do you use a multiplication table to find an element’s inverse?
You take the name of the column where the element’s value is \(e\). In a Cayley diagram, you follow the associated inverse arrow(s) in the reverse order (e.g. the inverse of \(fr\) is \(r^{-1}f^{-1}\)).
Exercise 4.27 (📑)#
Inverses can be used to solve equations. In the group \(C_5\), to solve \(a²x = a\) for x, I can proceed as in high school algebra:
\[\begin{split} \begin{align} a²x &= a \\ (a²)^{-1}a²x &= (a²)^{-1}a \\ x &= (a²)^{-1}a \\ x &= a^4 \end{align} \end{split}\]Computing \((a²)^{-1}a\) in \(C_5\) gives \(x = a^4\).
Try solving each of these equations in \(C_5\).
(a) \(a^3 x = a^2\)
(b) \(a^4 a^2 x = a\)
(c) \(a x (a^3)^{-1} = e\)
Exercise 4.28 (⚠)#
(a) If I have the equation \(a^2 x (a^2)^{-1} = a\) to solve as in the previous exercise, can I cancel the \(a²\) and the \((a^2)^{-1}\)? Why or why not? (Hint: Is the result you get by canceling actually a solution to the equation?)
Yes, because the group is abelian.
(b) If I have a similar equation, but in the group \(Q_4\) from Exercise 4.6, \(ixi^{-1} = j\), can I cancel the \(i\) and \(i^{-1}\)? Why or why not?
No, because the group is not abelian.
(c) Your answers to parts (a) and (b) should be different. What makes them different? Hint: Apply what you learned from the exercises in Section 4.5.5.
From the errata:
The exercise attempts to show a difference between abelian and nonabelian groups, but fails in the following way. In part (a), one can cancel a² and (a²)⁻¹ despite the x between them because the group C₅ is abelian; this part of the exercise is correct. In part (b), the group is Q₄, a nonabelian group, and in general it is not acceptable in nonabelian groups to rearrange elements to permit cancelling. However, in this case, the example chosen was a poor example, because the solution to part (b) is x = j, which one could obtain by naively canceling the i and i⁻¹. Although this strategy does not work in every nonabelian example, it works in this one.
A correct version of the exercise would use a different example for part (b), such as the equation a² x (a²)⁻¹ = d in the group A₄ from page 54. The solution would be x = b, which we would not get through naive cancelling. If we attempted to cancel the a² with (a²)⁻¹, we would find x = d instead, which is incorrect.
Exercise 4.29 (⚠)#
Premultiply by b₁’s inverse and postmultiply by a₂’s inverse.
Exercise 4.30 (⚠)#
Solve these equations for t. (a) In Q₄, \(jitk⁻¹ = -kj\)
\(i⁻¹j⁻¹jitk⁻¹k = i⁻¹j⁻¹(-k)jk = t = (-i)(-j)(-k)jk = (-k)(-k)(-i) = i\)
(b) In A₄, \(t(b₂)² = xyz\)
Skipping because these symbols don’t match the A₄ symbols; see errata.
(c) In S₃, \(rtf = e\)
Exercise 4.31#
Let’s say you have a group G with identity element e. Take any three elements a, b, and c in G.
(a) What does the equation ab = e say about the relationship between a and b?
It implies they are inverses of one another.
(b) If both ab = e and ac = e, can you use algebra to show that b = c?
We have ab = ac = e from the two equations. Premultiply by the inverse of a to show this implies b = c.
(c) Can an element in a group have two different inverses?
No
Exercise 4.32 (📑)#
The set of integers (all positive and negative whole numbers, and zero) is often written as ℤ. Use Definition 4.2 to answer each of the following questions about ℤ.
(a) Is it a group using ordinary addition as the operation?
Yes: It’s closed, associative, has an identity element (0), and every element has an inverse.
(b) Is it a group using ordinary multiplication as the operation?
No: Assume an identity element of 1. Every element does not have an inverse. For example, 3 does not have an inverse (you’d need to use 1/3 which is a rational).
(c) Are the even integers a group using ordinary addition as the operation?
Yes, still using 0 as the identity element.
(d) The even integers are sometimes written 2ℤ, because they can be obtained by multiplying every integer by 2. If we think of 3ℤ, 4ℤ, and in general any nℤ in the same way, for what integers n is the set nℤ a group using ordinary addition as the operation?
Any integer n should still describe a group.
Exercise 4.33 (📑)#
The rational numbers (often written ℚ) are the set of fractions \(\frac{a}{b}\), where a and b are integers (but b ≠ 0). For example, \(\frac{1}{2}\), \(\frac{-6}{11}\), and \(\frac{50}{3}\) are all rational. Any integer, including zero, is rational, because you can just divide it by 1. For example, 10 is the rational number \(\frac{10}{1}\).
Use Definition 4.2 to answer each of the following questions about ℚ.
(a) Is it a group using ordinary addition as the operation?
Yes: It’s closed, associative, has an identity element (0), and every element has an inverse.
(b) Is it a group using ordinary multiplication as the operation?
Almost: It’s closed, associative, has an identity element (1), and almost every element has an inverse (the reciprocal). Zero does not have a reciprocal.
(c) Call ℚ⁺ the positive rational numbers (only those greater than zero). Is ℚ⁺ a group under ordinary addition?
No, it doesn’t have an identity element.
(d) Is ℚ⁺ a group under ordinary multiplication?
Yes: It’s closed, associative, has an identity element (1), and every element has an inverse (the reciprocal).
(e) Call ℚ* the nonzero rational numbers (all positive and negative ones, only leaving out zero). Is ℚ* a group under ordinary addition?
No, it doesn’t have an identity element.
(f) Is ℚ* a group under ordinary multiplication?
Yes: It’s closed, associative, has an identity element (1), and every element has an inverse (the reciprocal).
(g) Why are groups like ℚ, ℚ⁺, and ℚ* difficult to visualize using multiplication tables and Cayley diagrams?
It’s hard to know what part of them to show since they’re infinite in two directions, both the numerator and the denominator. Besides that, they have have “holes” for irrational numbers like π (see Compact space) which will not be consistent or symmetric (will appear almost random).