![](`r system.file("help/figures/permutations.png", package = "permutations")`){width=10%}
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:
library("permutations") library("magrittr")
a <- as.cycle("(145)(26)") a
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))
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
(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)
(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
(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
(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
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)]
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)) as.function(a*b)(1) # should match fb(fa(1))
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
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 a_active # matrix form (active) a_passive # matrix form (passive)
and then b
, but we need to create equivalents b_active
and
b_passive
which we do as before:
b_active <- rbind(1:6,as.word(b)) rownames(b_active) <- c("place before move","place after move") b_passive <- rbind(1:6,as.word(inverse(b))) rownames(b_passive) <- c("place after move","place before move")
b b_active b_passive
(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 b_passive
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 inverse(b) * inverse(a) == inverse(a*b) # note b precedes a on LHS
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
Then we can express g
in terms of permutation matrices:
pg <- perm_matrix(g) pg
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
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 ph <- perm_matrix(h) dimnames(ph) <- list(place_before_move=1:6,place_after_move=1:6) ph
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
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.
Any scripts or data that you put into this service are public.
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.