# Notation: permutation and its inverse

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.}$$

• 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? – edgar.holleis May 1 '13 at 12:37
• I see: then I don't understand your question. – DonAntonio May 1 '13 at 12:39
• BTW, I think that what Federica got is exactly the same as I did but using another path... – 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.

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