How to prove that an even permutation of $A_n$ is a square of another permutation from $S_n$?
up vote
4
down vote
favorite
I am trying to go through a proof which contains a statement that an even permutation from $A_n$ is a square of another permutation from $S_n$. My basic ideas are like this:
Suppose an even permutation is $y$. As the signature of an even permutation is $+1$, we are able to write it as a product of $t_{1}t_{2}t_{3}t_{4}...t_{2r-1}t_{2r}$ with each $t$ standing for a two cycle. Then, consider $t_{1}t_{2}$, it can be written as $(ij)(kl)$ if $t_{1}$ and $t_{2}$ are distinct, or as $(ij)(jk)$ if they are not distinct. However, $(ij)(kl) = (ikjl)^2$ and $(ij)(jk) = (ikj)^2$, which means each of the $t_1t_2$, $t_3t_4$,...,$t_{2r-1}t_{2r}$ is a square of another permutation of $S_n$, say $x_i$.
However, how does it imply that $y$ is a square of another permutation? If $y = x_1^2...x_r^2$, does it necessarily mean that $y$ is a square of something? Is $x_i$ commutative in this case? I need some hints, thanks.
abstract-algebra combinatorics group-theory permutations permutation-cycles
add a comment |
up vote
4
down vote
favorite
I am trying to go through a proof which contains a statement that an even permutation from $A_n$ is a square of another permutation from $S_n$. My basic ideas are like this:
Suppose an even permutation is $y$. As the signature of an even permutation is $+1$, we are able to write it as a product of $t_{1}t_{2}t_{3}t_{4}...t_{2r-1}t_{2r}$ with each $t$ standing for a two cycle. Then, consider $t_{1}t_{2}$, it can be written as $(ij)(kl)$ if $t_{1}$ and $t_{2}$ are distinct, or as $(ij)(jk)$ if they are not distinct. However, $(ij)(kl) = (ikjl)^2$ and $(ij)(jk) = (ikj)^2$, which means each of the $t_1t_2$, $t_3t_4$,...,$t_{2r-1}t_{2r}$ is a square of another permutation of $S_n$, say $x_i$.
However, how does it imply that $y$ is a square of another permutation? If $y = x_1^2...x_r^2$, does it necessarily mean that $y$ is a square of something? Is $x_i$ commutative in this case? I need some hints, thanks.
abstract-algebra combinatorics group-theory permutations permutation-cycles
Aren't all elements $A_n$ even permutations?
– lhf
Nov 15 at 15:52
See math.stackexchange.com/a/538179/589
– lhf
Nov 15 at 15:52
The result claimed is in general not true. But it is true for n=5
– C Monsour
Nov 16 at 5:42
add a comment |
up vote
4
down vote
favorite
up vote
4
down vote
favorite
I am trying to go through a proof which contains a statement that an even permutation from $A_n$ is a square of another permutation from $S_n$. My basic ideas are like this:
Suppose an even permutation is $y$. As the signature of an even permutation is $+1$, we are able to write it as a product of $t_{1}t_{2}t_{3}t_{4}...t_{2r-1}t_{2r}$ with each $t$ standing for a two cycle. Then, consider $t_{1}t_{2}$, it can be written as $(ij)(kl)$ if $t_{1}$ and $t_{2}$ are distinct, or as $(ij)(jk)$ if they are not distinct. However, $(ij)(kl) = (ikjl)^2$ and $(ij)(jk) = (ikj)^2$, which means each of the $t_1t_2$, $t_3t_4$,...,$t_{2r-1}t_{2r}$ is a square of another permutation of $S_n$, say $x_i$.
However, how does it imply that $y$ is a square of another permutation? If $y = x_1^2...x_r^2$, does it necessarily mean that $y$ is a square of something? Is $x_i$ commutative in this case? I need some hints, thanks.
abstract-algebra combinatorics group-theory permutations permutation-cycles
I am trying to go through a proof which contains a statement that an even permutation from $A_n$ is a square of another permutation from $S_n$. My basic ideas are like this:
Suppose an even permutation is $y$. As the signature of an even permutation is $+1$, we are able to write it as a product of $t_{1}t_{2}t_{3}t_{4}...t_{2r-1}t_{2r}$ with each $t$ standing for a two cycle. Then, consider $t_{1}t_{2}$, it can be written as $(ij)(kl)$ if $t_{1}$ and $t_{2}$ are distinct, or as $(ij)(jk)$ if they are not distinct. However, $(ij)(kl) = (ikjl)^2$ and $(ij)(jk) = (ikj)^2$, which means each of the $t_1t_2$, $t_3t_4$,...,$t_{2r-1}t_{2r}$ is a square of another permutation of $S_n$, say $x_i$.
However, how does it imply that $y$ is a square of another permutation? If $y = x_1^2...x_r^2$, does it necessarily mean that $y$ is a square of something? Is $x_i$ commutative in this case? I need some hints, thanks.
abstract-algebra combinatorics group-theory permutations permutation-cycles
abstract-algebra combinatorics group-theory permutations permutation-cycles
edited Nov 15 at 13:37
amWhy
191k27223437
191k27223437
asked Nov 15 at 13:09
Jamie Carr
444
444
Aren't all elements $A_n$ even permutations?
– lhf
Nov 15 at 15:52
See math.stackexchange.com/a/538179/589
– lhf
Nov 15 at 15:52
The result claimed is in general not true. But it is true for n=5
– C Monsour
Nov 16 at 5:42
add a comment |
Aren't all elements $A_n$ even permutations?
– lhf
Nov 15 at 15:52
See math.stackexchange.com/a/538179/589
– lhf
Nov 15 at 15:52
The result claimed is in general not true. But it is true for n=5
– C Monsour
Nov 16 at 5:42
Aren't all elements $A_n$ even permutations?
– lhf
Nov 15 at 15:52
Aren't all elements $A_n$ even permutations?
– lhf
Nov 15 at 15:52
See math.stackexchange.com/a/538179/589
– lhf
Nov 15 at 15:52
See math.stackexchange.com/a/538179/589
– lhf
Nov 15 at 15:52
The result claimed is in general not true. But it is true for n=5
– C Monsour
Nov 16 at 5:42
The result claimed is in general not true. But it is true for n=5
– C Monsour
Nov 16 at 5:42
add a comment |
3 Answers
3
active
oldest
votes
up vote
3
down vote
Hint. A permutation is the square of another permutation if and only if, its cycle decomposition has an even number of cycles of length $m$ for every even number $m$.
1
Thanks for your answer but I wonder is there a strict proof of that? I am not so sured that these cycles are distinct so that I can change the order of them to make a perfect square...For example, if p = x^2y^2 does it mean that p is a square of another permutation?
– Jamie Carr
Nov 15 at 13:19
See for example math.stackexchange.com/questions/266569/…
– Robert Z
Nov 15 at 17:10
add a comment |
up vote
1
down vote
Some more hints:
Begin by studying the cycle structures of squares $sigma:=picircpi$ of arbitrary permutations. For this it is sufficient to find out what happens to a cycle of odd length under squaring, and what happens to a cycle of even length under squaring.
add a comment |
up vote
1
down vote
That's not remotely true: the density of squares in $S_n$ goes to zero as $nto +infty$ (like $frac{C}{sqrt{n}}$, actually), while your claim would imply that the $liminf$ of such density is at least $frac{1}{2}$. Indeed, if we consider
$$sigma = (1,2)(3,4,5,6) in A_6 $$
this is not the square of anything in $S_6$. A square in $S_6$ has the property that the cycles with a fixed even length appear with an even multiplicity.
Your last sentence is completely false. For example the set of squares in any dihedral group form a subgroup, and the set of squares in $S_5$ are in fact $A_5$.
– C Monsour
Nov 16 at 5:36
Not to mention that the squares form a subgroup of any group of odd order.
– C Monsour
Nov 16 at 5:46
1
I deleted the erroneous sentence.
– C Monsour
Nov 16 at 5:47
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Hint. A permutation is the square of another permutation if and only if, its cycle decomposition has an even number of cycles of length $m$ for every even number $m$.
1
Thanks for your answer but I wonder is there a strict proof of that? I am not so sured that these cycles are distinct so that I can change the order of them to make a perfect square...For example, if p = x^2y^2 does it mean that p is a square of another permutation?
– Jamie Carr
Nov 15 at 13:19
See for example math.stackexchange.com/questions/266569/…
– Robert Z
Nov 15 at 17:10
add a comment |
up vote
3
down vote
Hint. A permutation is the square of another permutation if and only if, its cycle decomposition has an even number of cycles of length $m$ for every even number $m$.
1
Thanks for your answer but I wonder is there a strict proof of that? I am not so sured that these cycles are distinct so that I can change the order of them to make a perfect square...For example, if p = x^2y^2 does it mean that p is a square of another permutation?
– Jamie Carr
Nov 15 at 13:19
See for example math.stackexchange.com/questions/266569/…
– Robert Z
Nov 15 at 17:10
add a comment |
up vote
3
down vote
up vote
3
down vote
Hint. A permutation is the square of another permutation if and only if, its cycle decomposition has an even number of cycles of length $m$ for every even number $m$.
Hint. A permutation is the square of another permutation if and only if, its cycle decomposition has an even number of cycles of length $m$ for every even number $m$.
answered Nov 15 at 13:13
Robert Z
89.8k1056128
89.8k1056128
1
Thanks for your answer but I wonder is there a strict proof of that? I am not so sured that these cycles are distinct so that I can change the order of them to make a perfect square...For example, if p = x^2y^2 does it mean that p is a square of another permutation?
– Jamie Carr
Nov 15 at 13:19
See for example math.stackexchange.com/questions/266569/…
– Robert Z
Nov 15 at 17:10
add a comment |
1
Thanks for your answer but I wonder is there a strict proof of that? I am not so sured that these cycles are distinct so that I can change the order of them to make a perfect square...For example, if p = x^2y^2 does it mean that p is a square of another permutation?
– Jamie Carr
Nov 15 at 13:19
See for example math.stackexchange.com/questions/266569/…
– Robert Z
Nov 15 at 17:10
1
1
Thanks for your answer but I wonder is there a strict proof of that? I am not so sured that these cycles are distinct so that I can change the order of them to make a perfect square...For example, if p = x^2y^2 does it mean that p is a square of another permutation?
– Jamie Carr
Nov 15 at 13:19
Thanks for your answer but I wonder is there a strict proof of that? I am not so sured that these cycles are distinct so that I can change the order of them to make a perfect square...For example, if p = x^2y^2 does it mean that p is a square of another permutation?
– Jamie Carr
Nov 15 at 13:19
See for example math.stackexchange.com/questions/266569/…
– Robert Z
Nov 15 at 17:10
See for example math.stackexchange.com/questions/266569/…
– Robert Z
Nov 15 at 17:10
add a comment |
up vote
1
down vote
Some more hints:
Begin by studying the cycle structures of squares $sigma:=picircpi$ of arbitrary permutations. For this it is sufficient to find out what happens to a cycle of odd length under squaring, and what happens to a cycle of even length under squaring.
add a comment |
up vote
1
down vote
Some more hints:
Begin by studying the cycle structures of squares $sigma:=picircpi$ of arbitrary permutations. For this it is sufficient to find out what happens to a cycle of odd length under squaring, and what happens to a cycle of even length under squaring.
add a comment |
up vote
1
down vote
up vote
1
down vote
Some more hints:
Begin by studying the cycle structures of squares $sigma:=picircpi$ of arbitrary permutations. For this it is sufficient to find out what happens to a cycle of odd length under squaring, and what happens to a cycle of even length under squaring.
Some more hints:
Begin by studying the cycle structures of squares $sigma:=picircpi$ of arbitrary permutations. For this it is sufficient to find out what happens to a cycle of odd length under squaring, and what happens to a cycle of even length under squaring.
edited Nov 15 at 15:37
answered Nov 15 at 13:34
Christian Blatter
170k7111324
170k7111324
add a comment |
add a comment |
up vote
1
down vote
That's not remotely true: the density of squares in $S_n$ goes to zero as $nto +infty$ (like $frac{C}{sqrt{n}}$, actually), while your claim would imply that the $liminf$ of such density is at least $frac{1}{2}$. Indeed, if we consider
$$sigma = (1,2)(3,4,5,6) in A_6 $$
this is not the square of anything in $S_6$. A square in $S_6$ has the property that the cycles with a fixed even length appear with an even multiplicity.
Your last sentence is completely false. For example the set of squares in any dihedral group form a subgroup, and the set of squares in $S_5$ are in fact $A_5$.
– C Monsour
Nov 16 at 5:36
Not to mention that the squares form a subgroup of any group of odd order.
– C Monsour
Nov 16 at 5:46
1
I deleted the erroneous sentence.
– C Monsour
Nov 16 at 5:47
add a comment |
up vote
1
down vote
That's not remotely true: the density of squares in $S_n$ goes to zero as $nto +infty$ (like $frac{C}{sqrt{n}}$, actually), while your claim would imply that the $liminf$ of such density is at least $frac{1}{2}$. Indeed, if we consider
$$sigma = (1,2)(3,4,5,6) in A_6 $$
this is not the square of anything in $S_6$. A square in $S_6$ has the property that the cycles with a fixed even length appear with an even multiplicity.
Your last sentence is completely false. For example the set of squares in any dihedral group form a subgroup, and the set of squares in $S_5$ are in fact $A_5$.
– C Monsour
Nov 16 at 5:36
Not to mention that the squares form a subgroup of any group of odd order.
– C Monsour
Nov 16 at 5:46
1
I deleted the erroneous sentence.
– C Monsour
Nov 16 at 5:47
add a comment |
up vote
1
down vote
up vote
1
down vote
That's not remotely true: the density of squares in $S_n$ goes to zero as $nto +infty$ (like $frac{C}{sqrt{n}}$, actually), while your claim would imply that the $liminf$ of such density is at least $frac{1}{2}$. Indeed, if we consider
$$sigma = (1,2)(3,4,5,6) in A_6 $$
this is not the square of anything in $S_6$. A square in $S_6$ has the property that the cycles with a fixed even length appear with an even multiplicity.
That's not remotely true: the density of squares in $S_n$ goes to zero as $nto +infty$ (like $frac{C}{sqrt{n}}$, actually), while your claim would imply that the $liminf$ of such density is at least $frac{1}{2}$. Indeed, if we consider
$$sigma = (1,2)(3,4,5,6) in A_6 $$
this is not the square of anything in $S_6$. A square in $S_6$ has the property that the cycles with a fixed even length appear with an even multiplicity.
edited Nov 16 at 5:47
C Monsour
5,552224
5,552224
answered Nov 15 at 18:32
Jack D'Aurizio
282k33274653
282k33274653
Your last sentence is completely false. For example the set of squares in any dihedral group form a subgroup, and the set of squares in $S_5$ are in fact $A_5$.
– C Monsour
Nov 16 at 5:36
Not to mention that the squares form a subgroup of any group of odd order.
– C Monsour
Nov 16 at 5:46
1
I deleted the erroneous sentence.
– C Monsour
Nov 16 at 5:47
add a comment |
Your last sentence is completely false. For example the set of squares in any dihedral group form a subgroup, and the set of squares in $S_5$ are in fact $A_5$.
– C Monsour
Nov 16 at 5:36
Not to mention that the squares form a subgroup of any group of odd order.
– C Monsour
Nov 16 at 5:46
1
I deleted the erroneous sentence.
– C Monsour
Nov 16 at 5:47
Your last sentence is completely false. For example the set of squares in any dihedral group form a subgroup, and the set of squares in $S_5$ are in fact $A_5$.
– C Monsour
Nov 16 at 5:36
Your last sentence is completely false. For example the set of squares in any dihedral group form a subgroup, and the set of squares in $S_5$ are in fact $A_5$.
– C Monsour
Nov 16 at 5:36
Not to mention that the squares form a subgroup of any group of odd order.
– C Monsour
Nov 16 at 5:46
Not to mention that the squares form a subgroup of any group of odd order.
– C Monsour
Nov 16 at 5:46
1
1
I deleted the erroneous sentence.
– C Monsour
Nov 16 at 5:47
I deleted the erroneous sentence.
– C Monsour
Nov 16 at 5:47
add a comment |
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%2f2999689%2fhow-to-prove-that-an-even-permutation-of-a-n-is-a-square-of-another-permutatio%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
Aren't all elements $A_n$ even permutations?
– lhf
Nov 15 at 15:52
See math.stackexchange.com/a/538179/589
– lhf
Nov 15 at 15:52
The result claimed is in general not true. But it is true for n=5
– C Monsour
Nov 16 at 5:42