Self-inverse permutation

Graph of a self-inverse permutation of the numbers from 1 to 8. The permutation consists only of cycles of length 1 or 2.

In combinatorics and group theory, a self-inverse or involutive permutation is a permutation that is equal to its inverse . A permutation is self-inverse if and only if its cycle representation consists exclusively of cycles of length one or two. The order of a self-inverse permutation is thus a maximum of two. Furthermore, the permutation matrix of a self-inverse permutation is always symmetrical . Self-inverse permutations play an important role in cryptography .

definition

If the symmetric group of all permutations of the set , then a permutation is called self-inverse or involutor if it is equal to its inverse permutation , so if ${\displaystyle S_{n}}$ ${\displaystyle \{1,\ldots ,n\}}$ ${\displaystyle \pi \in S_{n}}$ ${\displaystyle \pi ^{-1}}$

${\displaystyle \pi =\pi ^{-1}}$

applies. An equivalent requirement is

${\displaystyle \pi ^{2}=\operatorname {id} }$,

where are the sequential execution of with itself and the identical permutation . A self-inverse permutation thus represents an involution on the set . In addition, if a self-inverse permutation has no fixed points , so it applies to all , then one speaks of a genuinely self-inverse permutation . It is also called a genuinely involutive permutation . ${\displaystyle \pi ^{2}=\pi \circ \pi }$ ${\displaystyle \pi }$ ${\displaystyle \operatorname {id} }$ ${\displaystyle \{1,\dotsc ,n\}}$ ${\displaystyle \pi (i)\neq i}$ ${\displaystyle i=1,\dotsc ,n}$

In a more general way, permutations of any finite sets , for example alphabets , can be considered, but the analysis of the mathematical properties can be limited to the first natural numbers. ${\displaystyle n}$

Examples

${\displaystyle n}$	Self-inverse permutations			number
1	id			1
2	id	(1 2)		2
3	id	(1 2), (1 3), (2 3)		4th
4th	id	(1 2), (1 3), (1 4), (2 3), (2 4), (3 4)	(1 2) (3 4), (1 3) (2 4), (1 4) (2 3)	10

The identical permutation is trivially self-inverse, because it holds by definition ${\displaystyle \operatorname {id} }$

${\displaystyle \operatorname {id} ^{2}=\operatorname {id} \circ \operatorname {id} =\operatorname {id} }$.

Next, each of permutation (transposition) of two numbers and because even inverse, the double application of such a permutation exchanges the two numbers back and it is thus ${\displaystyle \tau _{ij}=(i~j)}$ ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle (\tau _{ij})^{2}=(i~j)(i~j)=\operatorname {id} }$.

The multiple exchange of pairs of different numbers represents a self-inverse permutation, because due to the disjointness of the cycles, the following applies accordingly ${\displaystyle (i_{1}~i_{2})\ldots (i_{2k-1}~i_{2k})}$ ${\displaystyle i_{1},\dotsc ,i_{2k}}$

${\displaystyle \left(\tau _{i_{1}i_{2}}\circ \ldots \circ \tau _{i_{2k-1}i_{2k}}\right)^{2}=(\tau _{i_{1}i_{2}})^{2}\circ \ldots \circ (\tau _{i_{2k-1}i_{2k}})^{2}=\operatorname {id} \circ \ldots \circ \operatorname {id} =\operatorname {id} }$.

The adjacent table lists all self-inverse permutations of the symmetrical groups up to degree four. Only the permutation and the three permutations in , which each swap two pairs of numbers, are truly self-inverse . ${\displaystyle (1~2)\in S_{2}}$ ${\displaystyle S_{4}}$

Another example of a self-inverse permutation is the reflection of n-tuples

${\displaystyle \sigma _{n}={\begin{pmatrix}1&2&\dotsb &n\\n&n-1&\dotsb &1\end{pmatrix}}=(1~n)(2~(n-1))(3~(n-2))\cdots }$,

see also word (Theoretical Computer Science) §Spiegelung und Palindrome .

properties

