¿Cómo actúa una permutación sobre una cadena?

Question

¿Existe una forma convencional de hacer que una permutación actúe sobre una lista de objetos? Parece que hay dos formas posibles, siendo una la inversa de la otra.

Supongamos que tengo una permutación $\sigma \in S_4$ que se especifica concretamente como una función del conjunto $S = \{1,2,3,4\}$ a sí mismo. Específicamente,

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

Digamos que quiero permutar la cadena "STAR" por $\sigma$ . Una forma de hacerlo sería enviar la carta en la posición $i$ a la posición $\sigma(i)$ en el resultado, dando "ARTS". Otra forma de hacerlo sería rellenar el $i^{\text{th}}$ entrada del resultado utilizando el $\sigma(i)^{\text{th}}$ entrada del original. Eso daría "RAST".

La primera parece más correcta, pero la segunda es más atractiva porque la cadena "1234" permuta a "4312", que se lee directamente en la tabla.

EDIT: Me doy cuenta de que esto es equivalente a preguntar si una matriz de permutación debe tener unos en las entradas $a_{i,\sigma(i)}$ o $a_{\sigma(i),i}$ .

Answer 1

Ambas acciones son correctas: una es una acción de izquierda y la otra es una acción de derecha.

[Ver [https://en.wikipedia.org/wiki/Group\_action\_(matemáticas)\]](https://en.wikipedia.org/wiki/Group_action_(mathematics)])

Para la primera acción: a una permutación $\sigma$ y una cadena $x$ asociamos una cadena $\sigma \cdot x$ definido por $(\sigma \cdot x)_{\sigma(i)} = x_i$ ("letra en la posición $i$ se envía a la posición $\sigma(i)$ "), para todos los índices $i$ o, de forma equivalente, $(\sigma \cdot x)_j = x_{\sigma^{-1}(j)}$ para todos los índices $j$ . Se trata de una acción de izquierda, ya que para dos permutaciones $\sigma$ y $\tau$ tenemos

$$[\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,$$ por lo que $$\sigma\cdot (\tau\cdot x) = (\sigma \tau)\cdot x.$$ Aplicando (es decir, "multiplicando" por) $\tau$ y luego $\sigma$ es lo mismo que aplicar $\sigma\tau$ . Así es como funciona la multiplicación a la izquierda, de ahí el término ''acción a la izquierda''.

Para la segunda acción: a una permutación $\sigma$ y una cadena $x$ asociamos una cadena $x\star \sigma$ definido por $(x\star \sigma)_i = x_{\sigma(i)}$ (" $i^{th}$ La entrada del resultado es el $\sigma(i)^{th}$ entrada del original"). Se trata de una acción correcta, ya que para dos permutaciones $\sigma$ y $\tau$ tenemos $$[(x\star \sigma)\star \tau]_i = [x\star\sigma]_{\tau(i)}= x_{\sigma(\tau(i))} = x_{(\sigma\tau)(i)} = [x\star (\sigma\tau)]_i,$$ por lo que $$(x\star \sigma)\star \tau = x\star(\sigma\tau).$$

Aplicando (es decir, "multiplicando" por) $\sigma$ y luego $\tau$ es lo mismo que aplicar $\sigma\tau$ . Así es como funciona la multiplicación a la derecha, de ahí el término ''acción correcta''.

Las dos acciones están efectivamente relacionadas por $$(\sigma \cdot x)\star \sigma = x = \sigma \cdot (x\star \sigma),$$ porque $$x\star \sigma = \sigma^{-1}\cdot x.$$