nLab
rotation permutation

Contents

Idea

A rotation permutation is, roughly speaking, a permutation in which, if we view the elements of a finite set as people standing in a circle, everybody shifts a given number of steps to the right, or everybody shifts a given number of steps to the left. It is an example of a cyclic permutation.

Formal definition

Recall that a permutation of a finite set XX can formally be defined to be a bijection XXX \rightarrow X.

Definition

Let XX be a finite set with nn elements. Fix an isomorphism, that is to say a bijection, i:X{1,,n}i : X \rightarrow \{ 1, \ldots, n \}. A rotation permutation of XX is a permutation of XX which belongs to the permutation group on XX generated by the permutation p:XXp: X \rightarrow X of XX such that the following diagram commutes, where σ\sigma is the permutation of {1,,n}\{ 1, \ldots, n \} given by ii+1i \mapsto i+1 for 1in11 \leq i \leq n-1 and by n1n \mapsto 1.

Remark

More explicitly, for each integer 0jn0 \leq j \leq n, there is a rotation permutation of {1,,n}\{ 1, \ldots, n \} given by ij+ii \mapsto j+i for 1inj1 \leq i \leq n - j and by ii(nj)i \mapsto i - (n - j) for nj+1inn - j + 1 \leq i \leq n. All rotation permutations of {1,,n}\{ 1, \ldots, n \} are of this form.

Remark

Let XX be a finite set with nn elements. Fix an isomorphism i:X{1,,n}i : X \rightarrow \{ 1, \ldots, n \}. A rotation permutation of XX is a permutation p:XXp: X \rightarrow X of XX such that the following diagram commutes, where σ\sigma is a rotation permutation of {1,,n}\{ 1, \ldots, n \}.

Rotation of a word

One sometimes also speaks of rotation of a word in some algebraic object.

Definition

Let w=a 1a nw=a_{1} \cdots a_{n} be a word in some algebraic object, for example a free monoid or a free group. A rotation of ww is a word in the same algebraic object of the form w=a σ(1)a σ(n)w=a_{\sigma(1)} \cdots a_{\sigma(n)} where σ\sigma is a rotation permutation of {1,,n}\{1, \ldots, n\}.

Example

Let X={a,b}X = \{a,b\} be a set. Examples of a rotation of the word a 2bab 3aa^{2} b a b^{3} a in (the free monoid on) XX are bab 3aa 2=bab 3a 3b a b^{3} a a^{2} = b a b^{3} a^{3}, ab 3aa 2b=ab 3a 3ba b^{3} a a^{2} b = a b^{3} a^{3} b, and aa 2bab 3=a 3bab 3a a^{2} b a b^{3} = a^{3} b a b^{3}.

Last revised on December 31, 2018 at 09:28:02. See the history of this page for a list of all contributions to it.