Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It is known that the order of the alternating group $A_n$ of order $n$ is $\frac{n!}{2}$. In Herstein's Abstract Algebra, it is proved by the First Homomorphism Theorem. I tried to find an alternative proof which needs not using the group homomorphism. I think the following rules may be helpful:

  1. The product of two even permutations is even.
  2. The product of two odd permutations is even.
  3. The product of an even permutation by an odd one (or of an odd one by an even one) is odd.

Intuitively, since the product of an odd(resp. even) permutation and a 1-cycle is even(resp. odd), a half of all the permutations should be even. Then we get $\frac{n!}{2}$.

What's more, the theorem mentioned in this question may be related. I don't know if one can turn the argument above into a proof. So here is my question:

Does anybody know other proofs about the order of $A_n$?

share|improve this question
2  
Your three rules are exactly the statement that sign is a homomorphism from $S_n$ to the two-element group. So any proof based on them would still be using this homomorphism. –  Chris Eagle Jun 20 '11 at 17:08
1  
The two answers below are very good. They are both specific instances of Lagrange's theorem. f(An) is called a coset of An in Sn. –  Jack Schmidt Jun 20 '11 at 17:32
add comment

4 Answers 4

up vote 13 down vote accepted

Let $\text{Odd}_n$ denote the set of odd permutations in $S_n$. Fix an element $\alpha \in \text{Odd}_n$, and define a function $f\colon A_n \to \text{Odd}_n$ by $$ f(\sigma) \;=\; \alpha\sigma. $$ I claim that $f$ is a bijection.

To prove that $f$ is one-to-one, suppose that $f(\sigma) = f(\sigma')$ for some $\sigma,\sigma' \in A_n$. Then $\alpha\sigma = \alpha\sigma'$, and therefore $\sigma=\sigma'$.

To prove that $f$ is onto, let $\beta \in \text{Odd}_n$. Then $\alpha^{-1}\beta$ is an even permutation and $f(\alpha^{-1}\beta) = \beta$, which proves that $f$ is onto.

We conclude that $|A_n| = |\text{Odd}_n|$, and therefore $|A_n| = |S_n|/2$.

share|improve this answer
    
Nice application of the property of bijection on finite set! –  Jack Jun 20 '11 at 17:47
add comment

Clearly, we need to assume $n\geq 2$. The permutation $(12)$ is odd. The mapping $f:S_n\rightarrow S_n$, $f(\sigma)=(12)\circ\sigma$ is inverse to itself, hence bijective. If $\sigma$ is even, then $(12)\circ\sigma$ is odd. If $\tau$ is odd, then $(12)\circ \tau$ is even, and $\tau=(12)\circ(12)\circ\tau$. Hence $f(A_n)$ is the set of odd permutations. Since $f$ is bijective, there are as many even permuations as there are odd ones, i.e. there are $\frac{n!}{2}$ even and $\frac{n!}{2}$ odd permutations.

share|improve this answer
add comment

The following is, in my opinion, a nice exercise for students - you might ask them to use what they know about determinant to show that the number of odd permutations is the same as the number of even permutations. (But it seems to be more complicated than the proofs provided in other answers to this question.)

Let us consider the following determinant of the $n\times n$ matrix where each entry is $1$ $$E=\begin{vmatrix} 1 & 1 & \ldots & 1 \\ 1 & 1 & \ldots & 1 \\ 1 & 1 & \ldots & 1 \\ 1 & 1 & \ldots & 1 \end{vmatrix} $$ where $n\ge 2$.

Recall that determinant of a matrix $A$ is $$\operatorname{det}A=\sum_{\varphi\in S_n} (-1)^{i(\varphi)} a_{1\varphi(1)}a_{2\varphi(2)}\ldots a_{n\varphi(n)},$$ where $i(\varphi)$ denotes the number of inversions of $\varphi$.

We know that $(-1)^{i(\varphi)}$ is $+1$ for even permutation and $-1$ for odd permutation.

For the matrix $E$ we get $$\operatorname{det}E=\sum_{\varphi\in S_n} (-1)^{i(\varphi)} = \sum_{\varphi\in A_n} 1 + \sum_{\varphi\in S_n\setminus A_n} (-1) = |A_n|-(|S_n|-|A_n|)=2|A_n|-|S_n|.$$ But we know that $\operatorname{det} E=0$, since the rows are linearly dependent. So we get $2|A_n|-|S_n|=0$ and $$|A_n|=\frac{|S_n|}2.$$

share|improve this answer
add comment

The supplied proofs don't seem to be valid. They seem to assume that a permutation cannot be both odd and even at the same time.

It is sufficient to show that if the identity permutation is the product of a number of transpositions then that number must be even. This is clearly true for the symmetric group on n = 2 elements. I will use induction on n.

Consider the symmetric group on n elements, n > 2. Let the identity permutation be written as a product of m transposition. Consider the transpositions of the form (1x). Define the weight of that product transposition to be the binary equivalent of where such transpositions (1x) occur. For example, the transposition product (12)(13)(23) has weight 6 since (12) occurs in the 3rd position to give 4 and (13) occurs in the second position to give 2 (and 6 = 4+2). The product transposition (23)(23)(12) has weight 1.

I will induct on the weight. I need the following:

  a) (1x)(yz) = (yz)(1x)
  b) (1x)(1z) = (xz)(1x)
  c) (1x)(xy) = (xy)(1y)
  d) (1x)(1x) = identity

If the weight is 0, then 1 doesn't appear and induction on n yields the result.

If the weight is 1, then this cannot happen since 1 would not be mapped to itself.

If the weight is greater than 1, then there is a transposition to the right of the first occurring (1x). One of the four cases a) through b) can be applied to reduce the weight. By induction on the weight, the result follows.

share|improve this answer
2  
The supplied proofs are perfectly valid since the thing they assume is true. –  Tobias Kildetoft Jun 29 '13 at 6:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.