# Abstract Nonsense

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

November 6, 2010 -

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