Self-inverse permutation
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
applies. An equivalent requirement is
- ,
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 .
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.
Examples
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
- .
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
- .
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
- .
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 .
Another example of a self-inverse permutation is the reflection of n-tuples
- ,
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
- ,
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
- .
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
- .
Conversely, every symmetric permutation matrix corresponds to a self-inverse permutation.
number
Recursive representation
|
In order to determine the number of self-inverse permutations in the symmetric group , the following two cases are distinguished:
- If so , then the remaining numbers must form a self-inverse permutation of the set , which is possible.
- Otherwise , then must hold and the remaining numbers must form a self-inverse permutation of the set , which can happen in different ways.
Since there are possibilities for the choice of , the linear recurrence follows from this for the number of self-inverse permutations
with the initial values and . The number of self-inverse permutations yields for growing the result
and is equal to the number of possible Young tableaus of the order .
Sums display
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
- ,
where the Gaussian bracket represents and applies to all . The numbers suffice for linear recurrence
After a permutation , which consists of exactly disjoint transpositions, has the cycle type , the sum representation is obtained
- ,
in which
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 ).
Generating functions
The exponentially generating function of the sequence of the number of self-inverse permutations is given as
- .
Correspondingly, the exponentially generating function of the sequence is equal to the number of truly self-inverse permutations
- .
Applications
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.
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
- ^ A b Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics . Cambridge University Press, 2009, pp. 122 .
- ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin a. a. 2000, p. 49.
- ^ Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching . 2nd Edition. Addison-Wesley, 1998, pp. 48 .
- ^ A b Alan Camina, Barry Lewis: An Introduction to Enumeration . Springer, 2011, p. 141-142 .
- ^ Roland W. Freund, Ronald W. Hoppe: Numerical Mathematics . 1. Ed .: Stoer, Bulirsch. 10th edition. tape 1 . Springer, 2007, p. 84 .