Abstract Nonsense

Crushing one theorem at a time

Permutations (Pt. I)


Point of post: This will be the first of a few posts that are an expansion upon the topic of permutations discussed in Halmos sections 26, 27, and 28. I expand not because it’s a necessity for the material he covers, but because I think it’s a fruitful topic to explore considering it’s vast use througout many fields of mathematics.

Motivation

No doubt any reader familiar with even the most basic group theory is aware of the power of permutations, in their own right, but alas this being a post about linear algebra I’ll try to keep the group theoretic rhetoric to a minimum. Anyways, why would anyone doing linear algebra care about permutations? Well, let’s recall some basics from undergraduate linear algebra, namely the determinant function. If one recalls the determinant function is some mystic tool which gives qualitative measure to the invertability of a matrix

M_n=\begin{bmatrix} a_{1,1} & \cdots & a_{1,n}\\ \vdots & \ddots & \vdots\\ a_{n,1} & \cdots & a_{n,n}\end{bmatrix}

namely, M is invertible if and only if \det M\ne 0.  But, how exactly did we define \det M? Well, for two-by-two matrices it was simple

\det M_2=a_{1,1}a_{2,2}-a_{1,2}a_{2,1}

If you have really good memory you might even remember off the top of your head \det M_3 (I sure can’t, I have to do the juxtaposition of a copy of the matrix trick). They then told you that the general form of the determinant was the ugly beast of the formua

\displaystyle \det M_n=\sum_{\pi\in S_n}\text{sgn}(\pi)\prod_{j=1}^{n}a_{j,\pi(j)}

and so we see the first (of trust me many) appearances of the concept of permutation and its ilk. But, that’s matrix theory you say! Why should a tangentially related concept motivate us to study this topic? Well, two reasons. Firstly, even though the determinant is classically matrix theory as we will see in subsequent chapters the determinant will play a vital role in determining the invertibility of a linear transformation, something which hits us very, very close to home. But, more immediately the determinant interests as as it is a an archetypal example of something we shall soon study. In particular if thought of as a function of the columns it is really a function

\det:\mathbb{C}^n\to\mathbb{C}

which is linear in each variable. In other words it’s the n-fold analogue of a bilinear form, it’s a k-linear form. Moreover, it has the property that if \bold{z}_1,\cdots,\bold{z}_n\in\mathbb{C}^n that

\det(\bold{z}_1,\cdots,\bold{z}_n)=\text{sgn}(\pi)\det(\bold{z}_{\pi(1)},\cdots,\bold{z}_{\pi(n)})

which is  an example of something called a skew-symmetric form. Both of these are integral parts of the subject, to be introduced, called multilinear algebra. So, with that said let’s embark on our study of the permutations, their group, and their parity.

Definition

Let \Omega be a set. Then, we define

S_{\Omega}=\left\{\sigma:\Omega\to\Omega\mid \sigma\text{ is a bijection}\right\}

which is called the permutation group on \Omega.

Theorem: S_{\Omega} forms a group under function composition.

Proof: Clearly \circ:S_{\Omega}\times S_{\Omega}\to S_{\Omega} since the composition of bijections is a bijection, and it’s also clear that \circ being normal function composition is associative. Thus, it suffices to check that there exist some element e of S_{\Omega} such that e\circ \sigma=\sigma\circ e=\sigma for all \sigma\in S_{\Omega} and that for every \sigma\in S_{\Omega} there exists some \tau\in S_{\Omega} such that \sigma\tau=\tau\sigma=e. Well, clearly e=\text{id}_{\Omega} satisfies the first property. For the second we merely notice that every bijection \sigma admits a set-theoretic inverse \sigma^{-1} such that \sigma\circ \sigma^{-1}=\sigma^{-1}\circ\sigma=\text{id}_{\Omega}. It follows that S_{\Omega} is a group under function composition. \blacksquare

If \left|\Omega\right|=n then S_{\Omega} is denoted S_n and called the symmetric group on n letters.

The next obvious questions is what is the order of S_n (i.e. what’s the cardinality)? To do this we create a recurrence relation to relate the cardinality of S_{n+1} with that of S_n.

Theorem: \left|S_n\right|=n!

Proof: Let a_n=|S_n|. Consider a_{n+1}, then a_{n+1} is the number of bijective mappings f:[n+1]\to[n+1]. Consider then that every such bijective map f is determined by f_{[n]}:[n]\to[n+1]. Thus, a_{n+1} is equal to the number of injections f:[n]\to[n+1]. But, consider fixing \{m_1,\cdots,m_n\}\subseteq[n+1] and considering the number of injections f:[n]\to\{m_1,\cdots,m_n\}. Then, by previous discussion we know that the number of such injections is the same as the number of such bijections. Thus, the number of injections f:[n]\to\{m_1,\cdots,m_n\} is a_n. Clearly then the total number of injections f:[n]\to[n+1] and thus a_{n+1} is

\displaystyle a_{n+1}={{n+1}\choose n}a_n=(n+1)a_n

and since a_1=1 it follows that a_n=n!. \blacksquare

References:

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

2.  Fraleigh, John B., and Victor J. Katz. A First Course in Abstract Algebra. Boston: Addison-Wesley, 2003. Print.

Advertisements

November 6, 2010 - Posted by | Algebra, Halmos, Linear Algebra | , , ,

4 Comments »

  1. […] of post: This post is a continuation of this post in a continuing effort to define permutations fully and clearly, something someone reading […]

    Pingback by Permutations (Pt. II Permutation Matrices) « Abstract Nonsense | November 6, 2010 | Reply

  2. […] of post: In this post we continue the discussion of permutations discussed here and here in our journey to understand permutations rigorously, clearly, and fully so that we may […]

    Pingback by Permutations (Pt. III Orbits and Cycles) « Abstract Nonsense | November 6, 2010 | Reply

  3. […] This was covered in this post. Less rigorously, let . Then, there are precisely choices for , and thus after that has been […]

    Pingback by Halmos Section 26 and 27: Permutations and Cycles « Abstract Nonsense | November 8, 2010 | Reply

  4. […] classes, and even explicitly computable sized classes–I am of course talking about the symmetric group. So, in this post we shall classify the conjugacy classes of and find their […]

    Pingback by Conjugacy Classes on the Symmetric Group « Abstract Nonsense | May 10, 2011 | Reply


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: