2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Tobias Kildetoft Jul 28 '16 at 8:28
  • $\begingroup$ 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). $\endgroup$ – Hopf eccentric Jul 28 '16 at 8:34
  • $\begingroup$ 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). $\endgroup$ – Tobias Kildetoft Jul 28 '16 at 8:36
  • $\begingroup$ 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. $\endgroup$ – Hopf eccentric Jul 28 '16 at 8:42
  • 4
    $\begingroup$ 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. $\endgroup$ – yatima2975 Jul 28 '16 at 9:27
3
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jack Nov 30 '18 at 23:51
  • $\begingroup$ 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. $\endgroup$ – Morgan Rodgers Dec 1 '18 at 0:56
  • $\begingroup$ 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). $\endgroup$ – Morgan Rodgers Dec 1 '18 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.