Permutation notation: Difference between revisions
clarified postfix notation; removed egregious POV statement |
re-clarify postfix notation, compare Python examples |
||
Line 44: | Line 44: | ||
Confusing these two interpretations will lead to confusing permutations with their inverses.<br> |
Confusing these two interpretations will lead to confusing permutations with their inverses.<br> |
||
[[w:Active and passive transformation|Active and passive transformations]] seem to be a related concept. |
[[w:Active and passive transformation|Active and passive transformations]] seem to be a related concept. |
||
---- |
|||
⚫ | |||
⚫ | |||
⚫ | |||
:<math>\pi \sigma</math> can be thought of as <math>\pi ~ {\scriptstyle after} ~ \sigma</math>, and <math>\pi x</math> as <math>\pi ~ {\scriptstyle of} ~ x</math> |
|||
⚫ | |||
:This notation corresponds to the usual way of writing [[w:function composition|function composition]].<br> |
|||
⚫ | |||
⚫ | |||
:<math>\pi \sigma</math> can be thought of as <math>\pi ~ {\scriptstyle before} ~ \sigma</math>, and <math>x \pi</math> as ([[w:Image (mathematics)|image]] of) <math>x ~ {\scriptstyle under} ~ \pi</math>. |
|||
:This notation is common in [[w:group theory|group theory]]. |
|||
:(In the Python examples in this article <code>(P*Q)(2)</code> = <code>2^P^Q</code> = <code>Q(P(2))</code>. The result is <code>R(2)</code> = 4). |
|||
---- |
|||
<!-- The active interpretation of a permutation should usually be seen as correct, and the passive one as a misunderstanding.<br> [disputed] --> |
|||
In its graphics this article shows all possible interpretations, including the passive ones.<br> |
In its graphics this article shows all possible interpretations, including the passive ones.<br> |
||
But to avoid confusion the accompanying calculations use only active right notation, which is also used by [[#SymPy|SymPy]] and [[#Wolfram|Wolfram]]. |
But to avoid confusion the accompanying calculations use only active right notation, which is also used by [[#SymPy|SymPy]] and [[#Wolfram|Wolfram]]. |
Revision as of 21:18, 10 April 2017
This article examines different notations for the composition of permutations with each other and with vectors.
Permutations are bijections from a set to itself, and the set does not need to have an order.
But they can also be described as operations that move things from places to other places — which is the natural mental image when the permutation is e.g. a rotation of a cube.
In the end it does not matter what kind of mental image is used to understand what a permutation is or does, as long as there is no ambiguity what result a formula will yield.
When a permutation is interpreted as moving objects from places to other places, there are two ways to describe it.
The usual way is as an active permutation or map or substitution:
- moves an object from place to place . In the arrow diagram the one-line notation denotes where the arrows go.
- The result of applying on a vector is .
But may also be represented by the result of applying it to the natural order. This is called a passive permutation[1] or (re)arrangement or ordering:
- replaces an object in position by that in position . In the arrow diagram the one-line notation denotes where the arrows come from.
- In this case the result of applying on a vector is .
Confusing these two interpretations will lead to confusing permutations with their inverses.
Active and passive transformations seem to be a related concept.
Composition of permutations is associative, but not commutative.
With prefix notation or left action .
- can be thought of as , and as
- This notation corresponds to the usual way of writing function composition.
With postfix notation or right action .
- can be thought of as , and as (image of) .
- This notation is common in group theory.
- (In the Python examples in this article
(P*Q)(2)
=2^P^Q
=Q(P(2))
. The result isR(2)
= 4).
In its graphics this article shows all possible interpretations, including the passive ones.
But to avoid confusion the accompanying calculations use only active right notation, which is also used by SymPy and Wolfram.
Notations
Active
If permuting by gives the permutation is active.
Active left
AL |
---|
If the notation should be seen as active left. * means and can be written . can be written . Permuting by may be written in different ways: The notation with the dot is just an abbreviation one may define. With two permutations it means: |
Active right
AR |
---|
If the notation should be seen as active right. * means and can be written . can be written . Permuting by may be written in different ways: (Compare box 12a.) The abbreviation with the dot corresponds to the function |
Passive
If permuting by gives the permutation is passive.
Passive left should be seen as a misunderstanding of active right, and passive right should be seen as a misunderstanding of active left. *
* (Unless permuting a vector proofs otherwise.)
Examples with 5-element permutations
Permutations can be combined with:
- other permutations (boxes 1 to 11)
- vectors of the same length with arbitrary elements (green boxes 12 and 16)
- vectors of arbitrary length with elements from the same range,
i.e. maps with the same codomain as the permutation, but bijectivity not required (blue boxes 14 and 15) - scalars from the same range (red boxes 13 and 17, compare blue box 14)
The variables used in the main examples are:
- the permutations and
- the vector (in the graphics simply )
- the vector
In the Wolfram calculations the 1-based equivalents are used.
Permutations of four elements are identified by their index numbers in RevCoLex order, i.e. as the -th finite permutation.
is denoted where it appears among other permutations of only four elements. (See box 19, compare with box 1.)
(Equivalents for the permutations of five elements would be , and [2], but only the letters are used.)
Box 0 Initialisation for the computations |
---|
Python: The simple function from sympy.combinatorics import Permutation def times(positions, sequence): return [sequence[i] for i in positions] def inv(perm): length = len(perm) if sorted(perm) != list(range(length)): print('Inverse not possible!') else: inverse = [0] * length for key, val in enumerate(perm): inverse[val] = key return inverse p = [1, 3, 0, 2, 4] q = [4, 3, 2, 1, 0] r = times(p, q) P = Permutation(p) Q = Permutation(q) R = P * Q v = ['0', '1', '2', '3', '4'] e = [0, 0, 4, 2, 3, 2] Wolfram: p = {2,4,1,3,5} q = {5,4,3,2,1} v = {v1,v2,v3,v4,v5} e = {1,1,5,3,4,3} |
Active vs. passive
A simple rule to avoid passive permutations: If the rows of a permutation matrix are labelled, the cycles must go clockwise (AR). If the columns are labelled, the cycles must go anticlockwise (AL).
Box 1 Ambiguity of | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Passive (PL): | Active (AR): | ||||||||||||||||||
If it is only required, that , and no one intends to permute vectors, there is no need to choose an interpretation. If on the other hand it is only required that a permutation permutes the vector into , it does dot matter if it is labelled or . While the permutations on the left and right have the same labels and do different things, the permutations below do exactly the same as those above them, but are labelled differently.
|
Left vs. right
Box 2 Ambiguity of with active permutations | |||
---|---|---|---|
Left (AL): | Right (AR): | ||
Box 3 Ambiguity of with passive permutations | |||
---|---|---|---|
Left (PL): | Right (PR): | ||
The following examples show with arrow diagrams what the composed permutations actually do, and how this can be interpreted as a product in two different ways, corresponding to two different matrix multiplications.
The two arrangements of matrices are symmetric to each other, including the direction of the arrows in the matrices.
In other terms: The matrix image on the left and on the right show exactly the same thing in a different way.
The arrows in both arrangements of matrices are the same as in the arrow diagram to their left.
In prefix notation (left action) means . In postfix notation (right action) means .
Obviously and are just different ways to say the same thing.
Active
Box 4 Formulas for and in two-line and cycle notation | |
---|---|
AL: | AR: |
|
|
|
|
The top left row is reordered like the bottom right, so the bottom left row becomes the result. | The top right row is reordered like the bottom left, so the bottom right row becomes the result. |
Box 5 Computation (AR only) | ||||||||
---|---|---|---|---|---|---|---|---|
|
Box 6 | |||
---|---|---|---|
|
Box 7 | |||
---|---|---|---|
|
Box 8 | |||
---|---|---|---|
|
Passive
Box 9 | |||
---|---|---|---|
|
Box 10 | |||
---|---|---|---|
|
Box 11 | |||
---|---|---|---|
|
Vectors, scalars and non-bijective maps
Active
Box 12 Permuting a vector | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Box 13 Concatenation with a scalar as permuting a vector | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Box 14 Concatenation with a scalar as concatenation with a constant | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
|
Box 15 Concatenation with a non-bijective map | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Passive
Box 16 Permuting a vector | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Box 17 Concatenation with a scalar as permuting a vector | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Examples with permutations of the square
The dihedral group Dih4 is the group of symmetries of the square.
Box 18 Cayley graphs | ||
---|---|---|
The three Cayley graphs below show how each element of the group can be displayed as a product of two different elements. | ||
(orange arrow), (green edge) | (red arrow), (blue edge) | (blue edge), (pink edge) |
orange arrow from to : green edge between and : |
red arrow from to : blue edge between and : |
blue edge between and : pink edge between and : |
Active vs. passive
Box 19 Ambiguity of | |||||||
---|---|---|---|---|---|---|---|
Passive (PL): | Active (AR): | ||||||
The inverse of is , while and are self-conjugate. The Cayley table above contains , so it fits the row above, and it contains , so its transpose would fit the row below. As above (box 1) the permutations on the left and right have the same labels and do different things, while the permutations below do exactly the same as those above them, but are labelled differently.
|
Left vs. right
Active
Box 20 | ||
---|---|---|
|
Box 21 | ||
---|---|---|
|
Passive
Box 22 | ||
---|---|---|
|
Box 23 | ||
---|---|---|
|
Languages
Wolfram
Wolfram Alpha displays permutations in a way that resembles PL representation in this article,
which – if only permutation concatenation is concerned – is the same as AR. (See boxes 1 and 19.)
is shown as , but in the arrow diagram and the permutation matrix the arrow from 1 goes to 3 — not to 2.
Wolfram does not accept the element 0, so the examples are converted to 1-based permutations:
P = (1243)(5) = 2 4 1 3 5 http://www.wolframalpha.com/input/?i=permutation+(1+2+4+3)(5) Q = (15)(24)(3) = 5 4 3 2 1 http://www.wolframalpha.com/input/?i=permutation+(1+5)(2+4)(3) R = (1435)(2) = 4 2 5 3 1 http://www.wolframalpha.com/input/?i=permutation+(1+4+3+5)(2) S = (1523)(4) = 5 3 1 4 2 http://www.wolframalpha.com/input/?i=permutation+(1+5+2+3)(4)
A blogpost from 2011 shows that back then the list notation with curly braces was the inverse of the one-line notation.
But in the calculations shown in this article (done in Mathematica Online in December 2016) the permutation p = {2,4,1,3,5}
corresponds to Cycles[{{1,2,4,3}}]
.
Apparently in the meantime a notation people found confusing was dropped in favour of a more mainstream one.
This article uses three binary Wolfram functions:
PermutationProduct[a, b, c] gives the product of permutations a, b, c. (box 5b)
PermutationReplace[expr, perm] replaces each part in expr by its image under the permutation perm. (boxes 13a, 15a, 17a)
Permute[l, p] permutes list l according to permutation p. (boxes 12a, 16a)
More examples | ||
---|---|---|
I: p O: {2,4,1,3,5} I: q O: {5,4,3,2,1} I: PermutationProduct[p, q] (* R *) O: {4,2,5,3,1} I: PermutationProduct[q, p] (* S *) O: {5,3,1,4,2} For two permutations I: PermutationReplace[p, q] (* R *) O: {4,2,5,3,1} I: PermutationReplace[q, p] (* S *) O: {5,3,1,4,2}
I: Permute[p, q] O: {5,3,1,4,2} I: Permute[q, p] O: {3,5,2,4,1}
Confusingly the result of The result of |
SymPy
http://docs.sympy.org/dev/modules/combinatorics/permutations.html
The composite of two permutations p*q means first apply p, then q, so i^(p*q) = (i^p)^q which is i^p^q according to Python precedence rules.
SymPy has two operators for permutations: Multiplication (*
) and what could be called exponentiation (^
). The latter seems to be intended only to access elements of a permutation, but can be used to combine two combinations. The result of a^b
is the same as ~b*a*b
(see Python script), which is a permutation in the same conjugacy class.
Negative results for ~p(i)
|
---|
Inverse permutations behave strangely when accessed from the right.
|
Sources
There appear to be no sources that actually use the passive interpretation of permutations. So the sources below are active left and active right.
Left
Aigner 2007
We read a product always from right to left, thus for
- , ,
we have
- and .
We call the word representation of .
Aigner, Martin (2007). A course in enumeration. Berlin New York: Springer. ISBN 3642072534. — Word Representation (p. 27 ff)
Right
Knuth 1973
In TAoCP Knuth states that in his book permutations are always multiplied from left to right, and gives the following example:
SymPy |
---|
>>> from sympy.combinatorics import Permutation >>> a = Permutation(0, 2)(1, 5, 3) >>> b = Permutation(0, 5)(1, 4)(2, 3) >>> a * b Permutation(0, 3, 4, 1)(2, 5) >>> b * a Permutation(0, 3)(1, 4, 5, 2) >>> Permutation.print_cyclic = False >>> a Permutation[2, 5, 0, 1, 4, 3] >>> b Permutation[5, 4, 3, 2, 1, 0] >>> a * b Permutation[3, 0, 5, 4, 1, 2] >>> b * a Permutation[3, 4, 1, 0, 5, 2] |
The left permutation sees the argument first:
Notice that the image of 1 under is , etc.
SymPy: (1^a)^b
= 5^b
= 0
This is not to be confused with right to left multiplication of permutations, i.e. the way functions are composed:
[...] traditional functional notation, in which one writes , makes it natural to think that should mean .
SymPy: a(b(1))
= a(4)
= 4
Knuth, Donald (1973). The art of computer programming. Reading, Mass: Addison-Wesley Pub. Co. ISBN 0201896850. — Chapter 7.2.1.2. Generating all permutations
Cameron 1994
Cameron decribes the active form of a permutation as a one-to-one mapping from to itself, and the passive form as the ordered n-tuple .
I wrote for the result of applying the function to the element .
[...] In order that the result of applying first and then can be called , it is more natural to denote the image of under as .
[Footnote:] We say that permutations act on the right if they compose according to this rule.
What Cameron calls the passive permutation is simply the one-line or word representation of an (active) permutation, not a passive permutation in the sense of this article.
Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 0-521-45761-0 — Chapter 3.5 Permutations (p. 29)
Grimaldi 2004
Grimaldi defines as the left rotation of a triangle and as the reflection that leaves the right base angle in place.
Their product is the reflection about the vertical axis.
Grimaldi, Ralph (2004). Discrete and combinatorial mathematics : an applied introduction. Reading, Mass: Addison-Wesley Longman. ISBN 0321211030. — Example 16.7 (p.749)
References
- ↑ Some authors – see Cameron (1994) – call a permutations one-line notation the passive form. But this article calls a permutation passive when its one-line notation denotes where the arrows in its arrow diagram come from — as opposed to where they go. In the 19th century passive permutations were called permutations, while permutations in the modern sense were called substitutions.
- ↑ Compare this list of the first 40320 finite permutations: https://oeis.org/A198380/a198380_1.txt (1-based)