Alternative proof about the order of the alternating group?

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$?

-
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
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
You may want to check out a proof that I published in the American Mathematical Monthly,1963,page 995.It dealt with the invariance of parity of a permutation written as a product of transpositions,and was one of the first to avoid the polynomial proof which was probably around from the days of Cauchy.--Ed Gray – Edwin Gray Apr 13 '15 at 14:47

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$.

-
Nice application of the property of bijection on finite set! – Jack Jun 20 '11 at 17:47

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.

-

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.$$

-

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.

-
The supplied proofs are perfectly valid since the thing they assume is true. – Tobias Kildetoft Jun 29 '13 at 6:25