Why does in a permutation indices move opposite to positions

84 Views Asked by At

This is a small notational observation I first noticed when learning about permutations. I am embarassed to admit that I still do not have a satisfactory explanation for it.

An example of the phenomenon:

Consider a permutation on the ordered set $(v_2,v_3,v_1)$ to give $(v_3,v_1,v_2)$.

One way to write it as a function on the indices, so: $$i(2) = 3,~ i(3)=1,~ i(1)=2$$ Or, represented as $i := (123)$

But, one can write it in positional terms as well, so: $$p(1)=3 ~~ \text{since}~v_2~\text{moves from position 1 to 3}$$ $$p(2)=1 ~~ \text{since}~v_3~\text{moves from position 2 to 1}$$ $$p(3)=2 ~~ \text{since}~v_1~\text{moves from position 3 to 2}$$ This can be represented as $p := (132)$

It is always the case that $$i=p^{-1}$$ Whats the reason for this?

My first thought was, if we consider the labelling as a function from the set of positions to the indices: $$l_1(1)=2,~ l_1(2)=3,~ l_1(3)=1$$ $$l_2(1)=3,~ l_2(2)=1,~ l_2(3)=2$$ then, perhaps $$p = l_2^{-1}\circ i \circ l_1$$ But, of course this doesn't work because $i$ and $p$ are 'opposite' and therefore not 'equivalent' or 'conjugate' (infact $l_2^{-1}\circ i \circ l_1 = Id$)

1

There are 1 best solutions below

0
On BEST ANSWER

Remember that a permutation of $X$ is a bijection from $X$ to $X$. So it's less confusing to write the permutation in your example as $(v_1v_2v_3)$.

About your statement, here's a counterexample: $(v_2,v_3,v_1)\mapsto (v_1,v_3,v_2)$, or $(v_1v_2)$. Using your notation, $i:=(12)$, and $p:=(13)$. But clearly $i\neq p^{-1}$.

The identity works for cyclic permutations if you start with $(v_1,v_2,\cdots,v_n)$, where the indices match the original positions. Why does it work? Think about what it means to move an object from position $a$ to position $b$. The object in position $b$ is now the object that was in position $a$ ($v_b$ is mapped to $v_a$). So, for instance, if $p:=(\cdots abc\cdots)$, then $i:=(\cdots cba\cdots)$.

$$\begin{array}{l c c c c c c c} \text{Before:} & \cdots & v_a & \cdots & v_b & \cdots & v_c & \cdots\\ & & \downarrow & & \downarrow & & \downarrow & \\ \text{After:} & \cdots & ? & \cdots & v_a & \cdots & v_b & \cdots\\ \end{array}$$

Another way of seeing this is writing $p$ and $i$ with function notation: $p(a)=b$ and $i(b)=a$. So $i=p^{-1}$.