To cite the permutations package in publications, please use Hankin (2020). When considering permutation
groups, the order of operations can be confusing. 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:

`## [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 by changing the default print method which coerces to cycle form:

```
## 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 5, object 2 in place 6, 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:

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

:

```
## 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:

```
## 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:

`## [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)

`## [1] 4`

`## [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] 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`

:

```
## 1 2 3 4 5 6
## [1] 4 6 . 5 1 2
```

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

```
## [,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:

```
## 1 2 3 4 5 6
## [1] 5 . . . 6 1
```

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

```
## [,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`

:

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

```
## [,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

`## [1] TRUE`

`## [1] TRUE`

Now we will show how permutation matrices work and how they deal with active and passive language.

`## [1] (126)`

Then we can express `g`

in terms of permutation
matrices:

```
## 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:

```
## 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:

```
## 1 2 3 4 5 6
## [1] . 3 4 5 2 .
```

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

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

Hankin, R. K. S. 2020. “Introducing the Permutations
R Package.” *SoftwareX* 11. https://doi.org/10.1016/j.softx.2020.100453.