Counting permutations in $S_n$ which take an n-cycle to another n-cycle under conjugation
Given two fixed $n$-cycles in $S_n$, $alpha$ and $beta$, I want to find how many unique $sigma in S_n$ satisfy
$$sigma alpha sigma^{-1} = beta$$
In class, we have already learned that conjugation preserves cycle type. I have attacked this problem several times and believe it to be $n$, but I would like to verify if this proof holds and if there is an easier way to do this. My attempt goes like:
- Fix an element $a_1$ in ${1,2,...,n}$
- Represent $alpha$ as $(a_1, alpha(a_1), alpha^2(a_1), ... alpha^{n-1}(a_1) )$
- Denote $Sigma$ the set of all permutations $sigma$ satisfying the above
- Partition $Sigma$ into $n$ disjoint subsests ${Sigma_1, Sigma_2, ... Sigma_n}$, where $sigma in Sigma_i$ if $sigma(a_1) = i$
- Construct the permutation $sigma_i$, which we define:
$$ sigma_i(a_1)=i \ sigma_i(a_i)=beta^{i-1}(i) $$
Hence the cycle representation of $sigma_i alpha sigma_i^{-1}$ is $$(sigma_i(a_1), sigma_i(a_2),...,sigma_i(a_n))=(i,beta(i),beta^2(i),...,beta^{n-1}(i))$$
The right side is a representation of $beta$, so we have $sigma_i in Sigma_i subset Sigma$
Suppose a given subset $Sigma_i$ had some other element in it, $bar{sigma_i}$. Then $bar{sigma_i}$ and $sigma_i$ must agree on $a_1$ since they both lie in $Sigma_i$, and they must disagree on some other element $a_l$. We may as well choose $l$ such that it is the minimal such positive index which this occurs- i.e., $sigma_i$ and $bar{sigma_i}$ agree for all $a_i$ for $i < l$. Then the cycle representation of $bar{sigma_i} alpha bar{sigma_i}^{-1}$ is
$$(bar{sigma_i}(a_1),bar{sigma_i}(a_2),...bar{sigma_i}(a_n)) = (i,beta(i),...,beta^{l-2}(i), mathbf{bar{sigma_i}(a_l)}, bar{sigma_i}(a_{l+1}),...bar{sigma_i}(a_n)) $$
I have put the $l$th element in boldface to indicate that it is strictly not equal to $beta^{l-1}(a_l)$ by assumption. Clearly this is a contradiction because this is no longer a representation of the cycle $beta$. Thus we cannot construct any members of $Sigma_i$ which differ from the permutation $sigma_i$. That is, each $Sigma_i$ is a singleton.
Thus, the collection of permutations $Sigma$ that we want is partitioned into exactly $n$ singleton sets, and hence $|Sigma|=n$.
I am not very happy with the proof I have given, as essentially it consists of explicitly constructing all of the permutations and proving their uniqueness, so it seems like the least effective method. It seems very plausible to me that this could be done somehow using group actions, but I'm not sure how. Any help would be appreciated.
abstract-algebra group-theory symmetric-groups
asked Dec 7 at 21:23
Gannon Earhart
62
add a comment |
Given two fixed $n$-cycles in $S_n$, $alpha$ and $beta$, I want to find how many unique $sigma in S_n$ satisfy
$$sigma alpha sigma^{-1} = beta$$
In class, we have already learned that conjugation preserves cycle type. I have attacked this problem several times and believe it to be $n$, but I would like to verify if this proof holds and if there is an easier way to do this. My attempt goes like:
- Fix an element $a_1$ in ${1,2,...,n}$
- Represent $alpha$ as $(a_1, alpha(a_1), alpha^2(a_1), ... alpha^{n-1}(a_1) )$
- Denote $Sigma$ the set of all permutations $sigma$ satisfying the above
- Partition $Sigma$ into $n$ disjoint subsests ${Sigma_1, Sigma_2, ... Sigma_n}$, where $sigma in Sigma_i$ if $sigma(a_1) = i$
- Construct the permutation $sigma_i$, which we define:
$$ sigma_i(a_1)=i \ sigma_i(a_i)=beta^{i-1}(i) $$
Hence the cycle representation of $sigma_i alpha sigma_i^{-1}$ is $$(sigma_i(a_1), sigma_i(a_2),...,sigma_i(a_n))=(i,beta(i),beta^2(i),...,beta^{n-1}(i))$$
The right side is a representation of $beta$, so we have $sigma_i in Sigma_i subset Sigma$
Suppose a given subset $Sigma_i$ had some other element in it, $bar{sigma_i}$. Then $bar{sigma_i}$ and $sigma_i$ must agree on $a_1$ since they both lie in $Sigma_i$, and they must disagree on some other element $a_l$. We may as well choose $l$ such that it is the minimal such positive index which this occurs- i.e., $sigma_i$ and $bar{sigma_i}$ agree for all $a_i$ for $i < l$. Then the cycle representation of $bar{sigma_i} alpha bar{sigma_i}^{-1}$ is
$$(bar{sigma_i}(a_1),bar{sigma_i}(a_2),...bar{sigma_i}(a_n)) = (i,beta(i),...,beta^{l-2}(i), mathbf{bar{sigma_i}(a_l)}, bar{sigma_i}(a_{l+1}),...bar{sigma_i}(a_n)) $$
I have put the $l$th element in boldface to indicate that it is strictly not equal to $beta^{l-1}(a_l)$ by assumption. Clearly this is a contradiction because this is no longer a representation of the cycle $beta$. Thus we cannot construct any members of $Sigma_i$ which differ from the permutation $sigma_i$. That is, each $Sigma_i$ is a singleton.
Thus, the collection of permutations $Sigma$ that we want is partitioned into exactly $n$ singleton sets, and hence $|Sigma|=n$.
I am not very happy with the proof I have given, as essentially it consists of explicitly constructing all of the permutations and proving their uniqueness, so it seems like the least effective method. It seems very plausible to me that this could be done somehow using group actions, but I'm not sure how. Any help would be appreciated.
abstract-algebra group-theory symmetric-groups
asked Dec 7 at 21:23
Gannon Earhart
62
1
I haven't read your proof, but have a comment that may help. The number of permutations that conjugate $alpha$ to $beta$ is independent of $beta$, so the same as the number that fix $alpha$.
– Ethan Bolker
Dec 7 at 21:27
Also another relevant fact is: not only does conjugation preserve cycle type, but a cycle's conjugacy class is ALL permutations with the same cycle type.
– user25959
Dec 7 at 21:33
Hmm, conjugation does induce an action of $S_n$ on the set of $n$-cycles which has size $(n-1)!$.
– Daniel Schepler
Dec 7 at 21:59
add a comment |
Given two fixed $n$-cycles in $S_n$, $alpha$ and $beta$, I want to find how many unique $sigma in S_n$ satisfy
$$sigma alpha sigma^{-1} = beta$$
In class, we have already learned that conjugation preserves cycle type. I have attacked this problem several times and believe it to be $n$, but I would like to verify if this proof holds and if there is an easier way to do this. My attempt goes like:
- Fix an element $a_1$ in ${1,2,...,n}$
- Represent $alpha$ as $(a_1, alpha(a_1), alpha^2(a_1), ... alpha^{n-1}(a_1) )$
- Denote $Sigma$ the set of all permutations $sigma$ satisfying the above
- Partition $Sigma$ into $n$ disjoint subsests ${Sigma_1, Sigma_2, ... Sigma_n}$, where $sigma in Sigma_i$ if $sigma(a_1) = i$
- Construct the permutation $sigma_i$, which we define:
$$ sigma_i(a_1)=i \ sigma_i(a_i)=beta^{i-1}(i) $$
Hence the cycle representation of $sigma_i alpha sigma_i^{-1}$ is $$(sigma_i(a_1), sigma_i(a_2),...,sigma_i(a_n))=(i,beta(i),beta^2(i),...,beta^{n-1}(i))$$
The right side is a representation of $beta$, so we have $sigma_i in Sigma_i subset Sigma$
Suppose a given subset $Sigma_i$ had some other element in it, $bar{sigma_i}$. Then $bar{sigma_i}$ and $sigma_i$ must agree on $a_1$ since they both lie in $Sigma_i$, and they must disagree on some other element $a_l$. We may as well choose $l$ such that it is the minimal such positive index which this occurs- i.e., $sigma_i$ and $bar{sigma_i}$ agree for all $a_i$ for $i < l$. Then the cycle representation of $bar{sigma_i} alpha bar{sigma_i}^{-1}$ is
$$(bar{sigma_i}(a_1),bar{sigma_i}(a_2),...bar{sigma_i}(a_n)) = (i,beta(i),...,beta^{l-2}(i), mathbf{bar{sigma_i}(a_l)}, bar{sigma_i}(a_{l+1}),...bar{sigma_i}(a_n)) $$
I have put the $l$th element in boldface to indicate that it is strictly not equal to $beta^{l-1}(a_l)$ by assumption. Clearly this is a contradiction because this is no longer a representation of the cycle $beta$. Thus we cannot construct any members of $Sigma_i$ which differ from the permutation $sigma_i$. That is, each $Sigma_i$ is a singleton.
Thus, the collection of permutations $Sigma$ that we want is partitioned into exactly $n$ singleton sets, and hence $|Sigma|=n$.
I am not very happy with the proof I have given, as essentially it consists of explicitly constructing all of the permutations and proving their uniqueness, so it seems like the least effective method. It seems very plausible to me that this could be done somehow using group actions, but I'm not sure how. Any help would be appreciated.
abstract-algebra group-theory symmetric-groups
asked Dec 7 at 21:23
Gannon Earhart
62
Given two fixed $n$-cycles in $S_n$, $alpha$ and $beta$, I want to find how many unique $sigma in S_n$ satisfy
$$sigma alpha sigma^{-1} = beta$$
In class, we have already learned that conjugation preserves cycle type. I have attacked this problem several times and believe it to be $n$, but I would like to verify if this proof holds and if there is an easier way to do this. My attempt goes like:
- Fix an element $a_1$ in ${1,2,...,n}$
- Represent $alpha$ as $(a_1, alpha(a_1), alpha^2(a_1), ... alpha^{n-1}(a_1) )$
- Denote $Sigma$ the set of all permutations $sigma$ satisfying the above
- Partition $Sigma$ into $n$ disjoint subsests ${Sigma_1, Sigma_2, ... Sigma_n}$, where $sigma in Sigma_i$ if $sigma(a_1) = i$
- Construct the permutation $sigma_i$, which we define:
$$ sigma_i(a_1)=i \ sigma_i(a_i)=beta^{i-1}(i) $$
Hence the cycle representation of $sigma_i alpha sigma_i^{-1}$ is $$(sigma_i(a_1), sigma_i(a_2),...,sigma_i(a_n))=(i,beta(i),beta^2(i),...,beta^{n-1}(i))$$
The right side is a representation of $beta$, so we have $sigma_i in Sigma_i subset Sigma$
Suppose a given subset $Sigma_i$ had some other element in it, $bar{sigma_i}$. Then $bar{sigma_i}$ and $sigma_i$ must agree on $a_1$ since they both lie in $Sigma_i$, and they must disagree on some other element $a_l$. We may as well choose $l$ such that it is the minimal such positive index which this occurs- i.e., $sigma_i$ and $bar{sigma_i}$ agree for all $a_i$ for $i < l$. Then the cycle representation of $bar{sigma_i} alpha bar{sigma_i}^{-1}$ is
$$(bar{sigma_i}(a_1),bar{sigma_i}(a_2),...bar{sigma_i}(a_n)) = (i,beta(i),...,beta^{l-2}(i), mathbf{bar{sigma_i}(a_l)}, bar{sigma_i}(a_{l+1}),...bar{sigma_i}(a_n)) $$
I have put the $l$th element in boldface to indicate that it is strictly not equal to $beta^{l-1}(a_l)$ by assumption. Clearly this is a contradiction because this is no longer a representation of the cycle $beta$. Thus we cannot construct any members of $Sigma_i$ which differ from the permutation $sigma_i$. That is, each $Sigma_i$ is a singleton.
Thus, the collection of permutations $Sigma$ that we want is partitioned into exactly $n$ singleton sets, and hence $|Sigma|=n$.
I am not very happy with the proof I have given, as essentially it consists of explicitly constructing all of the permutations and proving their uniqueness, so it seems like the least effective method. It seems very plausible to me that this could be done somehow using group actions, but I'm not sure how. Any help would be appreciated.
abstract-algebra group-theory symmetric-groups
abstract-algebra group-theory symmetric-groups
asked Dec 7 at 21:23
Gannon Earhart
62
asked Dec 7 at 21:23
Gannon Earhart
62
asked Dec 7 at 21:23
Gannon Earhart
62
asked Dec 7 at 21:23
Gannon Earhart
62
asked Dec 7 at 21:23
Gannon Earhart
62
62
1
I haven't read your proof, but have a comment that may help. The number of permutations that conjugate $alpha$ to $beta$ is independent of $beta$, so the same as the number that fix $alpha$.
– Ethan Bolker
Dec 7 at 21:27
Also another relevant fact is: not only does conjugation preserve cycle type, but a cycle's conjugacy class is ALL permutations with the same cycle type.
– user25959
Dec 7 at 21:33
Hmm, conjugation does induce an action of $S_n$ on the set of $n$-cycles which has size $(n-1)!$.
– Daniel Schepler
Dec 7 at 21:59
add a comment |
1
I haven't read your proof, but have a comment that may help. The number of permutations that conjugate $alpha$ to $beta$ is independent of $beta$, so the same as the number that fix $alpha$.
– Ethan Bolker
Dec 7 at 21:27
Also another relevant fact is: not only does conjugation preserve cycle type, but a cycle's conjugacy class is ALL permutations with the same cycle type.
– user25959
Dec 7 at 21:33
Hmm, conjugation does induce an action of $S_n$ on the set of $n$-cycles which has size $(n-1)!$.
– Daniel Schepler
Dec 7 at 21:59
1
1
I haven't read your proof, but have a comment that may help. The number of permutations that conjugate $alpha$ to $beta$ is independent of $beta$, so the same as the number that fix $alpha$.
– Ethan Bolker
Dec 7 at 21:27
I haven't read your proof, but have a comment that may help. The number of permutations that conjugate $alpha$ to $beta$ is independent of $beta$, so the same as the number that fix $alpha$.
– Ethan Bolker
Dec 7 at 21:27
Also another relevant fact is: not only does conjugation preserve cycle type, but a cycle's conjugacy class is ALL permutations with the same cycle type.
– user25959
Dec 7 at 21:33
Also another relevant fact is: not only does conjugation preserve cycle type, but a cycle's conjugacy class is ALL permutations with the same cycle type.
– user25959
Dec 7 at 21:33
Hmm, conjugation does induce an action of $S_n$ on the set of $n$-cycles which has size $(n-1)!$.
– Daniel Schepler
Dec 7 at 21:59
Hmm, conjugation does induce an action of $S_n$ on the set of $n$-cycles which has size $(n-1)!$.
– Daniel Schepler
Dec 7 at 21:59
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3030379%2fcounting-permutations-in-s-n-which-take-an-n-cycle-to-another-n-cycle-under-co%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3030379%2fcounting-permutations-in-s-n-which-take-an-n-cycle-to-another-n-cycle-under-co%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
I haven't read your proof, but have a comment that may help. The number of permutations that conjugate $alpha$ to $beta$ is independent of $beta$, so the same as the number that fix $alpha$.
– Ethan Bolker
Dec 7 at 21:27
Also another relevant fact is: not only does conjugation preserve cycle type, but a cycle's conjugacy class is ALL permutations with the same cycle type.
– user25959
Dec 7 at 21:33
Hmm, conjugation does induce an action of $S_n$ on the set of $n$-cycles which has size $(n-1)!$.
– Daniel Schepler
Dec 7 at 21:59