Math2020: Solving discrete problems

homework 6 hint

Due date:

The homework will be due on Thursday March 31, which will allow time for any extra questions in class on Tuesday.

More hints and examples coming soon - check later on Monday, March 28. Should be up by 2pm.

General:

This homework is about constructing group multiplication (or composition) tables for a group, and using this to say something about the group.

Class 16 was most similar to this homework. In class 16 we did examples of groups with 4 elements. See http://www.math.lsu.edu/~verrill/teaching/discrete2020/lecture16notes.pdf, and the hand out with examples. The homework is similar to this, but with 6 elements instead of 4 in the groups.

Hint about squares mod N

Here is a question similar to one on the homework, but about squares mod 17 instead of mod 13.

Question: Find the squares mod 13, not including 0, and make a mod 17 multiplication table for them.
Note, the squares form a subgroup of the group Z/17Z*. A subgroup is a subset which is also a subgroup.

How to find the squares? It's useful to make a table:

x	x^2	x^2 mod 17
1	1	1
2	4	4
3	9	9
4	16	16
5	25	8
6	36	2
7	49	15
8	64	13
9	81	13
10	100	15
11	121	2
12	144	8
13	169	16
14	196	9
15	225	4
16	256	1

So, there are only 8 different squares mod 17, which are:

(Remark: do you notice any pattern in this table of squares? How many nonzero squares do you think there are mod N, if N is an odd prime?)

Here is the mutiplication table for the subgroup of squares in Z/17Z*:

	1	2	4	8	9	13	15	16
1	1	2	4	8	9	13	15	16
2	2	4	8	16	1	9	13	15
4	4	8	16	15	2	1	9	13
8	8	16	15	13	4	2	1	9
9	9	1	2	4	13	15	16	8
13	13	9	1	2	15	16	8	4
15	15	13	9	1	16	8	4	2
16	16	15	13	9	8	4	2	1

Note, this can be made by first making a multiplication table of the numbers using usual arithmetic, and then working out the answers mod 17.

Note, the fact that this "works" is because the product of two squares is still a square. By works, I mean that the set of all squares is a subgroup. This means that all the numbers in the table are from the list 1,2,4,8,9,13,15,16.
Another example of a subgroup is the subgroup of all even numbers in Z,+. This is a subgroup since any two even numbers add to give another even number. But the set of all odd numbers is not a subgroup of Z,+ because two odd numbers add to give an even number.

Here are the answers to the rest of the questions for this example:

• B: Orders of elements. The order means the number of times you apply the element in order to get to the identity. You can find this from a table of powers mod 17:

  Table of powers
  x	x^1	x^2	x^3	x^4	x^5	x^6	x^7	x^8		order of x
  1	1	1	1	1	1	1	1	1		1
  2	2	4	8	16	15	13	9	1		8
  4	4	16	13	1	4	16	13	1		4
  8	8	13	2	16	9	4	15	1		8
  9	9	13	15	16	8	4	2	1		8
  13	13	16	4	1	13	16	4	1		4
  15	15	4	9	16	2	13	8	1		8
  16	16	1	16	1	16	1	16	1		2

  The orders are given in the last column.
  The question asks you to add these to the end of the table, so then you'd have a table like this:

  	1	2	4	8	9	13	15	16
  1	1	2	4	8	9	13	15	16
  2	2	4	8	16	1	9	13	15
  4	4	8	16	15	2	1	9	13
  8	8	16	15	13	4	2	1	9
  9	9	1	2	4	13	15	16	8
  13	13	9	1	2	15	16	8	4
  15	15	13	9	1	16	8	4	2
  16	16	15	13	9	8	4	2	1
  orders of elements	1	8	4	8	8	4	8	2

  Note that the order is a number n, which is the smallest number n such that x^n=1. These are marked in red. Note, in general, instead of powers, you'd need to apply the group operation n times, which might mean adding n times instead of multiplying n times.

  Note also that the orders of the elements must divide the order of the group. The group has 8 elements, which means it has order 8. So the orders of the elements must be 1,2,4, or 8. We see this is true. If we'd found an element with order 7, for example, we'd know we must have made a mistake.

• C: Cyclic? For a group to be cyclic, it must be generated by one element, i.e., all elements can be obtained by repeatedly applying composing one element. Also, for a group to be cyclic, it must have an element with order the same as the order of the group. In this case, there must be an element of order 8. This is true, e.g., we could take the element to be 2. Then the powers of 2 are given in the above table of powers, and are given by 2,4,8,16,15,13,9,1. This is a list of all the elements of the group. I.e., every element of this group can be written as a power of 2. So 2 generates this group. For comparison, look at 16. The only powers of 16 are 16 and 1, so 16 does not generate the whole group. Or 4, which generates 4,16,13,1, which are all possible powers of 4, also does not generate the group. But 2,8,9 or 15 could all be taken as generators of the group.

  Since there is an element that generates this group, this group is cyclic. The symmetries of a square is an example of a non cyclic group (see text book).

• D: Abelian? This group is abelian, which you can see since there is a symmetry about the main diagonal. The symmetries of a square is an example of a non cyclic group (see text book).
• E: Isomorphic groups? I'll have to add more examples for isomorphic groups. But you can actaully construct them yourself. In fact any cyclic groups of the same order are isomoprhic. You can see this in the next example.

What is the table for the composition if the group is Z/8Z,+?

Note, I should have asked for composition tables, not multiplication tables, since the composition law is often not multiplication. In this case it is addition.