Since a cycle 's length can only lead back to its identity after it has been executed one after the other and the cycle representation of a permutation (except for the order of the cycles and the arrangement of the numbers within the cycles) is unambiguous, a permutation is self-inverse if and only if its cycle representation is exclusively Cycles of length one or two. The cycle representation has a self-inverse permutation ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \pi \in S_{n}}$

${\displaystyle \pi =(i_{1}~i_{2})\ldots (i_{2k-1}~i_{2k})(i_{2k+1})\ldots (i_{n})}$,

where denotes the number of two and the number of one cycles. The cycle type of a self-inverse permutation is thus of the form ${\displaystyle k\leq n/2}$ ${\displaystyle n-2k}$ ${\displaystyle \pi }$

${\displaystyle \operatorname {typ} (\pi )=1^{n-2k}2^{k}}$.

The self-inverse permutations are thus exactly the permutations of order one or two, with the identical permutation being the only first order permutation. The permutation matrix of a self-inverse permutation is always symmetrical , because it is true with the orthogonality of permutation matrices ${\displaystyle P_{\pi }}$ ${\displaystyle \pi }$

${\displaystyle P_{\pi }^{T}=P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }}$.

Conversely, every symmetric permutation matrix corresponds to a self-inverse permutation.

number

Recursive representation

${\displaystyle {\begin{pmatrix}1&2&3&\dotsb &n\\1&\ast &\ast &\dotsb &\ast \end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}1&2&3&\dotsb &n\\2&1&\ast &\dotsb &\ast \end{pmatrix}}}$ When deriving the recurrence, a distinction must be made between two cases: either is or there are and . In the example is . ${\displaystyle \pi (1)=1}$ ${\displaystyle \pi (1)=j\neq 1}$ ${\displaystyle \pi (j)=1}$ ${\displaystyle j=2}$

In order to determine the number of self-inverse permutations in the symmetric group , the following two cases are distinguished: ${\displaystyle I_{n}}$ ${\displaystyle S_{n}}$

• If so , then the remaining numbers must form a self-inverse permutation of the set , which is possible. ${\displaystyle \pi (1)=1}$ ${\displaystyle n-1}$ ${\displaystyle \{2,\dotsc ,n\}}$ ${\displaystyle I_{n-1}}$
• Otherwise , then must hold and the remaining numbers must form a self-inverse permutation of the set , which can happen in different ways. ${\displaystyle \pi (1)=j\neq 1}$ ${\displaystyle \pi (j)=1}$ ${\displaystyle n-2}$ ${\displaystyle \{2,\dotsc ,n\}\setminus \{j\}}$ ${\displaystyle I_{n-2}}$

Since there are possibilities for the choice of , the linear recurrence follows from this for the number of self-inverse permutations ${\displaystyle n-1}$ ${\displaystyle j}$

${\displaystyle I_{n}=I_{n-1}+(n-1)I_{n-2}}$

with the initial values and . The number of self-inverse permutations yields for growing the result ${\displaystyle I_{1}=1}$ ${\displaystyle I_{2}=2}$ ${\displaystyle n}$

${\displaystyle 1,2,4,10,26,76,232,764,2620,9496,\dotsc }$(Follow A000085 in OEIS )

and is equal to the number of possible Young tableaus of the order . ${\displaystyle n}$

Sums display

Number of permutations of numbers that consist of disjoint transpositions ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	0	1	2	3	4th	5	total
1	1						1
2	1	1					2
3	1	3					4th
4th	1	6th	3				10
5	1	10	15th				26th
6th	1	15th	45	15th			76
7th	1	21st	105	105			232
8th	1	28	210	420	105		764
9	1	36	378	1260	945		2620
10	1	45	630	3150	4725	945	9496

Designates the number of permutations in , which consist of exactly disjoint transpositions, then applies to the number of self-inverse permutations ${\displaystyle I_{n,k}}$ ${\displaystyle S_{n}}$ ${\displaystyle k}$

${\displaystyle I_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }I_{n,k}}$,

