Which Cayley diagrams are isomorphic?

[radou]

Homework Statement

Given the four Cayley diagrams in the attachment, one needs to determine which of the groups represented by them are isomorphic.

The Attempt at a Solution

Well, after inspecting all of them, I concluded none are isomorphic.

For the first two, after constructing the tables, one can find a product where the identity elements don't coincide. The same with the third one and the first two. Now, the fourth diagram, unless I'm mistaken, doesn't even have 6 elements! Since the full line represents multiplication with the generator b and b^-1 = b. So it can't be isomorphic to any of the other ones.

I'm not really sure about my results. If you want, I can provide more details.

Thanks in advance for a glance.

 

[radou]

For example, to elaborate on the last diagram - let any point be the identity element e. Then, starting clockwise for example, we generate the elements b, b^2 = e (in my book the convention is used that a line without an arrowhead means that b^2 = e), b^3 = b, b^4 = e, b^5 = b, and we end at b^6 = e. Hence, this group has elements b and e.

Edit: the example of the first diagram can already be found in the book (see attachment), and the second is the same, only ab and ab^2 are interchanged, unless I'm wrong.

 

[micromass]

Hmm, the answer is certainly not correct. There are some Cayley graphs which come from thesame groups!

In fact, it would be easier if for every graph, you list the group where the graph comes from.

For example, the last diagram: clearly, if we choose an element b, then the other elements are of the form bⁿ. Thus this clearly is a cyclic group. In fact, the last graph is the Cayley graph of the group $$\mathbb{Z}_6$$.

