How does a permutation act on a string?

Question

Is there a conventional way to have a permutation act on a list of objects? It seems like there are two possible ways, one being the inverse of the other.

Suppose I have a permutation $\sigma \in S_4$ which is concretely specified as a function from the set $S = \{1,2,3,4\}$ to itself. Specifically,

$$\begin{array}{c|cccc} i & 1 & 2 & 3 & 4 \\ \hline \sigma(i) & 4 & 3 & 1 & 2 \end{array}$$

Say I want to permute the string "STAR" by $\sigma$. One way to do it would be to send the letter at position $i$ to position $\sigma(i)$ in the result, giving "ARTS". Another way to do it would be to populate the $i^{\text{th}}$ entry of the result using the $\sigma(i)^{\text{th}}$ entry of the original. That would give "RAST".

The first one seems more correct, but the second is more appealing because the string "1234" permutes to "4312", which you read directly off the table.

EDIT: I realize this is equivalent to asking if a permutation matrix should have ones in entries $a_{i,\sigma(i)}$ or $a_{\sigma(i),i}$.

Answer 1

Both actions are correct: one is a left action and the other is a right action.

[See https://en.wikipedia.org/wiki/Group_action_(mathematics)]

For the first action: to a permutation $\sigma$ and a string $x$, we associate a string $\sigma \cdot x$, defined by $(\sigma \cdot x)_{\sigma(i)} = x_i$ ("letter at position $i$ is sent to position $\sigma(i)$"), for all indices $i$ or, equivalently, $(\sigma \cdot x)_j = x_{\sigma^{-1}(j)}$ for all indices $j$. That is a left action, since for two permutations $\sigma$ and $\tau$, we have

$$[\sigma\cdot (\tau\cdot x))]_i = (\tau\cdot x)_{\sigma^{-1}(i)} = x_{\tau^{-1}(\sigma^{-1}(i))}= x_{(\sigma\tau)^{-1}(i)} = [(\sigma \tau)\cdot x]_i,$$ hence $$\sigma\cdot (\tau\cdot x) = (\sigma \tau)\cdot x.$$ Applying (i.e. "multiplying" by) $\tau$ and then $\sigma$ is the same as applying $\sigma\tau$. That is how multiplication to the left works, hence the term ''left action.''

For the second action: to a permutation $\sigma$ and a string $x$, we associate a string $x\star \sigma$, defined by $(x\star \sigma)_i = x_{\sigma(i)}$ ("$i^{th}$ entry of the result is the $\sigma(i)^{th}$ entry of the original."). That is a right action, since for two permutations $\sigma$ and $\tau$, we have $$[(x\star \sigma)\star \tau]_i = [x\star\sigma]_{\tau(i)}= x_{\sigma(\tau(i))} = x_{(\sigma\tau)(i)} = [x\star (\sigma\tau)]_i,$$ hence $$(x\star \sigma)\star \tau = x\star(\sigma\tau).$$

Applying (i.e. "multiplying" by) $\sigma$ and then $\tau$ is the same as applying $\sigma\tau$. That is how multiplication to the right works, hence the term ''right action.''

The two actions are indeed related by $$(\sigma \cdot x)\star \sigma = x = \sigma \cdot (x\star \sigma),$$ because $$x\star \sigma = \sigma^{-1}\cdot x.$$