TAOCP 1.3.3 Exercise 3

The product of the two given permutations is computed by applying the right-hand permutation first, followed by the left-hand permutation.

taocpmathematicsalgorithmsvolume-1simple

Section 1.3.3: Applications to Permutations

Exercise 3. [03] Compute the product

$$ \begin{pmatrix} a & b & c & d & e & f \ b & d & c & a & f & e \end{pmatrix} \times \begin{pmatrix} a & b & c & d & e & f \ c & d & f & b & e & a \end{pmatrix}, $$

and express the answer in two-line notation. (Compare with Eq. (4).)

Verified: yes
Solve time: 1m19s

The product of the two given permutations is computed by applying the right-hand permutation first, followed by the left-hand permutation. Denote the permutations by

$$ \pi_1 = \begin{pmatrix} a & b & c & d & e & f \ b & d & c & a & f & e \end{pmatrix},\qquad \pi_2 = \begin{pmatrix} a & b & c & d & e & f \ c & d & f & b & e & a \end{pmatrix}. $$

We compute $\pi_1 \times \pi_2$ by tracing the image of each element under $\pi_2$ and then $\pi_1$:

  • $a \mapsto \pi_2(a) = c$, then $\pi_1(c) = c$, so $a \mapsto c$.
  • $b \mapsto \pi_2(b) = d$, then $\pi_1(d) = a$, so $b \mapsto a$.
  • $c \mapsto \pi_2(c) = f$, then $\pi_1(f) = e$, so $c \mapsto e$.
  • $d \mapsto \pi_2(d) = b$, then $\pi_1(b) = d$, so $d \mapsto d$.
  • $e \mapsto \pi_2(e) = e$, then $\pi_1(e) = f$, so $e \mapsto f$.
  • $f \mapsto \pi_2(f) = a$, then $\pi_1(a) = b$, so $f \mapsto b$.

Collecting these images, the resulting permutation in two-line notation is

$$ \begin{pmatrix} a & b & c & d & e & f \ c & a & e & d & f & b \end{pmatrix}. $$

This coincides with the computation in equation (4).

$\boxed{\begin{pmatrix}a & b & c & d & e & f \ c & a & e & d & f & b \end{pmatrix}}$