one-line notation for permutations

One-line notation is a system for representing permutations on a collection of symbols by words over the alphabet consisting of those symbols. First we show how the notation works in an example, and then we show that the notation can be made to work for any symmetric group.

First consider the permutation $\pi=(134)(25)$ in the symmetric group $\mathfrak{S}_{5}$ . Here $\pi$ is written in cycle notation, so $\pi(1)=3$ , $\pi(2)=5$ , $\pi(3)=4$ , $\pi(4)=1$ , and $\pi(5)=2$ . We can record this information in the following table:

\begin{array}[]{clllll}i&1&2&3&4&5\\ \pi(i)&3&5&4&1&2\end{array}

Finally, we read off the one-line notation as the second row of the table. Thus we write $\pi=35412$ .

Now we define one-line notation for arbitrary finite symmetric groups. Let $X$ be a set of finite cardinality $n$ and let $\mathfrak{S}_{X}$ be the group of permutations on $X$ . Fix once and for all a total order $<$ on $X$ . Using this order, we may say that

X=\{x_{1}<x_{2}<\dots<x_{n}\}.

For an arbitrary $\pi\in\mathfrak{S}_{X}$ , the one-line notation for $\pi$ is then

\pi=\pi(x_{1})\pi(x_{2})\cdots\pi(x_{n}).

Observe that if $\pi$ and $\sigma$ are distinct permutations in $\mathfrak{S}_{X}$ , then there is some $i$ for which $\pi(x_{i})\neq\sigma(x_{i})$ . Hence the one-line notations for $\pi$ and $\sigma$ will differ in the $i$ th position. This shows that one-line notation is an injective map. Furthermore, we can immediately recover $\pi$ from its one-line notation. If $\pi$ has one-line notation $a_{1}a_{2}\dots a_{n}$ , then we know that $\pi(x_{i})=a_{i}$ for all $i$ . For example, consider the permutation in $\mathfrak{S}_{7}$ written in one-line notation as $\pi=1732654$ . We immediately obtain the following:

\begin{array}[]{clllllll}i&1&2&3&4&5&6&7\\ \pi(i)&1&7&3&2&6&5&4\end{array}

So now we can translate the permutation into cycle notation: $\pi=(1)(274)(56)$ .

If we are willing to allow words of infinite length, we can even extend one-line notation to symmetric groups of arbitrary cardinality. Let $X$ be a set and $\mathfrak{S}_{X}$ its symmetric group. Apply the axiom of choice to select a well-ordering on $X$ . So we may write the elements of $X$ in order as the tuple $(x_{1},x_{2},\dots,x_{\alpha},x_{\alpha+1},\dots)$ . Then for each $\pi\in\mathfrak{S}_{X}$ the one-line notation for $\pi$ is the tuple

(\pi(x_{1}),\pi(x_{2}),\dots,\pi(x_{\alpha}),\pi(x_{\alpha+1}),\dots).

The same analysis as in the finite case shows that a permutation is uniquely recoverable from its representation in one-line notation.

Title	one-line notation for permutations
Canonical name	OnelineNotationForPermutations
Date of creation	2013-03-22 16:24:38
Last modified on	2013-03-22 16:24:38
Owner	mps (409)
Last modified by	mps (409)
Numerical id	4
Author	mps (409)
Entry type	Definition
Classification	msc 05A05
Related topic	Permutation
Related topic	CycleNotation
Defines	one-line notation