Chain Of Transpositions Raised To A Power And Its Orbits The Next CEO of Stack OverflowIs $S_n$ generated by a maximum of n-2 transpositions?Proof that no permutation can be expressed both as the product of an even number of transpositions and as a product of an odd number of transpositionsconfusion over transpositions and cycle notationOrbits of action of $SL_m(mathbbZ)$ on $mathbbZ^m$Permutation cyclesWhy do we swap the position in the cycle when writing disjoint cyclesCount Orbits and stabilizerVisualizing Orbits and TransitivityClarification of $G$-orbits acting on a finite set $X$ and subspaces of $mathbbC[X].$Proving two binomial coefficient identities based on the expansion of $(1 + x)^2n$
What happened in Rome, when the western empire "fell"?
Raspberry pi 3 B with Ubuntu 18.04 server arm64: what chip
Can this note be analyzed as a non-chord tone?
Getting Stale Gas Out of a Gas Tank w/out Dropping the Tank
Is there a difference between "Fahrstuhl" and "Aufzug"?
What is the difference between "hamstring tendon" and "common hamstring tendon"?
Airplane gently rocking its wings during whole flight
Is Nisuin Biblical or Rabbinic?
Man transported from Alternate World into ours by a Neutrino Detector
Reshaping json / reparing json inside shell script (remove trailing comma)
Can you teleport closer to a creature you are Frightened of?
What day is it again?
Do I need to write [sic] when including a quotation with a number less than 10 that isn't written out?
Do scriptures give a method to recognize a truly self-realized person/jivanmukta?
It is correct to match light sources with the same color temperature?
how one can write a nice vector parser, something that does pgfvecparseA=B-C; D=E x F;
Is dried pee considered dirt?
Could a dragon use its wings to swim?
Is it ever safe to open a suspicious HTML file (e.g. email attachment)?
Players Circumventing the limitations of Wish
Won the lottery - how do I keep the money?
Why do we say 'Un seul M' and not 'Une seule M' even though M is a "consonne"
Traveling with my 5 year old daughter (as the father) without the mother from Germany to Mexico
TikZ: How to fill area with a special pattern?
Chain Of Transpositions Raised To A Power And Its Orbits
The Next CEO of Stack OverflowIs $S_n$ generated by a maximum of n-2 transpositions?Proof that no permutation can be expressed both as the product of an even number of transpositions and as a product of an odd number of transpositionsconfusion over transpositions and cycle notationOrbits of action of $SL_m(mathbbZ)$ on $mathbbZ^m$Permutation cyclesWhy do we swap the position in the cycle when writing disjoint cyclesCount Orbits and stabilizerVisualizing Orbits and TransitivityClarification of $G$-orbits acting on a finite set $X$ and subspaces of $mathbbC[X].$Proving two binomial coefficient identities based on the expansion of $(1 + x)^2n$
$begingroup$
Suppose we have a set of $n$ elements which we would like to permute. Let $beginpmatrix i & jendpmatrix$ denote the transposition (the swapping) of elements $i$ and $j$.
I would like to prove that $(beginpmatrix 1 & 2endpmatrixbeginpmatrix 2 & 3endpmatrixldotsbeginpmatrix n-1 & nendpmatrix)^m$ has exactly one orbit if and only if $m$ and $n$ are relatively prime.
I'm very stuck on how to prove this.
group-theory permutations permutation-cycles
asked Mar 28 at 3:40
Frederic ChopinFrederic Chopin
357111
$endgroup$
add a comment |
$begingroup$
Suppose we have a set of $n$ elements which we would like to permute. Let $beginpmatrix i & jendpmatrix$ denote the transposition (the swapping) of elements $i$ and $j$.
I would like to prove that $(beginpmatrix 1 & 2endpmatrixbeginpmatrix 2 & 3endpmatrixldotsbeginpmatrix n-1 & nendpmatrix)^m$ has exactly one orbit if and only if $m$ and $n$ are relatively prime.
I'm very stuck on how to prove this.
group-theory permutations permutation-cycles
asked Mar 28 at 3:40
Frederic ChopinFrederic Chopin
357111
$endgroup$
$begingroup$
Do you mean that you want to prove $((1 2)(2 3) cdots (n-1 n))^m$ has exactly one cycle in its cyclic decomposition iff $m$ and $n$ are relatively prime?
$endgroup$
– M. Vinay
Mar 28 at 5:07
$begingroup$
That's right, yes
$endgroup$
– Frederic Chopin
Mar 28 at 5:21
add a comment |
$begingroup$
Suppose we have a set of $n$ elements which we would like to permute. Let $beginpmatrix i & jendpmatrix$ denote the transposition (the swapping) of elements $i$ and $j$.
I would like to prove that $(beginpmatrix 1 & 2endpmatrixbeginpmatrix 2 & 3endpmatrixldotsbeginpmatrix n-1 & nendpmatrix)^m$ has exactly one orbit if and only if $m$ and $n$ are relatively prime.
I'm very stuck on how to prove this.
group-theory permutations permutation-cycles
asked Mar 28 at 3:40
Frederic ChopinFrederic Chopin
357111
$endgroup$
Suppose we have a set of $n$ elements which we would like to permute. Let $beginpmatrix i & jendpmatrix$ denote the transposition (the swapping) of elements $i$ and $j$.
I would like to prove that $(beginpmatrix 1 & 2endpmatrixbeginpmatrix 2 & 3endpmatrixldotsbeginpmatrix n-1 & nendpmatrix)^m$ has exactly one orbit if and only if $m$ and $n$ are relatively prime.
I'm very stuck on how to prove this.
group-theory permutations permutation-cycles
group-theory permutations permutation-cycles
asked Mar 28 at 3:40
Frederic ChopinFrederic Chopin
357111
asked Mar 28 at 3:40
Frederic ChopinFrederic Chopin
357111
asked Mar 28 at 3:40
Frederic ChopinFrederic Chopin
357111
asked Mar 28 at 3:40
Frederic ChopinFrederic Chopin
357111
asked Mar 28 at 3:40
Frederic ChopinFrederic Chopin
357111
357111
$begingroup$
Do you mean that you want to prove $((1 2)(2 3) cdots (n-1 n))^m$ has exactly one cycle in its cyclic decomposition iff $m$ and $n$ are relatively prime?
$endgroup$
– M. Vinay
Mar 28 at 5:07
$begingroup$
That's right, yes
$endgroup$
– Frederic Chopin
Mar 28 at 5:21
add a comment |
$begingroup$
Do you mean that you want to prove $((1 2)(2 3) cdots (n-1 n))^m$ has exactly one cycle in its cyclic decomposition iff $m$ and $n$ are relatively prime?
$endgroup$
– M. Vinay
Mar 28 at 5:07
$begingroup$
That's right, yes
$endgroup$
– Frederic Chopin
Mar 28 at 5:21
$begingroup$
Do you mean that you want to prove $((1 2)(2 3) cdots (n-1 n))^m$ has exactly one cycle in its cyclic decomposition iff $m$ and $n$ are relatively prime?
$endgroup$
– M. Vinay
Mar 28 at 5:07
$begingroup$
Do you mean that you want to prove $((1 2)(2 3) cdots (n-1 n))^m$ has exactly one cycle in its cyclic decomposition iff $m$ and $n$ are relatively prime?
$endgroup$
– M. Vinay
Mar 28 at 5:07
$begingroup$
That's right, yes
$endgroup$
– Frederic Chopin
Mar 28 at 5:21
$begingroup$
That's right, yes
$endgroup$
– Frederic Chopin
Mar 28 at 5:21
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Without loss of generality, let us take the left-to-right composition convention (i.e., assume that the permutation is acting from the right).
Then simply observe that the permutation $pi = ((1 2)(2 3) cdots (n-1 n))$ maps each $i$ to $i - 1 mod n$ (so, $1 mapsto n = 0$; $2 mapsto 1$, …, $n mapsto n - 1$).
Thus, $pi^m$ maps each $i$ to $i - m mod n$. Now, let $k$ ($1 le k le n$) be the length of the cycle containing $1$ in the cyclic decomposition of $pi^m$. That is, $k$ is the least positive integer such that
$$1 mapsto (1 - m) mapsto (1 - 2m) mapsto cdots mapsto (1 - (k - 1)m) mapsto (1 - km) = 1.$$
That is, $k$ is the least positive integer such that $km equiv 0 mod n$. Then $k = n$ if and only if $m$ and $n$ are relatively prime. Note that there is exactly one cycle in the decomposition if and only if $k = n$.
answered Mar 28 at 5:46
M. VinayM. Vinay
7,22822135
$endgroup$
$begingroup$
Thank you so much!
$endgroup$
– Frederic Chopin
Mar 29 at 3:31
add a comment |
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%2f3165442%2fchain-of-transpositions-raised-to-a-power-and-its-orbits%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Without loss of generality, let us take the left-to-right composition convention (i.e., assume that the permutation is acting from the right).
Then simply observe that the permutation $pi = ((1 2)(2 3) cdots (n-1 n))$ maps each $i$ to $i - 1 mod n$ (so, $1 mapsto n = 0$; $2 mapsto 1$, …, $n mapsto n - 1$).
Thus, $pi^m$ maps each $i$ to $i - m mod n$. Now, let $k$ ($1 le k le n$) be the length of the cycle containing $1$ in the cyclic decomposition of $pi^m$. That is, $k$ is the least positive integer such that
$$1 mapsto (1 - m) mapsto (1 - 2m) mapsto cdots mapsto (1 - (k - 1)m) mapsto (1 - km) = 1.$$
That is, $k$ is the least positive integer such that $km equiv 0 mod n$. Then $k = n$ if and only if $m$ and $n$ are relatively prime. Note that there is exactly one cycle in the decomposition if and only if $k = n$.
answered Mar 28 at 5:46
M. VinayM. Vinay
7,22822135
$endgroup$
$begingroup$
Thank you so much!
$endgroup$
– Frederic Chopin
Mar 29 at 3:31
add a comment |
$begingroup$
Without loss of generality, let us take the left-to-right composition convention (i.e., assume that the permutation is acting from the right).
Then simply observe that the permutation $pi = ((1 2)(2 3) cdots (n-1 n))$ maps each $i$ to $i - 1 mod n$ (so, $1 mapsto n = 0$; $2 mapsto 1$, …, $n mapsto n - 1$).
Thus, $pi^m$ maps each $i$ to $i - m mod n$. Now, let $k$ ($1 le k le n$) be the length of the cycle containing $1$ in the cyclic decomposition of $pi^m$. That is, $k$ is the least positive integer such that
$$1 mapsto (1 - m) mapsto (1 - 2m) mapsto cdots mapsto (1 - (k - 1)m) mapsto (1 - km) = 1.$$
That is, $k$ is the least positive integer such that $km equiv 0 mod n$. Then $k = n$ if and only if $m$ and $n$ are relatively prime. Note that there is exactly one cycle in the decomposition if and only if $k = n$.
answered Mar 28 at 5:46
M. VinayM. Vinay
7,22822135
$endgroup$
$begingroup$
Thank you so much!
$endgroup$
– Frederic Chopin
Mar 29 at 3:31
add a comment |
$begingroup$
Without loss of generality, let us take the left-to-right composition convention (i.e., assume that the permutation is acting from the right).
Then simply observe that the permutation $pi = ((1 2)(2 3) cdots (n-1 n))$ maps each $i$ to $i - 1 mod n$ (so, $1 mapsto n = 0$; $2 mapsto 1$, …, $n mapsto n - 1$).
Thus, $pi^m$ maps each $i$ to $i - m mod n$. Now, let $k$ ($1 le k le n$) be the length of the cycle containing $1$ in the cyclic decomposition of $pi^m$. That is, $k$ is the least positive integer such that
$$1 mapsto (1 - m) mapsto (1 - 2m) mapsto cdots mapsto (1 - (k - 1)m) mapsto (1 - km) = 1.$$
That is, $k$ is the least positive integer such that $km equiv 0 mod n$. Then $k = n$ if and only if $m$ and $n$ are relatively prime. Note that there is exactly one cycle in the decomposition if and only if $k = n$.
answered Mar 28 at 5:46
M. VinayM. Vinay
7,22822135
$endgroup$
Without loss of generality, let us take the left-to-right composition convention (i.e., assume that the permutation is acting from the right).
Then simply observe that the permutation $pi = ((1 2)(2 3) cdots (n-1 n))$ maps each $i$ to $i - 1 mod n$ (so, $1 mapsto n = 0$; $2 mapsto 1$, …, $n mapsto n - 1$).
Thus, $pi^m$ maps each $i$ to $i - m mod n$. Now, let $k$ ($1 le k le n$) be the length of the cycle containing $1$ in the cyclic decomposition of $pi^m$. That is, $k$ is the least positive integer such that
$$1 mapsto (1 - m) mapsto (1 - 2m) mapsto cdots mapsto (1 - (k - 1)m) mapsto (1 - km) = 1.$$
That is, $k$ is the least positive integer such that $km equiv 0 mod n$. Then $k = n$ if and only if $m$ and $n$ are relatively prime. Note that there is exactly one cycle in the decomposition if and only if $k = n$.
answered Mar 28 at 5:46
M. VinayM. Vinay
7,22822135
answered Mar 28 at 5:46
M. VinayM. Vinay
7,22822135
answered Mar 28 at 5:46
M. VinayM. Vinay
7,22822135
answered Mar 28 at 5:46
M. VinayM. Vinay
7,22822135
7,22822135
$begingroup$
Thank you so much!
$endgroup$
– Frederic Chopin
Mar 29 at 3:31
add a comment |
$begingroup$
Thank you so much!
$endgroup$
– Frederic Chopin
Mar 29 at 3:31
$begingroup$
Thank you so much!
$endgroup$
– Frederic Chopin
Mar 29 at 3:31
$begingroup$
Thank you so much!
$endgroup$
– Frederic Chopin
Mar 29 at 3:31
add a comment |
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.
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%2f3165442%2fchain-of-transpositions-raised-to-a-power-and-its-orbits%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
$begingroup$
Do you mean that you want to prove $((1 2)(2 3) cdots (n-1 n))^m$ has exactly one cycle in its cyclic decomposition iff $m$ and $n$ are relatively prime?
$endgroup$
– M. Vinay
Mar 28 at 5:07
$begingroup$
That's right, yes
$endgroup$
– Frederic Chopin
Mar 28 at 5:21