• Support PF! Buy your school textbooks, materials and every day products Here!

Find injective homomorphism from D_2n to S_n

  • #1
1,456
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
12,689
9,232

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
578
242
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,456
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
12,689
9,232
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
578
242
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,456
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
578
242
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,456
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
578
242
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.
 
  • #12
1,456
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
578
242
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
578
242
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.
 
  • #16
1,456
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
578
242
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,456
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
578
242
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].
 
  • #20
1,456
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
578
242
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,456
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
578
242
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,456
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
578
242
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].
 

Related Threads on Find injective homomorphism from D_2n to S_n

Replies
19
Views
668
Replies
5
Views
4K
Replies
1
Views
800
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
5
Views
3K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
9
Views
4K
Top