Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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