# Convention on Cauchy's two line notation for permutations

Let $n\in\mathbb{N}$. A permutation $\sigma\in S_n$ is denoted in Cauchy's two line notation as follow: \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix} My question is how do we normally interpret $\sigma(i)$, for all $1\leq i\leq n$? I have found (at least) two different ways to interpret it:

1. $\sigma(i)$ is the letter in the $i$th position (after the permutation is applied);

2. $\sigma(i)$ is the position of the letter $i$ (after the permutation is applied).

In general these two interpretations give rise to different permutations. For example suppose $123$ is being rearranged into, says, $231$. Then interpretation 1 gives \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} but interpretation 2 gives \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} My question will be that which convention do mathematicians usually follow?

Thanks in advance for clearing my doubt.

• If you write $\sigma(i)$ then this will usually mean that you are considering $\sigma$ to be a function, and therefore the first interpretation is the correct one. – Tobias Kildetoft Jul 28 '16 at 8:28
• Ok thanks. But isn't the second interpretation also satisfies the criteria of being a (valid) function? namely (1) the letter $i$ must be at some position (the image of an element must be in the codomain), and (2) the letter $i$ can at most occupy only one position (any element must have at most one image). – Hopf eccentric Jul 28 '16 at 8:34
• But that is not how one considers a permutation to be a function (in fact, a permutation is by definition a bijective function, so the notation $\sigma(i)$ is in this context completely unambiguous). – Tobias Kildetoft Jul 28 '16 at 8:36
• Yeah I know that it is a bijection. I think interpretation 2 also satisfies the bijectivity (1) one-to-one: if the letters $i$ and $j$ occupy the same position, then it must be $i=j$; (2) onto: every position must be occupied by some letter. That's why I am curious about the usual convention people stick to. Anyway, thanks. – Hopf eccentric Jul 28 '16 at 8:42
• Definitely the first. Think about what happens when the set being permuted does not have a 'natural' ordering (e.g. {apple,orange,banana}): the first way of writing makes immediate sense, but for the second you need to arbitrarily pick an order in which to enumerate the elements. – yatima2975 Jul 28 '16 at 9:27

Neither of your interpretations are very clear, although interpretation 1 gives you the correct result if I understand you correctly.

A permutation acts on a set; thinking of the "position" of a letter after applying to permutation (to what?) does not make a lot of sense. You seem to be thinking of having a string $123\ldots n$, where each letter has a distinct position, then you are applying the permutation to this string letter-by-letter to obtain a new string, where you can talk about the "positions". This is a complicated viewpoint, and I don't know that it is especially useful.

Your first interpretation is closest to correct; you should modify it to say "$\sigma(i)$ is the letter obtained by applying the permutation to the letter $i$". Then if $123$ is arranged to $231$, you see that $\sigma:1 \to 2$, $\sigma:2 \to 3$, $\sigma:3 \to 1$. This gives you $$\begin{pmatrix} 1 & 2 & 3\\ \sigma(1) & \sigma(2) & \sigma(3)\end{pmatrix} = \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1\end{pmatrix}.$$

Notice the convenience of this notation; it is very easy to look up the image of any letter under your permutation.

• Note that interpretation (2) is $\sigma^{-1}$. – Dean C Wills Dec 21 '16 at 5:50

Interpretation 1 is correct. If we are given a string ( not just a set ) we want to express permutations of the objects in some useful manner. That's what the Cauchy notation does.

" This is a complicated viewpoint, and I don't know that it is especially useful". As a physicist I assure you, it's the ONLY useful thing about permutation groups. I've never seen permutation groups in physics used any other way.

• It should be noted that ,in general, sets are unordered. Thus the set {1,2,3} is the same as {2,1,3}, or for that matter {2,2,1,3,3,3}. So to say permutation groups act on sets is meaningless. Only when they act upon strings can one permutation be concretely distinguished from another. – Jack Nov 30 '18 at 23:51
• It is perfectly reasonable to have permutations acting on sets. For example, if we have the permutation $\sigma = (1\ 2\ 3\ 4\ 5\ 6\ 7) \in S_{7}$, we can have it act on subsets of size 2, so $\{1,5\}^{\sigma} = \{2,7\}$. It is not necessary to be able to distinguish $\sigma$ completely from this, there will be several permutations sending $\{1,5\} \mapsto \{2,7\}$, but it's still a very important way to use permutation actions. – Morgan Rodgers Dec 1 '18 at 0:56
• Although what I mention in previous comment is not exactly what I meant by "acting on a set": this phrase means that we we have a set of objects and the permutations act on the (individual) objects of this set (so a permutation is a special type of function with that set as the domain). – Morgan Rodgers Dec 1 '18 at 1:03