Find injective homomorphism from D_2n to S_n

  • #1
1,462
44

Homework Statement


Find, with justification, an injective group homomorphism from ##D_{2n}## into ##S_n##.

Homework Equations




The Attempt at a Solution


So I'm thinking that the idea is to map ##r## and ##s## to elements in ##S_n## that obey the same relations that r and s satisfy. I can see how this might be done with a concrete example: maybe with n = 4 I could map r to (1234) and s to (24). But I don't really see how to do this in the general case.
 

Answers and Replies

  • #2
fresh_42
Mentor
Insights Author
2021 Award
16,706
16,070

Homework Statement


Find, with justification, an injective group homomorphism from ##D_{2n}## into ##S_n##.

Homework Equations




The Attempt at a Solution


So I'm thinking that the idea is to map ##r## and ##s## to elements in ##S_n## that obey the same relations that r and s satisfy. I can see how this might be done with a concrete example: maybe with n = 4 I could map r to (1234) and s to (24). But I don't really see how to do this in the general case.
The same way, I guess. I assume you defined ##D_{2n} = \langle r,s\,|\,r^n=s^2=srsr=1\rangle\,.## It would be more natural if you had it defined by geometric transformations. Wikipedia has the exact cycles.
 
  • #3
Infrared
Science Advisor
Gold Member
964
538
Label the vertices of a regular [itex]n[/itex]-gon with the numbers [itex]1,\ldots,n[/itex]. Then each element of [itex]D_{2n}[/itex] permutes these vertices and so defines a permutation of [itex]\{1,\ldots,n\}[/itex].

Edit: this is only a solution if you defined [itex]D_{2n}[/itex] as the group of symmetries of a regular [itex]n[/itex]-gon. If you defined it by relations, then you can still use this to see what permutations [itex]r[/itex] and [itex]s[/itex] correspond to.
 
  • #4
1,462
44
The same way, I guess. I assume you defined ##D_{2n} = \langle r,s\,|\,r^n=s^2=srsr=1\rangle\,.## It would be more natural if you had it defined by geometric transformations. Wikipedia has the exact cycles.
I'm using both the presentation and the symmetries of the n-gon to describe the group. Also, I'm not sure that's on the English Wikipedia article on the dihedral group.

But also, taking Infrared's advice, the permutation corresponding to ##r## is clear. It would be ##(123...n)##. However, the permutation corresponding to ##s## is less clear. I feel like it changes based on whether the n-gon is even or odd. I think in the even case it might look something like ##(2~~n)(3~~n-1)\dots (n/2~~n/2+2)##, but I'm not completely sure. This is the part that is confusing me.
 
  • #5
fresh_42
Mentor
Insights Author
2021 Award
16,706
16,070
I'm using both the presentation and the symmetries of the n-gon to describe the group. Also, I'm not sure that's on the English Wikipedia article on the dihedral group.
Nope, but for the formula you don't need to know the language. The first has already the solution.
 
  • #6
Infrared
Science Advisor
Gold Member
964
538
You're right that it will depend on whether [itex]n[/itex] is even or odd. Take the even case. Label the vertices from [itex]1[/itex] to [itex]n[/itex] counterclockwise, and reflect about the line of symmetry passing through the edge with endpoints labeled [itex]n[/itex] and [itex]1[/itex]. Where will [itex]k[/itex] be taken?
 
  • #7
1,462
44
You're right that it will depend on whether [itex]n[/itex] is even or odd. Take the even case. Label the vertices from [itex]1[/itex] to [itex]n[/itex] counterclockwise, and reflect about the line of symmetry passing through the edge with endpoints labeled [itex]n[/itex] and [itex]1[/itex]. Where will [itex]k[/itex] be taken?
First I don't see why the line through ##n## and ##1## would be a line of symmetry...
 
  • #8
Infrared
Science Advisor
Gold Member
964
538
I didn't say it was. I said to consider the line of symmetry passing through the edge with endpoints [itex]n[/itex] and [itex]1[/itex].
 
  • #9
1,462
44
I didn't say it was. I said to consider the line of symmetry passing through the edge with endpoints [itex]n[/itex] and [itex]1[/itex].
Do you mean, if we consider a a hexagon, labeled as such, then the resulting symmetry will be (13)(46) with 2 and 5 fixed?
 
  • #11
