Math 581    Problem Set 2    Due April 15

1.  Explain why the following position cannot be reached from the original configuration of the 15-puzzle.

1   3   5   7

9 11 13 15

14 12 10 8

 6   4   2  B

***
This position is represented by the permutation written in two-row notation as
1  2  3  4  5  6   7   8   9 10 11  12  13  14  15  B
1  3  5  7  9 11 13 15 14 12 10  8    6    4    2   B

In cycle notation it is  (2  3  5  9  14  4  7  13  6  11  10  12  8  15).
This is a 14-cycle, hence an odd permutation.
***

How about the following?

15 14 13 12

11 10   9   8

 7   6    5   4

 3    2   1   B

***
This position is represented by the permutation written in two-row notation as
1     2  3  4   5   6   7   8   9 10 11  12  13  14  15  B
15 14 13 12 11 10  9    8   7  6  5    4    3    2   1   B
In cycle notation it is  (1 15)(2 14)(3 13)(4 12)(5 11)(6 10)(7 9).  this is a product of seven transpositions, hence as odd permutation.  Therefore,the position cannot be reached.
***
 

2. Let H be a nonempty subset of a group G.   Prove that H is a subgroup of G if and only if H itself with the multiplication "inherited" from G is a group. (By "inherited" is meant that if h, k  are in H, then the product hk in H is the element hk given by G's multiplication.)
***
First, suppose that  H  is a subgroup of  G. Then  H  is nonempty, so it contains an element h. So it also contains  h' and then  hh' = e.  And, eh = h for every  h  in  H, so H  has an identity element, the  e  from  G.  Inverses:  if  h  is in  H, then  the inverse  h' from  G  is in  H.  But  hh' = e, which is now known to be the identity in  H.  So  H has inverses.  The multiplication in  H  is that given by  G, which is associative.  Therefore,  H  is a group.

Second, suppose that  H  is a group under the multiplication from  G.
Then H, as a group itself, is nonempty. If  h, k  are in  H, then  multiplying them in  H  gives the element  hk defined by  G's multiplication. Therefore, hk  is in  H.  Now,  H as a group has an identity  f, which is one of the elements of  G.  So  ff = f, where ff is the product given by G's multiplication.  But  fe = f in G.  So ff = fe, and by cancellation in  G,  f = e.  So the identity e of G is in H and serves as the identity in  H..  Finally, if  h  is in H, then  it has an inverse  k  in  H.  hk =  e, where hk is the product given by multiplication in  G.  But if  h'  is the inverse of  h  in G, the hh' = e.  So both k and h' are inverses for  h  in G.  So  k = h' and h' is in  H.  Therefore,  H  is a subgroup of  G.
***

3. Let G be a group and let g be any fixed element in G. Define a function  from G   into G by

"h in G,     f(h) = g'hg.

Prove that f is an isomorphism of G onto G. (An isomorphism of a group G onto itself is usually called an automorphism of G. This particular automorphism is usually called conjugation by g.)
***
one-to-one:  Let  f(h) = g'hg = f(k) = g'kg.  Cancel  g'  on the left and  g  on the right to get  h = k.

onto: If  h  is any element of G, then f(ghg') = g'ghg'g = h.

the multiplication condition:  f(h)f(k) = (g'hg)(g'kg) = g'hkg = f(hk).
***

4.  Let S6 denote the group of all permutations of the set {1, 2, 3, 4, 5, 6}.
Let g = (1 4 5 3). Calculate g'hg for the following permutations h.

(a)  h = (2 6 4)
    ***  (2 6 5)  ***

(b)  h = (2 6 5)
    ***  (2 6 3) ***

(c)  h = (2 6 1)
    ***  (2 6 4) ***

(d)  h = (2 4 5)
    ***  (2 5 3) ***

(e)  h = (2 5 4)
    ***  (2 3 5) ***

(f)  h = (3 4 1 2 6 5)
    ***  (1 5 4 2 6 3) ***

(g)  h = (6 2)(4 5)
    ***  (6 2)(5 3) ***

(h)  Formulate a general rule which encompasses these calculations. State it carefully, as if you were writing it for inclusion in a textbook.
***In a representation of  h  as a product of cycles, replace each symbol by its image under g.
***

5.  Textbook p. 206, #3
***on acetate 61.0***

6.  Textbook, p.206 #1 modified. Instead of showing that this system forms a semigroup, show that it does not form a group.
***To be a group the system would have to be associative, there would be an identity, and each element would need an inverse.
First, try to see if there is an identity.  If  n  is the identity, then the minimum of  n  and  any  k would be k.  So the min of  n  and  5 would be  5.  So, n could not be less thatn 5 and would have to be  5 itself.  Now that we've identified the only candidate, 5, for the identity, we look for inverses.  The element  1  has to have an inverse, say, m.  But the min of  1  and  m  would  be 1, which is not equal to 5, our only candidate for the identity.  Therefore, no inverses.  Therefore not a group.
***