Abstract Nonsense

Crushing one theorem at a time

Halmos Section 28: Parity


Point of post: In this post I will solve the, very few, problems in the twenty-eighth section of Halmos. This section is on the parity (sign) of a permutation.

1.

Problem: How many elements of A_n are there? (here A_n denotes the Alternating Group)

Proof: Let O_n be the set of all odd permutations in S_n and define

f:O_n\to A_n:\pi\mapsto (1,n)\pi

We claim that this mapping is bijective. It’s clearly injective since f(\pi)=f(\pi')\implies (1,n)\pi=(1,n)\pi'\implies \pi=\pi'. To see it’s surjective we note that if \sigma\in A_n then \text{sgn}(\sigma)=1 and thus

\text{sgn}\left((1,n)\sigma)\right)=\text{sgn}\left((1,n)\right)\text{sgn}\left((1,n)\right)=-1\cdot 1=-1

so that (1,n)\sigma\in O_n. But, then f\left((1,n)\sigma\right)=(1,n)^2\sigma=\sigma. It follows that f is bijective. Note though that since S_n=O_n\sqcup A_n (\{A_n,O_n\} partition S_n) we may conclude that

n!=\left|S_n\right|=\left|O_n\cup A_n\right|=\left|O_n\right|+\left|A_n\right|=2\left|O_n\right|=2\left|A_n\right|

and thus \displaystyle \left|A_n\right|=\left|O_n\right|=\frac{n!}{2}.

2.

Problem: Give examples of even permutations with even order and even permutations with odd order; do the same for odd permutations.

Proof: First note that (1,2,3)\in S_3 is an even permutation (as can be checked, I did it by computing P_{(1,2,3)} and finding that its determinant is 1) yet \text{ord}\left((1,2,3)\right)=3 (or, now that I think about it, the identity map \text{id}_{[n]} is even since \text{id}_{[n]}=(1,2)(1,2) but its order is 1). Take (1,2)(3,4)\in S_4, this is even and has even order.

Note that (1,2)\in S_3 is odd but has even order.  Take, (1,2,3)(4,5,6)(7,8,9)\in S_9. This is odd and has odd order.

3.

Problem: Prove that (1,2,3),\cdots,(1,2,n) generates A_n,\text{ }n\geqslant 3.

Proof: We proceed by induction. Clearly this i true for n=3. Now, suppose then that it’s true for n=m. Then, note that if \pi\in A_{m+1} with \pi(m+1)=k,  then \pi(1,2,k)(1,2,m+1)^{-1} is even and leaves m+1 fixed and thus by our induction hypothesis may be written as the product of 3-cycles, and thus \pi may be written as the product of three cycles. The conclusion follows.

Remark: Note that in general that if (1,\cdots,n)\in S_n that \text{sgn}\left((1,\cdots,n)\right)=(-1)^{n-1}. To see this note that a quick computations shows that

from where it follows that P_{(1,\cdots,n)} can be written as as the product of n-1 row-changing matrices and thus \det P_{(1,\cdots,n)}=\text{sgn}\left((1,\cdots,n)\right)=(-1)^{n-1}

References:

1. Halmos, Paul R.  Finite-dimensional Vector Spaces,. New York: Springer-Verlag, 1974. Print

Advertisements

November 10, 2010 - Posted by | Fun Problems, Halmos, Linear Algebra | , , , , , , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: