Find injective homomorphism from D_2n to S_n

[Mr Davis 97]

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.

 

[fresh_42]

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.

 

[Infrared]

Label the vertices of a regular $n$-gon with the numbers $1,\ldots,n$. Then each element of $D_{2n}$ permutes these vertices and so defines a permutation of $\{1,\ldots,n\}$.

Edit: this is only a solution if you defined $D_{2n}$ as the group of symmetries of a regular $n$-gon. If you defined it by relations, then you can still use this to see what permutations $r$ and $s$ correspond to.

 

[Mr Davis 97]

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.

 

[fresh_42]

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.

 

[Infrared]

You're right that it will depend on whether $n$ is even or odd. Take the even case. Label the vertices from $1$ to $n$ counterclockwise, and reflect about the line of symmetry passing through the edge with endpoints labeled $n$ and $1$. Where will $k$ be taken?

 

[Mr Davis 97]

You're right that it will depend on whether $n$ is even or odd. Take the even case. Label the vertices from $1$ to $n$ counterclockwise, and reflect about the line of symmetry passing through the edge with endpoints labeled $n$ and $1$. Where will $k$ be taken?

First I don't see why the line through $n$ and $1$ would be a line of symmetry...

 

[Infrared]

I didn't say it was. I said to consider the line of symmetry passing through the edge with endpoints $n$ and $1$.

 

[Mr Davis 97]

I didn't say it was. I said to consider the line of symmetry passing through the edge with endpoints $n$ and $1$.

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?

 

[Mr Davis 97]

Nope, but for the formula you don't need to know the language. The first has already the solution.

Is this what you mean? https://de.wikipedia.org/wiki/Diedergruppe#Permutations-Darstellung

 

[Infrared]

No. If you reflect about the line of symmetry bisecting the edge with endpoints $n$ and $1$, then $1$ and $n$ 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.

 

[Mr Davis 97]

No. If you reflect about the line of symmetry bisecting the edge with endpoints $n$ and $1$, then $1$ and $n$ 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)$?

 

[Infrared]

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 $(1~~n)(2~~n-1)\ldots (n/2~~n/2+1)$. What you wrote has $n,n/2$ as fixed points.

 

[Mr Davis 97]

Almost, but you have an off-by-one error. It should be $(1~~n)(2~~n-1)\ldots (n/2~~n/2+1)$. What you wrote has $n,n/2$ as fixed points.

Why in this https://de.wikipedia.org/wiki/Diedergruppe#Permutations-Darstellung does it have what I wrote down?

 

[Infrared]

That is reflection about the line passing through the vertices $n,n/2$. 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.

 

[Mr Davis 97]

That is reflection about the line passing through the vertices $n,n/2$. 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$

 

[Infrared]

Working modulo $n$, note that $\tau(k)=k+1$ and $\sigma(k)=-k+1$. This should make it clear.

 

[Mr Davis 97]

Working modulo $n$, note that $\tau(k)=k+1$ and $\sigma(k)=-k+1$. 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.

 

[Infrared]

Look at each transposition in the factorization of $\sigma$. The two terms always add up to $n+1$. So $\sigma(k)+k=n+1\cong 1\mod n$.

 

[Mr Davis 97]

Working modulo $n$, note that $\tau(k)=k+1$ and $\sigma(k)=-k+1$. 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...

 

[Infrared]

Every element in $D_{2n}$ can be written as a product $s^ir^j$ with $i\in\{0,1\}$ and $j\in\{0,\ldots,n-1\}$. There is only one possible candidate for where to send such an element if you know where $s,r$ should go. It will be a well-defined homomorphism because of the relations we verified.

 

[Mr Davis 97]

Every element in $D_{2n}$ can be written as a product $s^ir^j$ with $i\in\{0,1\}$ and $j\in\{0,\ldots,n-1\}$. There is only one possible candidate for where to send such an element if you know where $s,r$ 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)$

 

[Infrared]

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.

 

[Mr Davis 97]

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?

 

[Infrared]

It won't be well-defined otherwise: if $s^ir^j=s^pr^q$ (equivalently, $i\equiv p\mod 2$ and $j\equiv q\mod n$), then we need $f(s^ir^j)=f(s^pr^q)$.

If instead you restrict the exponents to be in the intervals that I did, then this isn't an issue of checking that $f$ is well-defined (since there is only one way to put an element of $D_n$ into the desired form), but in this case we need these relations for $f$ to be a homomorphism since we would need to reduce the exponents of the outputs modulo $2,n$.

 

[Mr Davis 97]

It won't be well-defined otherwise: if $s^ir^j=s^pr^q$ (equivalently, $i\equiv p\mod 2$ and $j\equiv q\mod n$), then we need $f(s^ir^j)=f(s^pr^q)$.

If instead you restrict the exponents to be in the intervals that I did, then this isn't an issue of checking that $f$ is well-defined (since there is only one way to put an element of $D_n$ into the desired form), but in this case we need these relations for $f$ to be a homomorphism since we would need to reduce the exponents of the outputs modulo $2,n$.

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

 

[Infrared]

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 $\sigma^i\tau^j=\sigma^p\tau^q$ 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.

 

[Mr Davis 97]

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 $\sigma^i\tau^j=\sigma^p\tau^q$ 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.

 

[Infrared]

If $i\equiv p\mod 2$, then $i=p+2l$ for some integer $l$. This means $\sigma^i=\sigma^{p+2l}=\sigma^p\sigma^{2l}=\sigma^p$. Likewise for the other term.

 

[Mr Davis 97]

If $i\equiv p\mod 2$, then $i=p+2l$ for some integer $l$. This means $\sigma^i=\sigma^{p+2l}=\sigma^p\sigma^{2l}=\sigma^p$. 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.

 

[Infrared]

Every element of $D_{2n}$ is either of the form $r^i$ or $sr^i$ for some $i$. The first case maps to $\tau^i$, which is addition by $i$ modulo $n$, so can only be the identity if $i$ is a multiple of $n$, meaning that $r^i=1$. The second case maps to $\sigma\tau^i$. This permutation takes $1$ to $-i$, so could only possibly be trivial if $i=n-1$. But in that case it doesn't fix $n$.

I think I gave you too much help. In the future, maybe try more on your own.

 

[Mr Davis 97]

Every element of $D_{2n}$ is either of the form $r^i$ or $sr^i$ for some $i$. The first case maps to $\tau^i$, which is addition by $i$ modulo $n$, so can only be the identity if $i$ is a multiple of $n$, meaning that $r^i=1$. The second case maps to $\sigma\tau^i$. This permutation takes $1$ to $-i$, so could only possibly be trivial if $i=n-1$. But in that case it doesn't fix $n$.

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$.

 

[Infrared]

Why do you need to find the cycle type?
In any event, yes, that expression is correct. The $sr^i$ are all reflections, so will map to a product of $n/2$ disjoint transpositions if the line of reflection is through an edge, and $n/2-1$ disjoint transpositions if the line of reflection is through opposite vertices.

 

[Mr Davis 97]

Why do you need to find the cycle type?
In any event, yes, that expression is correct. The $sr^i$ are all reflections, so will map to a product of $n/2$ disjoint transpositions if the line of reflection is through an edge, and $n/2-1$ 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...

 

[Infrared]

Most of the work is very similar/identical, so you can probably get away with saying something like "by arguing as before, we have...".