Prove that the order of An is (1/2)n!

ArcanaNoir · Oct 30, 2011

1. The problem statement, all variables and given/known data
Prove that the order of An (the subgroup of all even permutation of Sn) is (1/2)n!
And even permutation is one that must be written with an even number of transpositions (2-cycles)

2. Relevant equations

3. The attempt at a solution

I know that being (1/2)n! means half of Sn is even. I think I'm supposed to show why the subgroup must be half. I have in my notes something about a mapping, it was one of those days where I couldn't read my prof's handwriting (same as always) and I wasn't feeling up to asking him what the heck the board said. Something about a mapping Phi, that maps evens into odds.

This is just one in a long line of theorems I'm studying this weekend, and my brain is about fried. Please be clear, and try not to make it too hard.

ArcanaNoir · Oct 30, 2011

This is what wikipedia says, "If n>1, then there are just as many even permutations in Sn as there are odd ones;[3] consequently, An contains n!/2 permutations. [The reason: if σ is even, then (12)σ is odd; if σ is odd, then (12)σ is even; the two maps are inverse to each other.][3]"

But I don't get why this implies that there must be an equal number of even permuations and odd permutations in Sn.

I like Serena · Oct 30, 2011

For each even element there is a unique odd element.
That is, there is a 1-1 relation between the two (a "bijection").
So the number of even elements must be equal to the number of odd elements.

ArcanaNoir · Oct 30, 2011

Why is there a 1-1 relationship between them?

Deveno · Oct 30, 2011

one way to see this is using the "sign" function:

sgn(p) = 1, if p is even
sgn(p) = -1, if p is odd.

this is, in fact a homomorphism from Sn to {-1,1}, which is cyclic of order 2.

even more nicely, this homomorphism is onto, which means that {-1,1} ≅ Sn/ker(sgn).

and, ker(sgn) = {even permutations} = An.

so we know that |Sn/An| = 2.

can you do the rest?

I like Serena · Oct 30, 2011

ArcanaNoir said: ↑

Why is there a 1-1 relationship between them?

Ah, forget 1-1. It's true, but it makes it more complex.

An element is either even or odd.

Take the mapping from the even permutations to odd permutations, given by a → (1 2)a.
Each even element is mapped onto a (different) odd element.
So there are at least as many odd elements as even elements.

Similarly take the mapping from the odd permutations to the even permutations, given by b → (1 2)b.
Each odd element is mapped onto a (different) even element.
So there are at least as many even elements as odd elements.

Therefore there must be the same number of even as odd elements.

ArcanaNoir · Oct 30, 2011

We haven't done homomorphs or isomorphs or any-morphs yet. Also, what does ker mean? kernal? I assume sgn means sign?

ArcanaNoir · Oct 30, 2011

I like Serena said: ↑

Ah, forget 1-1. It's true, but it makes it more complex.

An element is either even or odd.

Take the mapping from the even permutations to odd permutations, given by a → (1 2)a.
Each even element is mapped onto a (different) odd element.
So there are at least as many odd elements as even elements.

Similarly take the mapping from the odd permutations to the even permutations, given by b → (1 2)b.
Each odd element is mapped onto a (different) even element.
So there are at least as many even elements as odd elements.

Therefore there must be the same number of even as odd elements.

why do the elements have to map to each other?

Deveno · Oct 30, 2011

then you'll have to use I like Serena's method.

the "hard part" is showing that p ---> (1 2)p is a bijection between the odd permutations and even permutations.

I like Serena · Oct 30, 2011

ArcanaNoir said: ↑

why do the elements have to map to each other?

(1 2) is an odd permutation.

An even permution is one that can be written as the product of an even number of transpositions.
If we add another transposition (an odd permutation), we get the product of an odd number of transpositions.

Deveno · Oct 30, 2011

suppose q is any even permutation. we want to find some odd permutation p, such that:

(1 2)p = q.

this will show that p ---> (1 2)p is onto, and since Sn is finite, a surjection on a finite set is bijective.

well, if q is even, then (1 2)q is odd (adding another transpositon changes the parity, or sign).

so we can choose as our odd permutation p = (1 2)q:

(1 2)p = (1 2)(1 2)q = q.

ArcanaNoir · Oct 30, 2011

Well, say we were in S4, and we took an arbitrary permutation, say (1 2 3 4), and then it is written as (3 2)(4 3)(1 4), so it's odd (is that right, i thought even length mean it was even?) so we know (1 2) is in S4, because it's in all Sn greater than or equal to two, so we know (1 2 3 4)*(1 2) is in S4, and we know this new permutation will have opposite parity from (1 2 3 4) because if (1 2) is in (1 2 3 4) then we take away one if it's not, we add one. and so suppose (assuming I'm right about (1 2 3 4) being odd) there are k odd permutations in S4, how do I know there will be at least k even permutations (how do I know each mapping will map to a different even permutation)?

I like Serena · Oct 30, 2011

ArcanaNoir said: ↑

Well, say we were in S4, and we took an arbitrary permutation, say (1 2 3 4), and then it is written as (3 2)(4 3)(1 4), so it's odd (is that right, i thought even length mean it was even?)

You have it right. Even length means odd permution.
Think of (1 2) which has an even length, but is only 1 transposition (odd!).

ArcanaNoir said: ↑

so we know (1 2) is in S4, because it's in all Sn greater than or equal to two, so we know (1 2 3 4)*(1 2) is in S4, and we know this new permutation will have opposite parity from (1 2 3 4) because if (1 2) is in (1 2 3 4) then we take away one if it's not, we add one.

Perhaps I should remark that the number of transpositions is not fixed.
An odd permutation can be written as any odd number of permutations (with a certain minimum).
For instance (1 2)=(1 2)(1 2)(1 2).

ArcanaNoir said: ↑

and so suppose (assuming I'm right about (1 2 3 4) being odd) there are k odd permutations in S4, how do I know there will be at least k even permutations (how do I know each mapping will map to a different even permutation)?

Very sharp!

Suppose a and b are different odd permutations that map to the same even permutation.
So (1 2)a = (1 2)b.
Then (1 2)(1 2)a = (1 2)(1 2)b, that is, a=b, which is a contradiction.
So each odd permutation maps onto a different even permutation.

ArcanaNoir · Oct 30, 2011

ah, left cancellation law. Okay, this helped. Thanks ILS. How come you know all this stuff anyway? You know a great level of detail of wide-ranging math subjects. How come you don't forget stuff? Shouldn't you only have a narrow band of this level of knowledge, maintained by everyday use ?

I like Serena · Oct 30, 2011

Thanks!

Actually, I'm a software engineer who doesn't do math or physics (that's why I'm so active on PF! ).

But in my spare time I'm a private tutor.
Currently I have a student who is already a math teacher, but who needs to learn algebra to upgrade her level.
I also have a number of psychology students who have difficulty learning statistics.

ArcanaNoir · Oct 30, 2011

So it's a fascinating coincidence? Well, I think you're a great tutor. :) You going to help me with diffyQ next semester?

I like Serena · Oct 30, 2011

ArcanaNoir said: ↑

So it's a fascinating coincidence? Well, I think you're a great tutor. :) You going to help me with diffyQ next semester?

Not really a coincidence.
I also do mechanics, electronics, linear algebra, differential equations, etcetera.
I'm currently (re)practicing/learning thermodynamics on PF.
And every now and then I try my hand at chemistry, but I'm a bit scared someone (Borek?) will find out I'm not so good at it.

I saw you were helping people on PF as well!

I'll look forward to seeing you with diffyQ.