The permutation group: active and passive permutations, and the order of operations
Robin K. S. Hankin
2023-02-22
Order of operations can be confusing when considering permutation groups. Here I discuss active and passive transforms, order of operations, prefix and postfix notation, and associativity from the perspective of the permutations R package.
Consider the following:
a <- as.cycle("(145)(26)")
a## [1] (145)(26)Thus we can see that \(a\) has a three-cycle \((145)\) and a two-cycle \((26)\). We can express \(a\) in word form (note that we have to stop the print method from printing in cycle form by changing the default):
options("print_word_as_cycle" = FALSE)
(a <- as.word(a))## {1} {2} {3} {4} {5} {6}
## [1] 4 6 . 5 1 2showing that 3 is a fixed point (indicated with a dot). In matrix form we would have:
\[ \left( \begin{array}{ccccccccc} 1&2&3&4&5&6\\ 4&6&3&5&1&2 \end{array} \right) \]
Expressed in functional notation, we have a function \(a\colon [6]\rightarrow [6]\) (here \([n]=\left\{1,2,\ldots,n\right\}\)); and we have \(a(1)=4\), \(a(2)=5\), \(a(3)=3\), and so on. If these were objects, or people, we might want to keep track of where they are. We would say: “at the start, object \(i\) sits in place \(i\), \(i\in[6]\). Then, after the move, object 1 is in place 4, object 2 in place 5, object 3 in place 3, and so on”. This information is encapsulated by as.word(a). In R matrix form we would have
a_active <- rbind(1:6,as.word(a))
rownames(a_active) <- c("place before move","place after move")
a_active## [,1] [,2] [,3] [,4] [,5] [,6]
## place before move 1 2 3 4 5 6
## place after move 4 6 3 5 1 2(in the above R chunk, note how the top row is 1:6. We give the objects persistent labels: each object is named according to the place it sits in, before any moving). On the other hand, we might be more interested in the places. We might want to know which object is sitting in place 4. We would say: “at the start, object \(i\) sits in place \(i\), \(i\in[6]\). Then place 1 is occupied by object 4, place 2 occupied by object 5, and so on”. This information is technically represented by permutation a but in an obscure form. To answer the question “which object is in place \(i\)?” in a convenient way, we need to rearrange the permutation:
\[ \left( \begin{array}{ccccccccc} 1&2&3&4&5&6\\ 4&6&3&5&1&2 \end{array} \right) {\mbox{swap rows}\atop\longrightarrow} \left( \begin{array}{ccccccccc} 4&6&3&5&1&2\\ 1&2&3&4&5&6 \end{array} \right){\mbox{shuffle columns}\atop\longrightarrow} \left( \begin{array}{ccccccccc} 1&2&3&4&5&6\\ 5&6&3&1&4&2 \end{array} \right) \]
In the above, it is easy to see that the rearrangement of permutation is equivalent to taking a group-theoretic inverse:
inverse(a)## {1} {2} {3} {4} {5} {6}
## [1] 5 6 . 1 4 2(even now I find the R idiom for inversion to be unreasonably elegant: a[a] <- seq_along(a)). In R idiom, the two-row matrix form would use inverse():
a_passive <- rbind(1:6,as.word(inverse(a)))
rownames(a_passive) <- c("place after move","place before move")
a_passive## [,1] [,2] [,3] [,4] [,5] [,6]
## place after move 1 2 3 4 5 6
## place before move 5 6 3 1 4 2(in the above R chunk, note how the top row—the place an object sits in after the move, is 1:6). Thus from the first column we see that the object currently in place 1 was originally in place 5. If the people subsequently move again, the mathematics and the R idiom depend on whether we are interested in people, or places. We need to specify use of active or passive transformations, much as in the Lorentz package.
Active permutations
An active permutation \(\pi\) moves an object from place \(i\) to place \(\pi(i)\). Textbooks and undergraduate courses usually use this system, and is used above.
Passive permutations
A passive permutation \(\pi\) replaces an object in position \(i\) by that in position \(\pi(i)\).
Composition of active permutations
Suppose we have (active) permutation a as above, and another active permutation b:
b <- as.word(c(5, 2, 3, 4, 6, 1))
b## {1} {2} {3} {4} {5} {6}
## [1] 5 . . . 6 1(note the three dots representing three fixed points of b). Note carefully that the operations \(a\) and \(b\) do not commute and we will discuss this in the context of active and passive transforms. What is the result of executing \(a\), followed by \(b\)? Symbolically we have:
\[ \overbrace{ \left( \begin{array}{ccccccccc} 1&2&3&4&5&6\\ 4&6&3&5&1&2 \end{array} \right) }^{a} \circ \overbrace{ \left( \begin{array}{ccccccccc} 1&2&3&4&5&6\\ 5&2&3&4&6&1\\ \end{array} \right) }^{b}= \overbrace{ \left( \begin{array}{ccccccccc} 1&2&3&4&5&6\\ 4&1&3&6&5&2\\ \end{array} \right) }^{a\circ b} \]
Thus, for example, \(4\longrightarrow 5\longrightarrow 6\). Considering the operation \(a\circ b\), this means that we perform permutation a first, and then perform permutation b. Taking this one step at a time we would have, for example: “the person in place 4 (this is object 4) moves to place 5 (but is still object 4) \(\ldots\) and then the object in place 5 (this is still object 4) moves to place 6”. See how we track the object that started in place 4 (that is, object 4) over two permutations, and so overall object 4 ends up in place 6. We see this on the right hand side: the fourth column of \(a\circ b\) is \(\left(\begin{array}{c}4\\6\end{array}\right)\). If we execute a and then b using active language [explicitly: express a and b as active permutations, and express the result of performing a then b in active language], we can use standard permutation composition, in R idiom the * operator:
a*b## {1} {2} {3} {4} {5} {6}
## [1] 4 1 . 6 . 2The * operator in R idiom is essentially carries out b[a] to evaluate a*b (which is why indexing starts at 1, not 0). Indeed we may verify that package idiom operates as expected:
as.vector(b)[as.vector(a)]## [1] 4 1 3 6 5 2showing agreement. With functional notation (also known as prefix notation) we can ask what happens to the object originally in place 1 (that would be object 1)
fa <- as.function(a)
fb <- as.function(b)
fb(fa(1))## [1] 4as.function(a*b)(1) # should match fb(fa(1))## [1] 4Note, however, the confusing order of operations: in functional notation, if we want to operate on an element \(x\) by function \(f\) and then by function \(g\) we write \(g(f(x))\) for the two successive mappings \(x\longrightarrow f(x)\longrightarrow g(f(x))\). Postfix notation would denote the same process as \(xfg\), as shorthand for \((xf)g\). In R idiom, this is implemented by the excellent magrittr package:
1 %>% fa %>% fb # idiom for fb(fa(1)), should match result above## [1] 4Composition of passive permutations
Now we consider the same operations a and b as discussed above, and perform a and then b. But this time we express the permutations, and their composition, in passive form, and this requires some modification. First we will express a and b in passive matrix form which we will call a_passive and b_passive:
a # word form ## {1} {2} {3} {4} {5} {6}
## [1] 4 6 . 5 1 2a_active # matrix form (active)## [,1] [,2] [,3] [,4] [,5] [,6]
## place before move 1 2 3 4 5 6
## place after move 4 6 3 5 1 2a_passive # matrix form (passive)## [,1] [,2] [,3] [,4] [,5] [,6]
## place after move 1 2 3 4 5 6
## place before move 5 6 3 1 4 2and then b, but we need to create equivalents b_active and b_passive which we do as before:
b## {1} {2} {3} {4} {5} {6}
## [1] 5 . . . 6 1b_active## [,1] [,2] [,3] [,4] [,5] [,6]
## place before move 1 2 3 4 5 6
## place after move 5 2 3 4 6 1b_passive## [,1] [,2] [,3] [,4] [,5] [,6]
## place after move 1 2 3 4 5 6
## place before move 6 2 3 4 1 5(note again the relationship between b_active and b_passive). We want to perform a and then b as before, but this time we want to use matrices a_passive and b_passive:
a_passive## [,1] [,2] [,3] [,4] [,5] [,6]
## place after move 1 2 3 4 5 6
## place before move 5 6 3 1 4 2b_passive## [,1] [,2] [,3] [,4] [,5] [,6]
## place after move 1 2 3 4 5 6
## place before move 6 2 3 4 1 5To work out the composition of a_passive and b_passive [explicitly: give the passive transform corresponding to performing a_passive first, and then b_passive second] we want a passive transformation, that is, a matrix with the same row labels as, say a_passive and first row 1:6. Let us call the result of these two permutations ab_passive. Given that ab_passive[1,1]=1, we ask “what is ab_passive[2,1]? This is equivalent to asking,”we have just performed permutation a followed by b. The object currently in place 1: where was it before this composition of permutations?"
To figure out which object is in place 1, we would look at b_passive, being the most recent operation. We would then look at the first column of b_passive and say that the object that was in place 6 was moved by b_passive to place 1. And then you would have to figure out which object was in place 6 before b_passive was executed. To answer that, you would look at a_passive and see, from column 6 of a_passive that the object in place 6 was moved from place 2 by a. Thus the passive transform ab_passive indicates that the object in place 1 after the move was in place 2 before the move. We would have \(1\longrightarrow 6\longrightarrow 2\) where in this case “\(\longrightarrow\)” means “comes from”.
We can thus represent the passive transformation by b_passive*a_passive: see how the R idiom for permutation composition “*” is used in exactly the same way for active and passive permutations, but with a different meaning which requires us to reverse the order of permutations. To express the result, ab_passive in active language we need to take the group-theoretic inverse of the composition. Recalling that passive transforms are the group-theoretic inverses of the same active transformation, in algebraic notation we would have
\[ \left(a^{-1}b^{-1}\right)^{-1}=ab;\qquad a^{-1}b^{-1}=\left(ab\right)^{-1} \]
and in R idiom we would have
inverse(inverse(b) * inverse(a)) == a*b # both should be TRUE## [1] TRUEinverse(b) * inverse(a) == inverse(a*b) # note b precedes a on LHS## [1] TRUEPermutation matrices
Now we will show how permutation matrices work and how they deal with active and passive language.
g <- as.cycle(c(1,2,6))
g## [1] (126)Then we can express g in terms of permutation matrices:
pg <- perm_matrix(g)
pg## 1 2 3 4 5 6
## 1 0 1 0 0 0 0
## 2 0 0 0 0 0 1
## 3 0 0 1 0 0 0
## 4 0 0 0 1 0 0
## 5 0 0 0 0 1 0
## 6 1 0 0 0 0 0But it is convenient to relabel the rows and the columns:
dimnames(pg) <- list(place_before_move=1:6,place_after_move=1:6)
pg## place_after_move
## place_before_move 1 2 3 4 5 6
## 1 0 1 0 0 0 0
## 2 0 0 0 0 0 1
## 3 0 0 1 0 0 0
## 4 0 0 0 1 0 0
## 5 0 0 0 0 1 0
## 6 1 0 0 0 0 0Row n of matrix pg shows where the object that was in place n before the move ends up. Thus, looking at the top row (row 1), we see that the object that was in place 1 is now in place 2 [because the second column of row 1 is nonzero]. The second row (row 2) shows that the object that was in place 2 is now in place 6, the object that was in place 3 is now in place 6, and so on. This is active language.
We can see that taking the transpose is equivalent to inverting the matrix: a permutation matrix is orthogonal. Now we can consider a second permutation h and convert it to matrix form:
h <- as.word(c(1,3,4,5,2,6))
h## {1} {2} {3} {4} {5} {6}
## [1] . 3 4 5 2 .ph <- perm_matrix(h)
dimnames(ph) <- list(place_before_move=1:6,place_after_move=1:6)
ph## place_after_move
## place_before_move 1 2 3 4 5 6
## 1 1 0 0 0 0 0
## 2 0 0 1 0 0 0
## 3 0 0 0 1 0 0
## 4 0 0 0 0 1 0
## 5 0 1 0 0 0 0
## 6 0 0 0 0 0 1We now consider what happens with successive permutations, as above, but this time using permutation matrices. We will permute first with g and then with h, using matrix multiplication.
pg %*% ph## place_after_move
## place_before_move 1 2 3 4 5 6
## 1 0 0 1 0 0 0
## 2 0 0 0 0 0 1
## 3 0 0 0 1 0 0
## 4 0 0 0 0 1 0
## 5 0 1 0 0 0 0
## 6 1 0 0 0 0 0 pg ph pg %*% ph
place_after_move place_after_move place_after_move
place_before_move 1 2 3 4 5 6 place_before_move 1 2 3 4 5 6 place_before_move 1 2 3 4 5 6
1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0
2 0 0 0 0 0 1 2 0 0 1 0 0 0 2 0 0 0 0 0 1
3 0 0 1 0 0 0 3 0 0 0 1 0 0 3 0 0 0 1 0 0
4 0 0 0 1 0 0 4 0 0 0 0 1 0 4 0 0 0 0 1 0
5 0 0 0 0 1 0 5 0 1 0 0 0 0 5 0 1 0 0 0 0
6 1 0 0 0 0 0 6 0 0 0 0 0 1 6 1 0 0 0 0 0(the above is hand-edited to put the matrices side-by-side). Let us consider the top row of pg. This multiplies by each column of ph but the only nonzero term is with column 3 of ph which has row 2 nonzero. Thus (pg%*%ph)[1,3]==1. The process is, symbolically, \(1\longrightarrow 2\longrightarrow 3\).
Passive language for permutation matrices
Alternatively, we could look at matrix pg in terms of columns. Column n of this matrix shows where the object that ended up in place n came from. Thus, looking at column 1, we see that the object that ended up in column 1 came from place 6, and the object that ended up in place 2 came from place 1, and so on. This is passive language.
Thus the passive matrix is the transpose of the active matrix (we could see this by swapping the dimension names). Now we use the matrix rule
\[ AB=(B'A')' \]
to show that permutation matrix multiplication has to be in the opposite order for passive matrices. Of course, we could observe that permutation matrices are orthogonal and use
\[ AB=\left(B^{-1}A^{-1}\right)^{-1} \]
instead.