6
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ For each $i\in S$, $i$ should go to $\sigma(i)$. Since the characters in the string are usually mapped to their indices, a permutation of the string is a permutation on its index set. Therefore, I would say your first way is correct. $\endgroup$ – John Douma May 14 at 23:55
  • 3
    $\begingroup$ Both are correct: one is a left action and the other is a right action. $\endgroup$ – Catalin Zara May 15 at 0:17
  • $\begingroup$ @CatalinZara could you expand this into an answer? $\endgroup$ – Q the Platypus May 15 at 1:46
10
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ Very well explained. Failing to recognize that the two possible conventions lead to actions on opposite sides can result in much confusion, as in this older question: math.stackexchange.com/questions/1373136 $\endgroup$ – Ted May 15 at 3:07

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.