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 2
```

showing 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.

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.

A passive permutation \(\pi\) replaces an object in position \(i\) by that in position \(\pi(i)\).

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 . 2
```

The `*`

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 2`

showing 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] 4`

`as.function(a*b)(1) # should match fb(fa(1))`

`## [1] 4`

Note, 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] 4`

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 2
```

`a_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 2
```

`a_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 2
```

and 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 1
```

`b_active`

```
## [,1] [,2] [,3] [,4] [,5] [,6]
## place before move 1 2 3 4 5 6
## place after move 5 2 3 4 6 1
```

`b_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 2
```

`b_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
```

To 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] TRUE`

`inverse(b) * inverse(a) == inverse(a*b) # note b precedes a on LHS`

`## [1] TRUE`

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 0
```

But 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 0
```

Row `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 1
```

We 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\).

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.