Take the 2-minute tour ×

I've been working on sorting and factorisation problems on permutations for some time now, and have observed that given a permutation $\pi$ of $n$ elements, the permutation $\pi^\chi=\chi\circ\pi\circ\chi^{-1}$, where $\chi=\chi^{-1}=(n\ n-1\ \cdots\ 2\ 1)$, often has attractive properties (with respect to a particular sorting problem).

Is there a name for this "special" permutation (other than "the conjugate of $\pi$ by $\chi$")?

share|improve this question
1. Is χ=(1 2 … n)? 2. Does χ have a name? If χ does not have a commonly-used name, I would not expect that χ∘π∘χ^{-1} has a common name, either. –  Tsuyoshi Ito Sep 6 '10 at 12:14
1. $\chi$ maps $i$ onto $n+1-i$, for $i\in\{1,2,\ldots, n\}$ 2. It is sometimes called the "reverse(d) permutation" or "full reversal", but I don't think these are widely-used. –  Anthony Labarre Sep 6 '10 at 12:18
Thanks for clarification. I thought that (n n−1 … 2 1) denoted a cyclic permutation. –  Tsuyoshi Ito Sep 6 '10 at 13:14

1 Answer 1

up vote 5 down vote accepted

This is the reverse-complement of $\pi$.

In one-line notation, the reverse of a permutation is what you get by writing it backwards and the complement of a permutation is what you get when you replace each entry $i$ by $n -i + 1$. (In other words, one of these operations is multiplication by $\chi$ on the right, the other on the left.) The reverse-complement is what you get by doing both of these operations, or equivalently by giving the permutation matrix a half-turn. (Together with inversion, these operations generate the dihedral group acting on each permutation matrix.)

share|improve this answer
Unfortunately, there doesn't seem to be a nice standard notation for the operation of reverse-complementation. –  JBL Sep 6 '10 at 15:09
Alright, thanks a lot! –  Anthony Labarre Sep 6 '10 at 16:25
I've seen $\pi^{rc}$ for the reverse complement of $\pi$ fairly often, although I believe it's not yet at that point where one can use this notation without defining it. –  Michael Lugo Sep 6 '10 at 18:22
Yes, I've seen it as well; even if it were to become standard, though, I'm not sure I would call it nice :-) –  JBL Sep 6 '10 at 18:35

Your Answer