Infrared
Science Advisor
Gold Member
964
538
No. If you reflect about the line of symmetry bisecting the edge with endpoints [itex]n[/itex] and [itex]1[/itex], then [itex]1[/itex] and [itex]n[/itex] are swapped. You could instead reflect about a diagonal passing through opposite vertices like you did. This would give a permutation with two fixed points. Either is fine.

Edit: I think I see the point of confusion. I didn't intend 'passing though' the edge to mean 'containing' the edge. I meant that it intersects the edge. I should have been clearer.
 
  • Like
Likes Mr Davis 97
  • #12
1,462
44
No. If you reflect about the line of symmetry bisecting the edge with endpoints [itex]n[/itex] and [itex]1[/itex], then [itex]1[/itex] and [itex]n[/itex] are swapped. You could instead reflect about a diagonal passing through opposite vertices like you did. This would give a permutation with two fixed points. Either is fine.
So would this symmetry in general look like ##(1~~n-1)(2~~n-2)\dots (n/2-1~~n/2+1)##? And would the odd case look like ##(1~~n-1)(2~~n-2)\dots ((n-1)/2-1~~(n+1)/2)##?
 
  • #13
Infrared
Science Advisor
Gold Member
964
538
So would this symmetry in general look like ##(1~~n-1)(2~~n-2)\dots (n/2-1~~n/2+1)##? ##?

Almost, but you have an off-by-one error. It should be [itex](1~~n)(2~~n-1)\ldots (n/2~~n/2+1)[/itex]. What you wrote has [itex]n,n/2[/itex] as fixed points.
 
  • #15
Infrared
Science Advisor
Gold Member
964
538
That is reflection about the line passing through the vertices [itex]n,n/2[/itex]. This is fine, but I thought you were trying to write down the permutation corresponding to the reflection about my line of symmetry. Again, either works.
 
  • Like
Likes Mr Davis 97
  • #16
1,462
44
That is reflection about the line passing through the vertices [itex]n,n/2[/itex]. This is fine, but I thought you were trying to write down the permutation corresponding to the reflection about my line of symmetry. Again, either works.
Okay, assuming that these are the two permutations that I want, and I start with the even case, and I let ##\tau = (1~2~\dots~n)## and ##\sigma =(1~~n)(2~~n-1)\ldots (n/2~~n/2+1)##, how can I show that ##\sigma \tau = \tau^{-1} \sigma##? I tried by rote computation but it gets a little confusing how to write the products down. Also, it's obvious that ##\tau^n = 1## and ##\sigma^2 = 1##
 
  • #17
Infrared
Science Advisor
Gold Member
964
538
Working modulo [itex]n[/itex], note that [itex]\tau(k)=k+1[/itex] and [itex]\sigma(k)=-k+1[/itex]. This should make it clear.
 
  • #18
1,462
44
Working modulo [itex]n[/itex], note that [itex]\tau(k)=k+1[/itex] and [itex]\sigma(k)=-k+1[/itex]. This should make it clear.
Why is it the case that ##\sigma (k) = (-k + 1) \bmod n##? How did the -k+1 come from the sigma written as a permutation?

Edit: Actually, I think I can see it now.
 
  • #19
Infrared
Science Advisor
Gold Member
964
538
Look at each transposition in the factorization of [itex]\sigma[/itex]. The two terms always add up to [itex]n+1[/itex]. So [itex]\sigma(k)+k=n+1\cong 1\mod n[/itex].
 
  • Like
Likes Mr Davis 97
  • #20
1,462
44
Working modulo [itex]n[/itex], note that [itex]\tau(k)=k+1[/itex] and [itex]\sigma(k)=-k+1[/itex]. This should make it clear.
So now that I have found two elements in ##S_n##, with ##n## being even, that satisfy the same relations as ##r## and ##s##, how do I construct a homomorphism? If ##f## is my map then I suppose we have ##f(r)=\tau## and ##f(s) = \sigma##, but why does this show that we have a homomorphism? Not to mention we must also show this is injective...
 
  • #21
Infrared
Science Advisor
Gold Member
964
538
Every element in [itex]D_{2n}[/itex] can be written as a product [itex]s^ir^j[/itex] with [itex]i\in\{0,1\}[/itex] and [itex]j\in\{0,\ldots,n-1\}[/itex]. There is only one possible candidate for where to send such an element if you know where [itex]s,r[/itex] should go. It will be a well-defined homomorphism because of the relations we verified.
 
  • #22
