Register to reply

A Cayley diagram problem

by radou
Tags: cayley, diagram
Share this thread:
radou
#1
Feb7-11, 05:10 PM
HW Helper
radou's Avatar
P: 3,220
1. The problem statement, all variables and given/known data

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


3. 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.
Attached Thumbnails
Clipboard01.jpg  
Phys.Org News Partner Science news on Phys.org
Pilot sites in energy from coffee waste show good results
Startups offer banking for smartphone users
Factor in naked mole rat's cells enhances protein integrity
radou
#2
Feb7-11, 05:29 PM
HW Helper
radou's Avatar
P: 3,220
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.
Attached Thumbnails
Clipboard02.jpg  
micromass
#3
Feb7-11, 06:00 PM
Mentor
micromass's Avatar
P: 18,299
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 bn. Thus this clearly is a cyclic group. In fact, the last graph is the Cayley graph of the group [tex]\mathbb{Z}_6[/tex].

(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: [tex]\mathbb{Z}_6[/tex] and [tex]S_3[/tex]. So this could help you...

micromass
#4
Feb7-11, 06:04 PM
Mentor
micromass's Avatar
P: 18,299
A Cayley diagram problem

Maybe start with this: which of the Cayley diagrams come from abelian groups?? That's not hard to find out I think...
radou
#5
Feb8-11, 12:58 AM
HW Helper
radou's Avatar
P: 3,220
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
#6
Feb8-11, 02:17 AM
HW Helper
radou's Avatar
P: 3,220
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
#7
Feb8-11, 07:48 AM
Mentor
micromass's Avatar
P: 18,299
Hmm, I really don't know why the author doesn't write arrowheads on the last diagram...

Quote Quote by radou View Post
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
#8
Feb8-11, 07:58 AM
HW Helper
radou's Avatar
P: 3,220
Quote Quote by micromass View Post
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.

.
Quote Quote by micromass View Post
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
#9
Feb8-11, 08:08 AM
Mentor
micromass's Avatar
P: 18,299
Quote Quote by radou View Post
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 [tex]\mathbb{R}^2[/tex] and [tex]\mathbb{R}^3[/tex], it is not trivial to see why these spaces are not homeomorphic...
radou
#10
Feb8-11, 08:11 AM
HW Helper
radou's Avatar
P: 3,220
Quote Quote by micromass View Post
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 [tex]\mathbb{R}^2[/tex] and [tex]\mathbb{R}^3[/tex], 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
#11
Feb8-11, 09:30 AM
HW Helper
radou's Avatar
P: 3,220
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
#12
Feb8-11, 09:46 AM
HW Helper
radou's Avatar
P: 3,220
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
#13
Feb8-11, 10:31 AM
Mentor
micromass's Avatar
P: 18,299
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 S3...
radou
#14
Feb8-11, 12:42 PM
HW Helper
radou's Avatar
P: 3,220
Quote Quote by micromass View Post
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
#15
Feb8-11, 12:46 PM
HW Helper
radou's Avatar
P: 3,220
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
#16
Feb8-11, 12:56 PM
Mentor
micromass's Avatar
P: 18,299
Quote Quote by radou View Post
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
#17
Feb8-11, 01:02 PM
HW Helper
radou's Avatar
P: 3,220
Quote Quote by micromass View Post
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
#18
Feb8-11, 01:04 PM
Mentor
micromass's Avatar
P: 18,299
Quote Quote by radou View Post
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 S3 (not S6, since this contains 6! elements, not 6). You could prove this by selecting suitable generators in S3 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 [tex]\mathbb{Z}_n[/tex]. And any infinite cyclic group is isomorphic to [tex]\mathbb{Z}[/tex].


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.


Register to reply

Related Discussions
Groups and Cayley's theorem Linear & Abstract Algebra 0
Cayley digraph Calculus & Beyond Homework 0
Cayley hamilton Linear & Abstract Algebra 7
Deligne Dam of Cayley River Calculus & Beyond Homework 2
Cayley - hamilton theorem Linear & Abstract Algebra 7