Find injective homomorphism from D_2n to S_n

  • Thread starter Mr Davis 97
  • Start date
  • Tags
    Injective
In summary: Edit: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/2-1~~n/2+1)?
  • #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.
 
Physics news on Phys.org
  • #2
Mr Davis 97 said:

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
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
fresh_42 said:
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
Mr Davis 97 said:
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
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
Infrared said:
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
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
Infrared said:
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
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
Infrared said:
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
Mr Davis 97 said:
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
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
Infrared said:
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
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
Infrared said:
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
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
Infrared said:
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
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
Infrared said:
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
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
Infrared said:
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
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
Infrared said:
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
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
Infrared said:
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
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
Infrared said:
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
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
Infrared said:
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
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
Infrared said:
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
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

Suggested for: Find injective homomorphism from D_2n to S_n

Back
Top