1,462
44
Every element in [itex]D_{2n}[/itex] can be written as a product [itex]s^ir^j[/itex] with [itex]i\in\{0,1\}[/itex] and [itex]j\in\{0,\ldots,n-1\}[/itex]. There is only one possible candidate for where to send such an element if you know where [itex]s,r[/itex] should go. It will be a well-defined homomorphism because of the relations we verified.
So I want to show that ##f(s^ir^j) = \sigma^i \tau^j## is a homomorphism. Does the following justify it?

##f(ab) = f(s^i r^j s^k r^m) = f(s^{i+k}r^{-j+m}) = \sigma^{i+k} \tau^{-j+m} = \sigma^i \sigma^j \tau^k \tau^m = f(a)f(b)##
 
  • #23
Infrared
Science Advisor
Gold Member
964
538
You have a typo in the second to last term, but yes that's the right idea. Just say explicitly that you are using the relation we checked in your second to last equality.
 
  • #24
1,462
44
You have a typo in the second to last term, but yes that's the right idea. Just say explicitly that you are using the relation we checked in your second to last equality.
If the relation ##\sigma \tau = \tau^{-1} \sigma## is all we need for proving that ##f## is a homomorphism, then why do we need the relations ##\tau^n = 1## and ##\sigma^2 =1## to be true?
 
  • #25
Infrared
Science Advisor
Gold Member
964
538
It won't be well-defined otherwise: if [itex]s^ir^j=s^pr^q[/itex] (equivalently, [itex]i\equiv p\mod 2[/itex] and [itex]j\equiv q\mod n[/itex]), then we need [itex]f(s^ir^j)=f(s^pr^q)[/itex].

If instead you restrict the exponents to be in the intervals that I did, then this isn't an issue of checking that [itex]f[/itex] is well-defined (since there is only one way to put an element of [itex]D_n[/itex] into the desired form), but in this case we need these relations for [itex]f[/itex] to be a homomorphism since we would need to reduce the exponents of the outputs modulo [itex]2,n[/itex].
 
  • #26
1,462
44
It won't be well-defined otherwise: if [itex]s^ir^j=s^pr^q[/itex] (equivalently, [itex]i\equiv p\mod 2[/itex] and [itex]j\equiv q\mod n[/itex]), then we need [itex]f(s^ir^j)=f(s^pr^q)[/itex].

If instead you restrict the exponents to be in the intervals that I did, then this isn't an issue of checking that [itex]f[/itex] is well-defined (since there is only one way to put an element of [itex]D_n[/itex] into the desired form), but in this case we need these relations for [itex]f[/itex] to be a homomorphism since we would need to reduce the exponents of the outputs modulo [itex]2,n[/itex].
What would I need to do to formally prove that ##f## is well-defined given those two relations? It would seem that I need to show that ##s^ir^j = s^pr^q## implies that ##f(s^ir^j) = f(s^pr^q)##, but how to do this doesn't seem obvious
 
  • #27
Infrared
Science Advisor
Gold Member
964
538
Well-defined for us here just means that the value of the function is independent of how you represent its input. So you just need to check that [itex]\sigma^i\tau^j=\sigma^p\tau^q[/itex] in the above situation.

I'll repeat my remark above because I think it's slightly subtle: if you had represented your elements in the same way, but restricted the exponents as I did, then well-definedness is automatic since we only have one allowed way of representing elements. But then the work just gets shifted over to verifying that the map is a homomorphism, so we don't really gain anything.
 
  • #28
1,462
44
Well-defined for us here just means that the value of the function is independent of how you represent its input. So you just need to check that [itex]\sigma^i\tau^j=\sigma^p\tau^q[/itex] in the above situation.

I'll repeat my remark above because I think it's slightly subtle: if you had represented your elements in the same way, but restricted the exponents as I did, then well-definedness is automatic since we only have one allowed way of representing elements. But then the work just gets shifted over to verifying that the map is a homomorphism, so we don't really gain anything.
Why does the fact that ##\tau^n = 1## and ##\sigma^2 = 1## help us verify that ##\sigma^i\tau^j=\sigma^p\tau^q##? I kind of understand what you saying: like if ##|r|=4## and ##r^2 = r^6## then ##f(r^2) = f(r^6)## because ##f(r^6) = f(r)^6 = f(r)^2 = f(r^2)##. However, I'm not sure if this what you're saying or how to do it in the general case.
 
  • #29
