Recently, I asked a question about action of a permutation group on a set here. Let me summarize it.

Let $\mathrm{S}_{m}$ be the set of all permutations of $\{1,2,\cdots,m\}$. Then $(\mathrm{S}_{m},\circ)$ is a group where $\circ$ is function composition operation.

Show that $$\mathrm{S}_{m} \times \mathbb{N}^{m} \rightarrow \mathbb{N}^{m}, \quad(\sigma, x) \mapsto \sigma \cdot x := \left(x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(m)}\right)$$ defines an action of $\mathrm{S}_{m}$ on $\mathbb{N}^{m}$.

For $\sigma , \tau \in \mathrm{S}_{m}$ and $x \in \mathbb{N}^{m}$, I try to prove $$\sigma \cdot (\tau \cdot x) = (\sigma \circ \tau) \cdot x$$

In this answer, Wuestenfux presents the following proof:

$$\begin{aligned} \sigma \tau \cdot x &= (x_{(\sigma\tau)^{-1}(1)}, \ldots, x_{(\sigma\tau)^{-1}(n)})\\ &= (x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) \\ &= \tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})\\ &=\sigma\cdot(\tau \cdot x) \end{aligned}$$

Here he writes $\sigma \tau$ for $\sigma \circ \tau$.

In his proof, I think $(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = \tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})$ is wrong. Instead, it should be $(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = \sigma \cdot (x_{\tau^{-1}(1)}, \ldots, x_{\tau^{-1}(n)})$.

My reasoning:

  1. In $(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)})$, the flow of input-output is $\sigma \longrightarrow \tau \longrightarrow x$, whereas it is $\tau \longrightarrow \sigma \longrightarrow x$ in $\tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})$. As such, I feel that it is counter-intuitive to have $(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = \tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})$.

  2. It's clear that $\sigma \cdot x = x \circ \sigma^{-1}$. Then $$\begin{aligned} \sigma \tau \cdot x &= x \circ (\sigma \circ \tau)^{-1}\\ &= x \circ (\tau^{-1} \circ \sigma^{-1})\\ &= (x \circ \tau^{-1}) \circ \sigma^{-1}\\ &= \sigma \cdot (x \circ \tau^{-1})\\ &= \sigma \cdot (x_{\tau^{-1}(1)}, \ldots, x_{\tau^{-1}(n)}) \end{aligned}$$

Please check if my reasoning is correct or not!

  • $\begingroup$ See example 2.5 and 2.6 here. $\endgroup$ – Thomas Shelby Jun 1 at 4:01
  • 1
    $\begingroup$ Hi @ThomasShelby. Thank you so much for your link! It really helps me understand what is going on behind the notation. I have posted my reasoning as an answer below. Could you please have a check on it? $\endgroup$ – Le Anh Dung Jun 1 at 9:32
  • $\begingroup$ Thank you so much for your kindness @ThomasShelby :v $\endgroup$ – Le Anh Dung Jun 1 at 13:18

I found that the blue argument is not correct in @Wuestenfux's proof.

$$\begin{aligned} \sigma \tau \cdot x &= (x_{(\sigma\tau)^{-1}(1)}, \ldots, x_{(\sigma\tau)^{-1}(n)})\\ &= \color{blue}{(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)})} \\ &= \color{blue}{\tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})}\\ &= \sigma\cdot(\tau \cdot x) \end{aligned}$$

We have

$$\begin{aligned} \sigma \cdot (\tau \cdot x) &= \color{blue}{\sigma \cdot (x_{\tau^{-1}(1)}, \ldots, x_{\tau^{-1}(n)})} \\ &= \sigma \cdot (d_1, \ldots, d_n) \quad \text{where} \quad d_i = x_{\tau^{-1}(i)} \\ &= (d_{\sigma^{-1} (1)}, \ldots, d_{\sigma^{-1} (n)}) \\ &= (x_{\tau^{-1} (\sigma^{-1}(1))}, \ldots, x_{\tau^{-1} (\sigma^{-1} (n))})\\ &= \color{blue}{(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)})} \end{aligned}$$

It follows that $$(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = \sigma \cdot (x_{\tau^{-1}(1)}, \ldots, x_{\tau^{-1}(n)})$$ and NOT that $$(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = \tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})$$

  • $\begingroup$ Seems correct. I wasn't convinced either. $\endgroup$ – Wuestenfux Jun 1 at 12:34
  • $\begingroup$ Hi @Wuestenfux, I quite don't understand by "I wasn't convinced either". Did you mean that you are not convinced by my reasoning? $\endgroup$ – Le Anh Dung Jun 1 at 12:37
  • $\begingroup$ Just my reasoning. I had to do a substitution. $\endgroup$ – Wuestenfux Jun 1 at 12:39
  • $\begingroup$ Thank you so much for your interest in my question @Wuestenfux :) $\endgroup$ – Le Anh Dung Jun 1 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.