Q: “What’s commutative and purple?”
A: “An abelian grape”.
– Ancient Math Joke“In 1910 the mathematician Oswald Veblen and the physicist James Jeans were discussing the reform of the mathematical curriculum at Princeton University. `We may as well cut out group theory,` said Jeans. `That is a subject which will never be of any use to physics.` It is not recorded whether Veblen disputed Jeans’ point, or whether he argued for the retention of group theory on purely mathematical grounds. All we know is that group theory continued to be taught. And Veblen’s disregard for Jeans’ advice continued to be of some importance to the history of science at Princeton. By the irony of fate group theory later grew into one of the central themes of physics, and it still dominates the thinking of all of us who are struggling to understand the fundamental particles of nature.”
Freeman J. Dyson
SCIENTIFIC AMERICAN, Sep, 1964
GROUPS, I
Let X be any finite set and let S_X denote the set of all permutations of X onto itself:
S_X = { f : X -> X | f is a bijection }.
This set has the following properties:
(1) if f, g belong to S_X then fg (the composition of these permutations) also belongs to S_X,
(2) if f, g, h all belong to S_X then (fg)h = f(gh), (“associativity“),
(3) the identity permutation I : X -> X, I(x) = x for all x in X, belongs to S_X (“existence of the identity“),
(4) if f belongs to S_X then the inverse permutation f^(-1) of X also belongs to S_X (“existence of the inverse“).
The set S_X is called the symmetric group of X. We shall usually take for the set X a set of the form {1, 2, …, n}, in which case we shall denote the symmetric group by Sn. This group is also called the “symmetric group on n letters.
Example: Suppose X = {1,2,3}. We can describe S_X as
S_X = { I, s1=(1, 2), s2=(2, 3), s3=(1, 3, 2),
s4=(1, 2 ,3), s5=(1, 3)},
written in cycle notation. The multiplication table is
| I s1 s2 s3 s4 s5
---------------------------------------
I | I s1 s2 s3 s4 s5
|
s1 | s1 I s3 s2 s5 s4
|
s2 | s2 s4 I s5 s1 s3
|
s3 | s3 s5 s1 s4 I s2
|
s4 | s4 s2 s5 I s3 s1
|
s5 | s5 s3 s4 s1 s2 I
Exercise: Verify the four properties of S_X mentioned above in the case of the above example. Note that associativity follows from the associative property of the composition of functions.
We take these four properties as the four defining properties of a group:
Definition: Let G be a set and suppose that there is a function
* : GxG --> G
(g1,g2) |---> g1*g2
(called the group’s “operation”) satisfying
(G1) if g1, g2 belong to G thn g1*g2 belongs to G (“G is closed under *”),
(G2) if g1, g2, g3 belong to G then (g1*g2)*g3 = g1*(g2*g3) (“associativity”),
(G3) there is an element 1 in G such that 1*g = g*1 = g for all g in G (“existence of an identity”),
(G4) if g belongs to G then there is an element g^(-1) in G such that g*g^(-1) = g^(-1)*g = 1.
Then G (along with the operation *) is a group.
Definition: Let g and h be two elements of a group G. We say that g commutes with h (or we say that “g, h commute”) if g*h = h*g. We call a group abelian (or commutative) if every pair of elements g, h belonging to G commute. If G is a group for which there exists some pair g,h in G which do not commute then we call G nonabelian or noncommutative.
Example: The integers, with ordinary addition as the group operation, is an abelian group.
Exercise: Show that any group having exactly 2 elements is abelian.
Now the reader should understand the punchline to the joke quoted at the beginning!
Convention: When dealing with groups in general we often drop the * and denote multiplication simply by juxtaposition (that is, sometimes we write gh in place of g*h), with one exception. If the group G is abelian then one often replaces * by + and then + is NOT dropped.
Now that we know the definition of a group, the question arises: how might they be described? The simplest answer is that we describe a group much as we might describe a set: we could list all its elements and give the multiplication table or we could describe all its elements and their multiplication in terms of some property from which we can verify the four properties of group. Though the first way has the distinct advantage of being explicit, it is this second alternative which is the most common since it is usually more concise.
Our objective is to introduce terminology and techniques which enable us to analyse mathematically permutation puzzles. The type of groups which arise in this context are defined next.
Definition: Let X be a finite set. Let g1, g2, …, gn be a finite set of permutations of X. Let G be the set of all possible products of the form
g = x1*x2...*xm, m>0,
where each of the x1, …, xm is taken from the set {g1, g1^(-1), …, gn, gn^(-1)}. The set G, together with the group operation given by composition of permutations, is called a permutation group with generators g1, …, gn. We sometimes write
G = <g1, ..., gn> subset S_X.
Remark: The above definition can be generalized: Replace S_X by any group S which includes all the generators g1, …, gn. The resulting set G is called the group generated by the elements g1, …, gn.
Algorithm:
Input: The generators g1, ..., gn (as permutations in S_X),
Output: The elements of G
S = {g1, ..., gn, g1^(-1), ..., gn^(-1) },
L = S union {1}
for g in S do
for h in L do
if g*h not in L then L = L union {g*h} endif
endfor
endfor
Note that the size of the list L in the for loop changes after each iteration of the loop. The meaning of this is that the if-then command is to be executed exactly once for each element of the list.
Exercise: Verify that a permutation group G satisfies the four properties of a group (G1)-(G4).
Definition: If G is a group then the order of G, denoted |G|, is the number of elements of G. If g is an element of the group G then the order of g, denoted ord(g), is the smallest positive integer m such that g^m=1, if it exists. If such an integer m does not exist then we say that g has infinite order.
Exercise: Let X = {1,2,3}. Recall s1=(1, 2), s2=(2, 3), s3=(1, 3, 2), s4=(1, 2, 3), s5=(1, 3).
(a) Let G be the permutation group with generator s1, G = <s1>
What is the order of G?
(b) What is the order of s5?
(c) Let G be the permutation group with generator s3, G = <s3>.
What is the order of G?
(d) Find the order of s4.
(e) Show that S_X = <s1,s2>.
If G is a permutation group G with only one generator then we say that G is cyclic.
Lemma: If G = is cyclic with generator g then |G|=ord(g).
proof: Let m=ord(g), so g^m = 1. We can list all the elements of G as follows:
1, g, g^2, ..., g^(m-1).
There are m elements in this list (we can prove this by contradiction: if not then g^j=g^k, some j < k in between 0 and m-1, which implies g^(k-j)=1, so 0<ord(g)=k-j<m, a contradiction). QED
Definition: Let G be a group. A subgroup of G is a subset H of G such that H, together with the operation * inherited as a subset of G, satisfies the group operations (G1)-(G4)
(with G replaced by H everywhere).
Notation: If G is a group then we will denote the statement “H is a subgroup of G” by “H < G”.
Example: A permutation group G generated by elements g1, …, gn belonging to S_X is a subgroup of S_X, i.e., G < S_X.
Commutators
Definition: If g, h are two elements of a group G then we call the element
[g,h] = g*h*g^(-1)*h^(-1)
then commutator of g,h.
Not that [g,h]=1 if and only if g,h commute. Thus the commutator may be regarded as a rough measurement of the lack of commutativity.
Exercise: Let G = S3, the symmetric group on 3 letters. Compute [s1,s2], [s2,s1].
Exercise (requires a Rubik’s cube): Let R, U be the Rubik’s cube moves introduced previously. Determine the order of the move [R,U].
(Ans: 6)
Definition (Singmaster): Let G be the permutation group generated by the permutations R, L, U, D, F, B regarded as permutations in S54. The “Y commutator” is the element
[F,R^(-1)] = F*R^(-1)*F^(-1)*R .
The “Z commutator” is the element
[F,R] = F*R*F^(-1)*R^(-1) .
Exercise: Find the orders of the Y commutator and the Z commutator.
Definition: Let G be any group. The group G’ generated by all the commutators
{ [g,h] | g, h belong to G }
This is called the commutator subgroup of G.
This group may be regarded as a rough measurement of the lack of commutativity of the group G.
Remark: We will see later that the group generated by the basic moves of the Rubik’s cube – R, L, U, D, F, B – has a relatively large commutator subgroup. In other words, roughly speaking “most” moves of the Rubik’s cube can be generated by commutators such as the Y commutator or the Z commutator.
Conjugation
Definition: If g, h are two elements of a group G then we call the element
g^h = g*h*g^(-1)
then conjugation of h by g.
Not that g^h=1 if and only if g,h commute. Thus the conjugates may be regarded as a rough measurement of the lack of commutativity.
Exercise: Show [g,h]*h = h*g.
Exercise: Let G = S3, the symmetric group on 3 letters. Compute s1^s2, s2^s1.
Exercise (requires a Rubik’s cube): Let R, U be the Rubik’s cube moves introduced previously. Determine the order of the move R^U. (Ans: 4)
Definition: We say two elements g1, g2 of G are conjugate if there is an element h in G such that g2=g1^h.
Exercise: Show that the notion of conjugate defines an equivalence relation. That is, show that
(a) any element g in G is conjugate to itself (“reflexive”),
(b) if g is conjugate to h (g,h belonging to G) then h is conjugate to g (“symmetry”),
(c) if g1 is conjugate to g2 and g2 is conjugate to g3 then g1 is conjugate to g3 (“transitivity”).
Definition: Fix an element g in a group G. The set
Cl(g) = { h*g*h^(-1) | h in G }
is called the conjugacy class of g in G. It is the equivalence class of the element g under the relation given by conjugation.
If H is a subgroup of G and if g is a fixed element of G then the set
H^g = {g*h*g^(-1) | h in H }
is a subgroup of G. Such a subgroup of G is called a subgroup conjugate to H.
Exercise: Let S be the set of all subgroups of G. We define a relation R on S by
R = { (H1,H2) in SxS | H1 is conjugate to H2 }.
Show that R is an equivalence relation.
Example: Let G = Sn and let H = be a cyclic subgroup generated by a permutation g of the set {1,2,…,n}. With respect to the equivalence relation in the previous exercise, show that a subgroup K of G belongs to the equivalence class [H] of H in G if any only if K is cyclic and is generated by an element k of G conjugate to g in G.
Yet Another Mathblog 