Infrared
Science Advisor
Gold Member
964
538
If [itex]i\equiv p\mod 2[/itex], then [itex]i=p+2l[/itex] for some integer [itex]l[/itex]. This means [itex]\sigma^i=\sigma^{p+2l}=\sigma^p\sigma^{2l}=\sigma^p[/itex]. Likewise for the other term.
 
  • Like
Likes Mr Davis 97
  • #30
1,462
44
If [itex]i\equiv p\mod 2[/itex], then [itex]i=p+2l[/itex] for some integer [itex]l[/itex]. This means [itex]\sigma^i=\sigma^{p+2l}=\sigma^p\sigma^{2l}=\sigma^p[/itex]. Likewise for the other term.
Alright, I think this is the last thing. How do I show that ##f## is injective? All I can think to do is show that the kernel is 1 only, but I am not seeing how to do this in practice.
 
  • #31
Infrared
Science Advisor
Gold Member
964
538
Every element of [itex]D_{2n}[/itex] is either of the form [itex]r^i[/itex] or [itex]sr^i[/itex] for some [itex]i[/itex]. The first case maps to [itex]\tau^i[/itex], which is addition by [itex]i[/itex] modulo [itex]n[/itex], so can only be the identity if [itex]i[/itex] is a multiple of [itex]n[/itex], meaning that [itex]r^i=1[/itex]. The second case maps to [itex]\sigma\tau^i[/itex]. This permutation takes [itex]1[/itex] to [itex]-i[/itex], so could only possibly be trivial if [itex]i=n-1[/itex]. But in that case it doesn't fix [itex]n[/itex].

I think I gave you too much help. In the future, maybe try more on your own.
 
  • Like
Likes Mr Davis 97
  • #32
1,462
44
Every element of [itex]D_{2n}[/itex] is either of the form [itex]r^i[/itex] or [itex]sr^i[/itex] for some [itex]i[/itex]. The first case maps to [itex]\tau^i[/itex], which is addition by [itex]i[/itex] modulo [itex]n[/itex], so can only be the identity if [itex]i[/itex] is a multiple of [itex]n[/itex], meaning that [itex]r^i=1[/itex]. The second case maps to [itex]\sigma\tau^i[/itex]. This permutation takes [itex]1[/itex] to [itex]-i[/itex], so could only possibly be trivial if [itex]i=n-1[/itex]. But in that case it doesn't fix [itex]n[/itex].

I think I gave you too much help. In the future, maybe try more on your own.
I actually have one more question. I'm trying to find the cycle type of each element in the image of the homomorphism. I think I worked out correctly that the cycle type of ##\tau^i## is ##\displaystyle \frac{n}{\operatorname{gcd} (i,n)}##, repeated as many times as need to get ##n##. For example, if ##n = 16## then ##\tau^4## has cycle type 4,4,4,4. Is this right?

Also, I need a bit of help figuring out what the cycle type for ##f(sr^i)## would be for any ##i##.
 
  • #33
Infrared
Science Advisor
Gold Member
964
538
Why do you need to find the cycle type?
In any event, yes, that expression is correct. The [itex]sr^i[/itex] are all reflections, so will map to a product of [itex]n/2[/itex] disjoint transpositions if the line of reflection is through an edge, and [itex]n/2-1[/itex] disjoint transpositions if the line of reflection is through opposite vertices.
 
  • Like
Likes Mr Davis 97
  • #34
1,462
44
Why do you need to find the cycle type?
In any event, yes, that expression is correct. The [itex]sr^i[/itex] are all reflections, so will map to a product of [itex]n/2[/itex] disjoint transpositions if the line of reflection is through an edge, and [itex]n/2-1[/itex] disjoint transpositions if the line of reflection is through opposite vertices.
It's just an additional aspect of the problem. So I think this is all the help I need. Just one more thing. Do I have to do all of this again for the case when ##n## is odd? That would seem to be very tedious....
 
  • #35
Infrared
Science Advisor
Gold Member
964
538
Most of the work is very similar/identical, so you can probably get away with saying something like "by arguing as before, we have...".
 
  • Like
Likes Mr Davis 97

Related Threads on Find injective homomorphism from D_2n to S_n

Replies
19
Views
940
  • Last Post
Replies
1
Views
2K
Replies
5
Views
5K
  • Last Post
Replies
7
Views
5K
Replies
8
Views
1K
Replies
5
Views
4K
Replies
1
Views
981
Replies
2
Views
1K
Replies
19
Views
2K
Top