Friday, March 22, 2013

Permutations

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com. 

Permutation of n objects is just a bijection on the set of these n objects?
Right.  If we don't specify the set, we means a permutation on the set {1,2,3,...,n}.

How to present a permutation?
Of course, we can present it as a bijection, e.g.
$$f(x)=\begin{cases}1 & x=1\\3 & x=2\\2 & x=3\end{cases}$$ However, traditionally we have a simpler presentation
$$\left(\begin{matrix}1&2&3\\1&3&2\end{matrix}\right)$$ which is, I believe, self-explanatory. The lower part is the new arrangement.

Why not just write (1 3 2)?
It is because we already use this symbol for a special type of permutations-the cycles. For instance (1 3 2) refers to the permutation f(1)=3, f(3)=2 and f(2)=1, i.e. $$\left(\begin{matrix}1&2&3\\3&1&2\end{matrix}\right).$$
It is easy to see cycles are interesting, mathematically?
First, we have to understand the multiplication of two permutations. If we consider two permutations $f$ and $g$ as two bijections on {1,2,3,...,n}, then their product is just the permutation $(fg)(x)=f\circ g(x)=f(g(x))$, that means if $g(r)=s$ and $f(s)=t$ then $(fg)(r)=s$. For instance, $$\left(\begin{matrix}1&2&3\\1&3&2\end{matrix}\right)\left(\begin{matrix}1&2&3\\3&1&2\end{matrix}\right)=\left(\begin{matrix}1&2&3\\2&1&3\end{matrix}\right).$$ It is known that every permutation is a product of cycles.

So cycles are the primes for permutations?
Not quite. The transpositions (i,j), i.e. the cycles of two elements, are the primes. Every permutation can be written as a product of transpositions. e.g. $$\left(\begin{matrix}1&2&3&4&5\\3&5&4&1&2\end{matrix}\right)=(1\, 3\, 4)(2\, 5)=(1\, 4)(1\, 3)(2\, 5).$$