(where I'm confused is when you say that the last graph doesn't have 6 elements. Why do you conclude that? A graph has as much elements as it's vertices)...

Try to write down explicitely the groups (or even try working out their Cayley multiplication table).

Maybe a little hint: there are only two groups of order 6: $$\mathbb{Z}_6$$ and $$S_3$$. So this could help you...

 

[micromass]

Maybe start with this: which of the Cayley diagrams come from abelian groups?? That's not hard to find out I think...

 

[radou]

Ah, of course, I just realized that points on a Cayley diagram stand for distinct elements - however, what confused me was the convention in the book which says that "arrows with no arrowheads mean that b^2 = e, where these arrows mean multiplying from the right with b". There's something confusing about that. If the group represented by the last diagram is Cyclic, then why don't the lines connecting the points have arrowheads?

 

[radou]

OK, about the first two diagrams.

As I mentioned, the second one is the same as the first, except ab and ab^2 are interchanged. I wrote down the group table, but even without it, if you follow the diagram, it is obvious that for this group we have ab^2 * ab = e, whereas in the first one we have ab^2 * ab = b^2.

Since if two groups G and H are isomorphic, then for xy = e in G, we have f(xy) = f(x)f(y) = e in H. For example, an obvious bijection for the upper examples would be the identity! The groups even consist of the same elements. But the structure is not preserved - the products of the images of x and y do not equal the inverse in H (i.e. the second Cayley diagram in our case).

 

[micromass]

Hmm, I really don't know why the author doesn't write arrowheads on the last diagram...

OK, about the first two diagrams.

As I mentioned, the second one is the same as the first, except ab and ab^2 are interchanged. I wrote down the group table, but even without it, if you follow the diagram, it is obvious that for this group we have ab^2 * ab = e, whereas in the first one we have ab^2 * ab = b^2.

Hmmm, this doesn't really convince me. There is nobody who says that the elements a and b in the two diagrams are thesame. Furthermore:

Since if two groups G and H are isomorphic, then for xy = e in G, we have f(xy) = f(x)f(y) = e in H. For example, an obvious bijection for the upper examples would be the identity! The groups even consist of the same elements. But the structure is not preserved - the products of the images of x and y do not equal the inverse in H (i.e. the second Cayley diagram in our case).

You say that the identity is a bijection which is not a homomorphism. But that doesn't suffice. There may be other (exotic) bijections between the two sets that you haven't thought about, and which may be homomorphisms.

So in order to prove this, you have to write down every possible bijection and check if it is an homomorphism. However, there are 6! possible bijections, so you would not want to do that. Instead, try to find a qualitative difference between the two diagrams. For example, the first diagram yields a nonabelian group and the second is an abelian group. This would suffice to show that the two groups are not isomorphic...

 

[radou]

Hmm, I really don't know why the author doesn't write arrowheads on the last diagram...

Yes, that's really confusing. But I guess I can imagine there are arrowheads on the diagram. that would make perfect sense.

.

You say that the identity is a bijection which is not a homomorphism. But that doesn't suffice. There may be other (exotic) bijections between the two sets that you haven't thought about, and which may be homomorphisms.

So in order to prove this, you have to write down every possible bijection and check if it is an homomorphism. However, there are 6! possible bijections, so you would not want to do that. Instead, try to find a qualitative difference between the two diagrams. For example, the first diagram yields a nonabelian group and the second is an abelian group. This would suffice to show that the two groups are not isomorphic...

Good point, I was confusing things a bit. OK, I'll think about this a bit later.

Edit: I was trying to prove or disprove an isomorphism relation by merely looking at the multiplication tables of the groups, which was actually a bit misleading. Actually, this only is of use when the tables "look the same" (I'm being very informal now, but I think you know what I mean, i.e. if we identify every element of a table for G with another element of H in a one-to-one manner, then the product of any two elements in G must be on the same place as the product of the elements in H which correspond to our starting elements in G).

 

[micromass]

Edit: I was trying to prove or disprove an isomorphism relation by merely looking at the multiplication tables of the groups, which was actually a bit misleading. Actually, this only is of use when the tables "look the same" (I'm being very informal now, but I think you know what I mean, i.e. if we identify every element of a table for G with another element of H in a one-to-one manner, then the product of any two elements in G must be on the same place as the product of the elements in H which correspond to our starting elements in G).

Yes, I know what you mean. Two tables of thesame group can look very different... But you see that it can be very hard to determine whether two groups are isomorphic or not. It's a bit the same with topology: in general it is really hard to see whether two spaces are homeomorphic or not. For example $$\mathbb{R}^2$$ and $$\mathbb{R}^3$$, it is not trivial to see why these spaces are not homeomorphic...

 

[radou]

Yes, I know what you mean. Two tables of thesame group can look very different... But you see that it can be very hard to determine whether two groups are isomorphic or not. It's a bit the same with topology: in general it is really hard to see whether two spaces are homeomorphic or not. For example $$\mathbb{R}^2$$ and $$\mathbb{R}^3$$, it is not trivial to see why these spaces are not homeomorphic...

Yes, like in topology, we search for certain properties which are conserved under isomorphisms, such as "being abelian" or "being generated by some element", etc.

 

[radou]

OK, let's first resolve the last two groups.

The last group is a cyclic group (generated by b) with elements {e, b, b^2, b^3, b^4, b^5}, of course after we added the arrowheads to the diagram, since without them it doesn't seem to make any sense. This group is obviously abelian.

Now, let's look at the diagram before the last one. So, we get a group consisting of {e, b, ba, bab, baba, babab}. From the diagram we can conclude that a = a^-1 and b = b^-1. Actually, in this diagram, the notation without arrowheads makes sense. This group is not abelian, since for example ba*bab = babab, and bab*ba = b.

Hence, the last two groups are not isomorphic. Is this correct?

 

[radou]

Further on, the first group is not abelian, since ba = ab^2 and ab = ab. But the second one is (I wrote down its table and it is symmetric). Hence (I'll refer to the diagrams, i.e. the groups as 1, 2, 3 and 4 respectively according to the attachment from now on) 4 is not isomorphic to 3, neither to 1.

 

[micromass]

Yes, that is correct. 4 is not isomorphic to either 1 or 3. But I claim that it is isomorphic to 2. And sadly there is no other way to prove this than to construct an explicit isomorphism...

Thesame technique shows that 3 is not isomorphic to either 2 or 4. But it probably is isomorphic to 1. In fact, 1 and 3 both come from the group S₃...

 

[radou]

Yes, that is correct. 4 is not isomorphic to either 1 or 3. But I claim that it is isomorphic to 2. And sadly there is no other way to prove this than to construct an explicit isomorphism...

Yes, this is what I thought... But for some reason, this gets a bit messy.

I have both tables. First of all, the element having itself as an inverse must be matched to the element with the same property. So I obtain b^3 --> a. Now I look where b^3 occurs and obtain b^5 --> b^2 and b^4 --> ab. But when I proceed with the other 3 elements, I always find a multiplication entry which is not correct.

I think I may be missing something here. I checked my tables, they seem to be OK.

 

[radou]

Actually, the relations I wrote above (except for b^3) won't work either.

If the point of this is to find a combination that works, then I won't do it. Just verify if my thought is correct.

Edit: and btw, did you mean that 1 and 3 both come from S6? Or I'm missing something here?

It is, btw, obvious that 4 is isomorphic to the addition of integers modulo 5 (in fact, it seems to me I've seen some result before and it seems quite expectable that every finite cyclic group opf order n is isomorphic to a certain group of integers under addition modulo n-1, probably the same holds for infinite cyclic groups and the set of integers with standard addition), but it seems less obvious that 1 and 3 are isomorphic to S6...or it's trivial - these are simply groups with the same number of elements as S6 and the entries in the rows are simply permutations of 6 elements, nothing more...

 

[micromass]

I have both tables. First of all, the element having itself as an inverse must be matched to the element with the same property. So I obtain b^3 --> a. Now I look where b^3 occurs and obtain b^5 --> b^2 and b^4 --> ab. But when I proceed with the other 3 elements, I always find a multiplication entry which is not correct.

What you wrote is correct. It's strange that the multiplication don't work with you, because they work for me...

I had something different: I did b --> ab. But your choice should work to.

But the sad thing about these kinds of exercises that it actually comes down to finding the right isomorphism. A quicker proof is possible when you solved 13.F, that exercise states that there are exactly 2 groups of order 6. That implies immediately that an isomorphism exists and then you won't have to construct it explicitely...

 

[radou]

What you wrote is correct. It's strange that the multiplication don't work with you, because they work for me...

I had something different: I did b --> ab. But your choice should work to.

But the sad thing about these kinds of exercises that it actually comes down to finding the right isomorphism. A quicker proof is possible when you solved 13.F, that exercise states that there are exactly 2 groups of order 6. That implies immediately that an isomorphism exists and then you won't have to construct it explicitely...

And these groups are probably exactly some cyclic group of order 6 and the group S6?

 

[micromass]

Edit: and btw, did you mean that 1 and 3 both come from S6? Or I'm missing something here?

Yes, I claim that both 1 and 3 come from S₃ (not S₆, since this contains 6! elements, not 6). You could prove this by selecting suitable generators in S₃ and constructing the diagram. I think if you take a= (1 2) and b= (2 3), then you will obtain the third diagram...

It is, btw, obvious that 4 is isomorphic to the addition of integers modulo 5

modulo 6

(in fact, it seems to me I've seen some result before and it seems quite expectable that every finite cyclic group opf order n is isomorphic to a certain group of integers under addition modulo n-1, probably the same holds for infinite cyclic groups and the set of integers with standard addition),

Yes, this is true. You will prove this in the chapter about cyclic groups... In fact, every cyclic group of order n is isomorphic to $$\mathbb{Z}_n$$. And any infinite cyclic group is isomorphic to $$\mathbb{Z}$$.

but it seems less obvious that 1 and 3 are isomorphic to S6...or it's trivial - these are simply groups with the same number of elements as S6 and the entries in the rows are simply permutations of 6 elements, nothing more...

Like mentioned previously, it's not hard to show this. Just find the correct generators in S6. In fact, if you take (1 2 3) and (1 2), then I think you should obtain diagram 1.

 

[radou]

OK, I'll think about this...thanks.

Btw, I'll consider this problem solved, I'm too lazy to mess with multiplication right now.

 

[micromass]

And these groups are probably exactly some cyclic group of order 6 and the group S6?

Yes (if you change S6 by S3 at least...).

In fact, it helps a lot if you know all the finite groups of order less than 10. I had to learn them by heart when I first did group theory. And it helps a lot to know them!

Here is the list of all small groups:

1. Order 1: the trivial group
2. Order 2: $$\mathbb{Z}_2$$
3. Order 3: $$\mathbb{Z}_3$$
4. Order 4: $$\mathbb{Z}_4$$ and $$\mathbb{Z}_2\times\mathbb{Z}_2$$.
5. Order 5: $$\mathbb{Z}_5$$
6. Order 6: $$\mathbb{Z}_6$$ (which is isomorphic to $$\mathbb{Z}_2\times \mathbb{Z}_3$$) and $$S_3$$ (which is isomorphic to $$D_3$$.
7. Order 7: $$\mathbb{Z}_7$$
8. Order 8: $$\mathbb{Z}_8$$, $$\mathbb{Z}_4\times \mathbb{Z}_2$$, $$\mathbb{Z}_2\times \mathbb{Z}_2\times \mathbb{Z}_2$$, $$D_4$$ and $$Q_8$$
9. Order 9: $$\mathbb{Z}_9$$ and $$\mathbb{Z}_3\times \mathbb{Z}_3$$
10. Order 10: $$\mathbb{Z}_{10}$$ and $$D_5$$

The group $$Q_8$$ is the quaternion group and consists of

$$\{1,-1,i, -i, j, -j, k, -k\}$$

with multiplication $$i^2=j^2=k^2=-1$$ and $$ijk=-1$$ (this determines the product completely).

 

[radou]

Hm, OK.

Btw Z4 is isomorphic to Z2 x Z2 ? I just wrote down their multiplication tables. In Z2 x Z2, all elements equal their own inverses (the diagonal of the table consists only of identity elements), but in Z4, only 0 and 2 are their own inverses... How can there be an isomorphism then? If a is an element of Z2 x Z2, then f(aa) = e = f(a)f(a), for any a in Z2 x Z2. But we only have 2 such elements to match in Z4?

Sorry if these questions are stupid, but I really find this is the right time to try and understand some fundamental concepts which I might miss later on...

 

[micromass]

Hm, OK.

Btw Z4 is isomorphic to Z2 x Z2 ? I just wrote down their multiplication tables. In Z2 x Z2, all elements equal their own inverses (the diagonal of the table consists only of identity elements), but in Z4, only 0 and 2 are their own inverses... How can there be an isomorphism then? If a is an element of Z2 x Z2, then f(aa) = e = f(a)f(a), for any a in Z2 x Z2. But we only have 2 such elements to match in Z4?

Sorry if these questions are stupid, but I really find this is the right time to try and understand some fundamental concepts which I might miss later on...

Nono, Z4 is totally not isomorphic to Z2 x Z2! I didn't write that, did I?? I only said that there are 2 groups of order 4: Z4 and Z2 x Z2...

What is true however, is that Z6 and Z2 x Z3 are isomorphic!

 

[radou]

Ahhh, OK, for some bizarre reason I concluded that they are isomorphic, which doesn't make any sense at all, since we're only interested in not isomorphic groups of some specific order! All the other ones are isomorphic to them!

OK, thanks a lot!

 

[radou]

Btw, another line of reasoning I'd like to check, I mentioned it before, I think...

One exercise asks to show that R and R* (the set of all non-zero real numbers with respect to multiplication) are not isomorphic. The hint says to consider -1 in R*.

Now, clearly, in both groups the identity elements are their own inverses, so they're not really interesting. But -1 is an element in R* which is its own inverse and we can't match this element to any element of R because there is no element in R which has this property (except 0, of course, but it is mapped to 1!).

Edit: more generally, if we have two groups G and H, and n elements in G which are their own identity, and m elements in H with the same property (m and n are distinct integers), G and H are not isomorphic.

I ask because this seems an easy operative criterion to conclude something about isomorphism relations in applications.

 

[radou]

Oh yes, and another question. (Btw, sorry for overloading this thread with questions )

I want to prove that Z is not isomorphic to Q. Well, let's assume they are isomorphic. Then, by a fact proven before, since Z is a cyclic group with generator 1, then Q would be cyclic group with generator f(1). I don't have a formal proof from now on, but it's somehow obvious that this can't be true, i.e. there is no element in Q such that for any x in Q there exists some n such that nf(1) = x.

 

[micromass]

Btw, another line of reasoning I'd like to check, I mentioned it before, I think...

One exercise asks to show that R and R* (the set of all non-zero real numbers with respect to multiplication) are not isomorphic. The hint says to consider -1 in R*.

Now, clearly, in both groups the identity elements are their own inverses, so they're not really interesting. But -1 is an element in R* which is its own inverse and we can't match this element to any element of R because there is no element in R which has this property (except 0, of course, but it is mapped to 1!).

Edit: more generally, if we have two groups G and H, and n elements in G which are their own identity, and m elements in H with the same property (m and n are distinct integers), G and H are not isomorphic.

I ask because this seems an easy operative criterion to conclude something about isomorphism relations in applications.

Yes, this is all correct. And it is indeed a handy criterion to conclude something about isomorphism. But you can easily extend this criterion: in next chapter you will see that an a element has order n if $$a^n=1$$. Now, isomorphism preserves the order of the elements. Thus an easy criterion is this: if G has n elements of a certain order, and if H has m elements of this certain order, and n and m are distinct, then G and H are not isomorphic.

 

[micromass]

Oh yes, and another question. (Btw, sorry for overloading this thread with questions )

I want to prove that Z is not isomorphic to Q. Well, let's assume they are isomorphic. Then, by a fact proven before, since Z is a cyclic group with generator 1, then Q would be cyclic group with generator f(1). I don't have a formal proof from now on, but it's somehow obvious that this can't be true, i.e. there is no element in Q such that for any x in Q there exists some n such that nf(1) = x.

Yes, this is also correct. And I think that that proof is already formal enough I mean: it's pretty much obvious...

 

[radou]

OK, great, thanks a bunch!

 

[radou]

Oh yes, and another little question regarding defining equations of finite groups. An example in the book is the group {e, a, b, b^2, ab, ab^2} whose generators satisfy the equations a^2 = e, b^3 = e and ba = ab^2. If I'm looking at this the right way, the point of our defining equations is exactly to point out what our products in the multiplication tables are - i.e. what element of {e, a, b, b^2, ab, ab^2} some product is, for if we didn't have no defining equations, we could just fill out the table with products, for example abb^2aaab^2, and we'd know it is some element of {e, a, b, b^2, ab, ab^2}, but not exactl which one. Am I right on this one?

 

[micromass]

Oh yes, and another little question regarding defining equations of finite groups. An example in the book is the group {e, a, b, b^2, ab, ab^2} whose generators satisfy the equations a^2 = e, b^3 = e and ba = ab^2. If I'm looking at this the right way, the point of our defining equations is exactly to point out what our products in the multiplication tables are - i.e. what element of {e, a, b, b^2, ab, ab^2} some product is, for if we didn't have no defining equations, we could just fill out the table with products, for example abb^2aaab^2, and we'd know it is some element of {e, a, b, b^2, ab, ab^2}, but not exactl which one. Am I right on this one?

Yes, that is indeed the reason why you should always give defining equations! If there were no defining equations, then we couldn't prove that abbbbbbb=aaaaaaab for example. So you should always give enough defining equations. Typically, the defining equations determine the order of the generating elements (these are the equations of the form a^2=e and b^3=e) and a commutation rule (that is: ba=ab^2). You will encounter this a lot in group theory!