• A. Composition table

  Table of addition mod 8
  0	0	1	2	3	4	5	6	7
  1	1	2	3	4	5	6	7	0
  2	2	3	4	5	6	7	0	1
  3	3	4	5	6	7	0	1	2
  4	4	5	6	7	0	1	2	3
  5	5	6	7	0	1	2	3	4
  6	6	7	0	1	2	3	4	5
  7	7	0	1	2	3	4	5	6

• B:Orders: Make another table similar to the above example. But now applying the operation + several times is the same as multiplcation, rather than taking powers. E.g., doing *8 twice is the same as doing *(8^2). But doing +8 twice is the same as doing +(2*8). Another example: (8*8*8)=(8^3), but (8+8+8)=3*8. We are now using + as our operation. So we have:

  Table of multiples
  x	1x	2x	3x	4x	5x	6x	7x	8x		order of x
  0	0	0	0	0	0	0	0	0		1
  1	1	2	3	4	5	6	7	0		8
  2	2	4	6	0	2	4	6	0		4
  3	3	6	1	4	7	2	5	0		8
  4	4	0	4	0	4	0	4	0		4
  5	5	2	7	4	1	6	3	0		8
  6	6	4	2	0	6	4	2	0		4
  7	7	6	5	4	3	2	1	0		8

  Note that the identity element is now 0 instead of 1, so we are looking for the first place 0 occurs in each row. These are marked in red, and used to give the last column. Note that the orders are again numbers dividing 8.

• C: Cyclic? Similarly to the previous example, this is a cyclic group. One possible generator is 1. You could also take 3,5 or 7.
• D: Abelian? This group is abelian, which you can see since there is a symmetry about the main diagonal.
• E: Isomorphic groups? This group is isomprphic to the group in the above example. As they are given right now, it's quite hard to see that these are isomorphic, if you don't know the result that cyclic groups of the same order are isomorphic. But, we can rearange the rows and columns of the first table so that they match up.

  If I want to match up 1 in Z/8Z with 2 in the group of non zero squares mod 17, then I have to match up 2*1 with 2^2, and 3*1 with 2^3, and so on. So, this means that if I want my table of squares to look similar to the table for Z/8Z, I should rearange the squares to be in the order 1,2,4,8,16,32= 15 mod 17, 64= 13 mod 17, 128=9 mod 17. So, the new table for the nonzero squares mod 17 looks like:

  	1	2	4	8	16	15	13	9
  1	1	2	4	8	16	15	13	9
  2	2	4	8	16	15	13	9	1
  4	4	8	16	15	13	9	1	2
  8	8	16	15	13	9	1	2	4
  16	16	15	13	9	1	2	4	8
  15	15	13	9	1	2	4	8	16
  13	13	9	1	2	4	8	16	15
  9	9	1	2	4	8	16	15	13

  Although this is a table for the same group as the table of multiplications, above, putting the elements in a different order results in quite a different looking table. Now we can easily see that this table has the same pattern as the addition mod 8 table. E.g., you can clearly see the same pattern of the NE-SW diagonals.

  Explicitly, the isomorphism is given by the map phi, defined as in the folowoing table:

  x	0	1	2	3	4	5	6	7
  phi(x)	1	2	4	8	16	15	13	9

  Note, by replacing 2 by 8, 9, or 15, and following the same procedure as above, you'll get a different isomophism between the nonzero squares mod 17 and Z/8Z,+.

Note about isomorphisms

Hints for symmetries

• Dog school page
• Pearson ed page
• JCU symmetries page

Example of a non abelian group

In the text book there is an example of the symmetry group of the square, which is an example of a non abliean group of order 8. See Example 9.85, page 389, of the first edition of text book. Note that the table on page 390 is not symmetric about the NW-SE diagonal, so the group is not abelian.

Note, there is a nice java applet showing symmetries of the square on a page at CSUSB .

Answer to question about permutations

So, these computations are similar to those done on the quiz on the symmetries of the cube and tetrahedron - see
http://www.math.lsu.edu/~verrill/teaching/discrete2020/cubesolution.pdf and
http://www.math.lsu.edu/~verrill/teaching/discrete2020/tetra_solution.pdf

This was also discussed in class 12 - see
http://www.math.lsu.edu/~verrill/teaching/discrete2020/lecture12notes.pdf

In the text book, first edition, see section 4.2, page 141-142, also see exercise 1, page 146, end of section 4.2. Also section 9.5, especially example 9.86, page 389-391. Several of the exercises at the end of section 9.5 are also on permutations.

Composition of functions example

Order means how many times you have to compose an element with itself to get back to the identity. In this case the identity is the map f1(x)=x.

For example, for f6(x), we have
f6(f6(x)) = f6( x/(x-1) ) = x/(x-1) / ( x/(x-1) -1)
mutliply top and bottom by (x-1) to get:
f6(f6(x)) = x / (x - (x-1)) = x/( x - x +1)
= x/1 =x
So f6(f6(x)) = x = f1(x)
So f6 has order 2.

But other elements may have other orders.

E.g.,
f5(f5(x)) = f5(1 - 1/x) = 1 - 1/(1-1/x)
= 1 - 1/ (1-1/x)
multiply top and bottom of second part by x:
= 1 - x/( x - 1)
put everything over a common denominator:
= (x-1 - x)/( x-1) = -1/( x-1) = 1/(1-x) = f4(x)
So doing f5 twice is not the identity, so f5 does not have order 2.

Now you have to compute f5(f5(f5(x)), and see if this is the identity, ie., since f5(f5(x)) = 1/(1-x), is
f5(1/(1-x)) = 1 - 1/(1-1/x))
the same as just x?
If it is, then f5 has order 3. If it's not, the you have to compose again, and see if f5(f5(f5(f5(x))) = x. Continue until you find how many times you have to compose f5 with itself to get x. This is a good review/practice of your algebra skills!