where the Gaussian bracket represents and applies to all . The numbers suffice for linear recurrence ${\displaystyle \lfloor ~\rfloor }$ ${\displaystyle I_{n,0}=1}$ ${\displaystyle n}$ ${\displaystyle I_{n,k}}$

${\displaystyle I_{n,k}=I_{n-1,k}+(n-2k+1)I_{n-1,k-1}}$(Follow A100861 in OEIS ).

After a permutation , which consists of exactly disjoint transpositions, has the cycle type , the sum representation is obtained ${\displaystyle \pi \in S_{n}}$ ${\displaystyle k}$ ${\displaystyle \operatorname {typ} (\pi )=1^{n-2k}2^{k}}$

${\displaystyle I_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\frac {n!}{(n-2k)!\,k!\,2^{k}}}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}(2k-1)!!}$,

in which

${\displaystyle (2k-1)!!=1\cdot 3\cdot \ldots \cdot (2k-1)={\frac {(2k)!}{k!\,2^{k}}}}$

the dual faculty is. The number corresponds precisely to the number of genuinely self-inverse permutations in , i.e. those permutations that consist of precisely disjoint transpositions and thus have the cycle type (sequence A001147 in OEIS ). ${\displaystyle (2k-1)!!}$ ${\displaystyle I_{2k,k}}$ ${\displaystyle S_{2k}}$ ${\displaystyle k}$ ${\displaystyle \operatorname {typ} (\pi )=2^{k}}$

Generating functions

The exponentially generating function of the sequence of the number of self-inverse permutations is given as ${\displaystyle I_{n}}$

${\displaystyle f(x)=\sum _{n=0}^{\infty }I_{n}{\frac {x^{n}}{n!}}=e^{x+x^{2}/2}}$.

Correspondingly, the exponentially generating function of the sequence is equal to the number of truly self-inverse permutations ${\displaystyle I_{2k,k}}$

${\displaystyle f(x)=\sum _{k=0}^{\infty }I_{2k,k}{\frac {x^{2k}}{(2k)!}}=e^{x^{2}/2}}$.

Applications

Letters swapped by the Enigma encryption machine

In the cryptography itself inverse permutations play an important role. If a message is encrypted using a self-inverse permutation, the message can also be decrypted again using the same permutation. A simple example is the Caesar encryption ROT13 , in which each letter is replaced by the letter shifted by places in the alphabet for encryption . The repeated application then results in a shift by letters and thus again the original message. Another possibility of such an encryption is the use of the bit-wise XOR operation , which is used, for example, with the one-time pad . Much more complex, true self-inverse permutations were carried out by the German encryption machine Enigma , which was used during the Second World War. ${\displaystyle 13}$ ${\displaystyle 26}$

The truly self-inverse permutations are also required to compute the Pfaff determinant of an alternating matrix . A special self-inverse permutation is used for bit inversion in the efficient implementation of the Fast Fourier Transform (FFT).

literature

• Alan Camina, Barry Lewis: An Introduction to Enumeration . Springer, 2011, ISBN 0-85729-600-0 .
• Philippe Flajolet , Robert Sedgewick : Analytic Combinatorics . Cambridge University Press, 2009, ISBN 1-139-47716-1 .
• Donald E. Knuth : The Art of Computer Programming . 2nd Edition. Volume 3: Sorting and Searching. Addison-Wesley, 1998, ISBN 0-201-89685-0 .

Web links

• Eric W. Weisstein : Permutation involution . In: MathWorld (English).

Individual evidence

1. ^ ^{A b} Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics . Cambridge University Press, 2009, pp. 122 .
2. ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin a. a. 2000, p. 49.
3. ^ Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching . 2nd Edition. Addison-Wesley, 1998, pp. 48 .
4. ^ ^{A b} Alan Camina, Barry Lewis: An Introduction to Enumeration . Springer, 2011, p. 141-142 .
5. ^ Roland W. Freund, Ronald W. Hoppe: Numerical Mathematics . 1. Ed .: Stoer, Bulirsch. 10th edition. tape 1 . Springer, 2007, p. 84 .