Consider the sequence $S = (A, B, C, D, E)$ and the permutation $\pi = (4, 1, 3, 5, 2)$:

Which of the following is true? $$ \pi(S) = (B, E, C, A, D) \quad and \quad \pi^{-1}(S) = (D, A, C, E, B) \qquad (1)$$ $$ \pi(S) = (D, A, C, E, B) \quad and \quad \pi^{-1}(S) = (B, E, C, A, D) \qquad (2)$$

Or is there perhaps no single standard on how to write a permutation and its inverse?

Update: My question is much more basic than your answers sofar. Basically I wonder how to correctly apply a permutation to a squence.

In Matlab:

p = [ 4 1 3 5 2 ]
S = [ 'A' 'B' 'C' 'D' 'E' ]
S_perm_1(p) = S              % Option 1
S_perm_2 = S(p)              % Option 2

Your question is essentially about the notation of a permutation of $n$ acting on some set $X^n$ of $n$-tuples of elements from $X$. You are writing $\pi(S)$ for what would usually be written $\pi\cdot S$. Now which of the two alternatives is the right one for you depends on your convention for multiplying permutations, for which different conventions exist. I will suppose that your one-line notation is an abbreviation for a two-line notation, with $\pi=(4,1,3,5,2)$ standing for $\pi=( \begin{smallmatrix} 1&2&3&4&5\\ 4&1&3&5&2\end{smallmatrix})$, the map that sends $1\mapsto 4$, $2\mapsto 1$ etc., and that permutation are multiplied as usual for composition, the left function acting after the right one: $\pi\cdot\sigma:i\mapsto \pi(\sigma(i))$.

In all cases you want an action, written on the left, to satisfy $(\pi\cdot\sigma)\cdot S=\pi\cdot(\sigma\cdot S)$. If you check, only one of the two conventions you propose has this property; this is the convention that $$ \sigma\cdot(x_1,\ldots,x_n)= (x_{\sigma^{-1}(1)},\ldots,x_{\sigma^{-1}(n)}), $$ which in you case concretely becomes $$ ( \begin{smallmatrix} 1&2&3&4&5\\ 4&1&3&5&2\end{smallmatrix})\cdot(A,B,C,D,E) = (B,E,C,A,D). $$ A mnemonic is that if $\sigma$ sends an index $i$ to another index $k$ (so $\sigma(i)=k$), then the action of $\sigma$ sends the component that originally was at position $i$ to end up at position $k$. It makes sense that this is the right convention, since if $\sigma(i)=j$ and $\pi(j)=k$, then $\pi\cdot\sigma$ sends $i$ to $k$, while the action of $\sigma$ sends component $i$ to position $j$, after which the action of $\pi$ sends that component to position $k$, so $\pi\cdot\sigma$ sends the component originally at position $i$ to position $k$.


Assuming $\,A\leftrightarrow 1\,,\,B\leftrightarrow 2\,\ldots\;$ etc., we get

$$(4\;1\;3\;5\;2)=(1\;3\;5\;2\;4)\leftrightarrow (A\;C\;E\;B\;D)=(D\;A\;C\;E\;B)$$

Remember: when dealing with cycles (in permutation groups theory), we have that

$$(a\;b\;c\;d\ldots) = (b\;c\;d\ldots a)=(c\;d\ldots a\;b)=\text{etc.}$$

  • $\begingroup$ I would assume that cycles are irrelevant with regards to my question. I also wouldn't associate the elements of S with the numbers in \pi. My question is about convention and notation: If I want to permute the elements of S according to \pi, what would I get? $\endgroup$ – edgar.holleis May 1 '13 at 12:37
  • $\begingroup$ I see: then I don't understand your question. $\endgroup$ – DonAntonio May 1 '13 at 12:39
  • $\begingroup$ BTW, I think that what Federica got is exactly the same as I did but using another path... $\endgroup$ – DonAntonio May 1 '13 at 12:40

Remember you can always express a cycle as a product of transpositions $$\pi=(4\ 1\ 3\ 5\ 2)=(4 1)(4 3)(4 5)(4 2)$$ from which you get, by simply reversing the order of factors $$\pi^{-1}=(4 2)(4 5 )(4 3)(4 1)=(1 4 2 5 3)$$ Now apply $\pi^{-1}$ to equation $(2)$ of your question and find $$S=\pi^{-1}(D,A,C,E,B)$$ which is true because $\pi^{-1}(D,A,C,E,B)=(D,E,A,B,C)$ and $(D,E,A,B,C)=(A,B,C,D,E)=S$ by cyclicity.

  • $\begingroup$ This implies option (2) is correct. Thank you. $\endgroup$ – edgar.holleis May 1 '13 at 12:56

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.