¿Qué es una explicación intuitiva del signo de una permutación?

Answer 1

Una permutación es otro nombre para barajar algo. Una forma de dibujar una permutación es así:
Comenzamos con la fila superior, movemos las cosas según las flechas y terminamos con la fila inferior. Si comenzaste con los números 1,2,3,4 en los círculos, luego de aplicar esta permutación, tendrías 4,1,3,2.

Algunas de las flechas se cruzarán entre sí. En esta permutación, hay cuatro cruces:

Llamamos a la permutación par o impar dependiendo del número de cruces que tenga: un número par de cruces es una permutación par y un número impar de cruces es una permutación impar. Esta permutación es pareja. (Asegúrese de no tener tres o más líneas que se crucen todas en el mismo punto cuando cuente los cruces).

Esto también se llama el signo de una permutación: se dice que las permutaciones impares tienen un signo negativo e incluso las permutaciones un signo positivo. Finalmente, el carácter par / impar también se llama paridad de una permutación.

Eso es todo por la definición. En el resto de la respuesta, daré un par de datos clave sobre el signo de una permutación.

El primero es que cada vez que cambia dos círculos (llamado transposición), cambia el signo de la permutación. Si fue extraño se vuelve par y viceversa.

Veamos esto con un ejemplo. Cambiaremos las dos primeras flechas. Estoy redibujando la imagen original con esas flechas verdes.

Cuando los cambiamos, se ve así:

El número de cruces ha pasado de cuatro a cinco, por lo que el signo ha cambiado de positivo a negativo.

Es fácil ver de dónde vino el cruce adicional: las flechas verdes no se cruzaron para empezar, pero al cambiarlas las cruzamos unas sobre otras.

En cuanto a las líneas rojas, solo hay unas pocas posibilidades de cómo se ve una línea roja particular y las dos líneas verdes. Si los dibuja todos, verá que una línea roja dada no puede cambiar su número de cruces o subir o bajar en dos.

Debido a que los cruces verde / verde cambiarán en uno y los cruces rojo / verde cambiarán en un número par, el signo de la permutación cambia.

Puede usar transposiciones para deshacer una permutación, lo que se denomina factorización. Por ejemplo, nuestra permutación original se puede factorizar en dos transposiciones: cambiar las flechas primera y última, luego cambiar las flechas segunda y cuarta. Eso lo llevará de regreso a tener todas las flechas apuntando hacia abajo para que no pase nada, lo que se llama permutación de identidad.

Nuestra permutación fue pareja y tomó un número par de transposiciones para resolverla. Es fácil ver que siempre es así. Cada transposición cambia el signo, así que si comienzas con pares y haces muchas transposiciones, irás par-impar-par-impar … Necesitas cambiar un número par de veces porque tu objetivo, la identidad, es par. Del mismo modo, las permutaciones impares necesitan un número impar de transposiciones para ser resueltas.

Ya mencionaste un lugar en el que esto es importante: en los determinantes. Cuando cambia dos filas o columnas de una matriz, multiplica el determinante por -1. El signo de un determinante cambia de la misma manera que el signo de una permutación.

Otra aplicación está en un cubo de Rubik. Cada vez que tuerces una cara del cubo de Rubik, es una permutación uniforme. Eso significa que no hay forma de resolver una permutación extraña. Saque dos piezas del cubo y cámbielas y nunca podrá resolverlo sin volver a sacar las piezas.

Puede usar estos conceptos básicos para mostrar que dos o dos permutaciones impares se suman para hacer una permutación par, y una permutación par más una impar se agrega para hacer una permutación impar. Esto es igual que con los números. (Agregar permutaciones significa hacer una, luego hacer la siguiente al resultado para obtener una permutación del producto final).

Además, para los elementos [math] n [/ math], hay permutaciones [math] n! [/ Math]. La mitad de ellos son impares y la otra mitad son pares (excepto [math] n = 1 [/ math], donde solo existe la identidad). Probablemente pueda pensar en una prueba de esto buscando una biyección entre permutaciones pares e impares.

Esta respuesta es una reescritura de una antigua publicación de blog que escribí sobre ella aquí: Respuesta: Paridad de permutaciones.

Answer 2

El grupo simétrico en n letras, o, en otras palabras, el grupo de todas las permutaciones, tiene precisamente una representación unidimensional no trivial, y esta representación es precisamente el signo de la permutación.

¿Qué significa esto? Bueno, considere escribir la tabla de multiplicar para todas las permutaciones de n elementos. Por ejemplo, aquí está la tabla de multiplicar cuando n = 3 :

Ahora veamos si podemos reemplazar estas permutaciones con números para obtener una tabla de multiplicación real. Por supuesto, no podemos hacer esto si queremos enviar cada permutación a un número diferente, porque la composición de las permutaciones no es conmutativa, pero la multiplicación de números es conmutativa. Por lo tanto, debemos permitir el envío de más de una permutación al mismo número.

La forma más fácil de hacer esto es bastante estúpida:

Si solo enviamos todo a uno, entonces todo funciona porque una vez uno es uno. Esto se llama la representación trivial .

Resulta que hay otra forma de hacerlo. Exactamente uno al otro, de hecho.
Si enviamos cada permutación a su signo, obtenemos una representación unidimensional más.

(También puede enviar todo a cero, pero eso no cuenta como una representación por razones técnicas).

¿Por qué se llaman estas representaciones unidimensionales ? Porque hemos reemplazado cada permutación con un número, en otras palabras, con una matriz uno por uno . Una representación bidimensional sería aquella en la que reemplazamos cada número por un dos por dos matriz, y así sucesivamente.

¿Por qué nos importa? Bueno, los grupos solos son inútiles. Solo nos importan los grupos en la medida en que actúan sobre las cosas. Las permutaciones, por ejemplo, permutan los elementos de un conjunto discreto.

Al comprender las representaciones de un grupo, entendemos cómo puede actuar en espacios vectoriales. Y casi cada acción de un grupo sobre cualquier cosa puede entenderse como una acción en un espacio vectorial, tal vez en un espacio tangente, por ejemplo, o un espacio de funciones. Y las representaciones unidimensionales son aún más especiales, esencialmente porque los escalares pueden actuar sobre casi cualquier cosa , mientras que las matrices tienen que actuar sobre vectores de una dimensión particular.

O, para el caso, puede usarlos como invariantes para mostrar que dos cosas no son iguales, como la respuesta de Mark Eichenlaub a ¿Qué es una explicación intuitiva del signo de una permutación? muestra que cualquier configuración alcanzable del cubo de Rubik es necesariamente diferente de ciertas configuraciones que podría obtener al desmontar el cubo y volver a ensamblarlo.

Answer 3

Piense en una permutación como un ordenamiento de enteros 1, … n. Ahora ordene esa lista ordenada utilizando solo intercambios por pares. Si el número de intercambios que usó fue par, entonces tiene una permutación par. De lo contrario, tiene una permutación extraña.

Por ejemplo, si nuestro pedido es [1, 3, 4, 2], entonces podemos ordenarlo mediante la siguiente secuencia de intercambios:
intercambia los dos últimos elementos para obtener: [1,3,2,4]
intercambia los dos elementos del medio para obtener: [1,2,3,4]
Y como utilizamos dos intercambios, el signo de nuestra permutación es incluso 🙂

Answer 4

Una permutación puede escribirse únicamente como un producto de ciclos disjuntos, módulo de la ordenación de los ciclos. Pero hay muchas formas de escribir una permutación como producto de transposiciones. El signo de una permutación implica que el número de tales transposiciones modulo [math] 2 [/ math], es fijo.

Para mostrar que el signo de una permutación es invariante con respecto a cómo se expresa una permutación en términos de número de transposiciones, consideraremos una cantidad ( ver la ecuación 1 a continuación ), que es fácil de ver como una invariante que no mostraremos para mantener su invariancia, si el signo de una permutación no es invariante.

Considere, una permutación [matemática] \ sigma [/ matemática] en [matemática] \ {1,2, \ puntos, n \} [/ matemática] representada por [matemática] \ {i_1, i_2 \ dots, i_n \} [ /matemáticas] . Es decir, [math] 1 [/ math] está mapeado a [math] i_1, 2 [/ math] está mapeado a [math] i_2 [/ math] por [math] \ sigma [/ math] y así sucesivamente. Asociar con esta permutación, la cantidad ( ecuación 1 a continuación )

[matemáticas] \ Delta (i_1, i_2, \ dots, i_n) = \ prod_ {1 <= j

Del mismo modo, con el conjunto [matemáticas] \ {1, 2, \ puntos, n \} [/ matemáticas] podemos asociar la cantidad ( ecuación 2 )

[matemática] \ Delta (1, 2, \ puntos, n) = \ prod_ {1 <= i

Ahora podemos ver que si la permutación [math] \ sigma [/ math] se escribe como un producto de transposiciones [math] r [/ math] [math] \ sigma_1 \ sigma_2 \ dots \ sigma_r [/ math], entonces aplica estas las transposiciones en el orden inverso que es [math] \ sigma_r \ dots \ sigma_2 \ sigma_1 [/ math] invertirá la permutación [math] \ sigma [/ math] y volveremos al conjunto ordenado original [math] \ { 1,2 \ puntos n \} [/ matemáticas].

Deje que [math] (i_c, i_d) [/ math] sea la transposición [math] \ sigma_1 [/ math]. Aplicando esta transposición a [math] \ sigma [/ math] obtendremos un nuevo orden [math] \ {j_1, j_2 \ dots j_n \} [/ math] derivado de [math] \ {i_1, i_2, \ dots i_n \} [/ matemáticas] y

[matemática] \ Delta (j_1, j_2, \ dots j_n) = (-1) \ Delta (i_1, i_2, \ dots i_n) [/ math]

Aplicando todas las transposiciones r que vemos ( ecuación 3 )

[matemáticas] \ Delta (1, 2, \ puntos, n) = (-1) ^ r \ Delta (i_1, i_2, \ puntos, i_n) [/ matemáticas]

Del mismo modo, si [math] \ sigma [/ math] puede expresarse como el producto de las transposiciones [math] s [/ math] aplicando todas estas transposiciones [math] s [/ math] a la inversa, obtendremos ( ecuación 4 )

[matemáticas] \ Delta (1, 2, \ puntos, n) = (-1) ^ s \ Delta (i_1, i_2, \ puntos, i_n) [/ matemáticas]

y si [math] r [/ math] no es congruente con [math] s [/ math] modulo [math] 2 [/ math], es decir, si uno es impar y el otro es par, obtendremos de las ecuaciones [ matemáticas] 3 [/ matemáticas] y [matemáticas] 4 [/ matemáticas],

[matemáticas] \ Delta (1, 2, \ puntos, n) = (-1) \ Delta (1, 2, \ puntos, n) [/ matemáticas]

lo que hará

[matemáticas] \ Delta (1, 2, \ puntos, n) = 0 [/ matemáticas]

lo cual es una contradicción, ya que [math] \ Delta (1, 2, \ dots, n) [/ math] es producto de términos distintos de cero y nunca puede ser [math] 0 [/ math].

Esto significa que [math] r [/ math] es congruente con [math] s [/ math] modulo [math] 2 [/ math], o en otras palabras, la paridad del número de transposiciones requeridas para expresar una permutación dada es fija.

La prueba anterior está adaptada del libro Algebra de Hungerford.

Answer 5

Aquí hay una intuición geométrica:

Para una permutación [math] \ pi \ in \ mathcal {S} _n [/ math], considere la matriz [math] A \ in \ mathbb {R} ^ {n \ times n} [/ math] que tiene un 1 en cada posición [matemáticas] (i, \ pi (i)) [/ matemáticas] y ceros en otro lugar. Vista como una transformación lineal, esta matriz permuta los ejes de [math] \ mathbb {R} ^ n [/ math].

Ahora: imagine que tiene una “imagen” que ocupa el cubo de la unidad de [math] \ mathbb {R} ^ n [/ math]. (Para [matemáticas] n = 2 [/ matemáticas], piense en una imagen plana ordinaria; para [matemáticas] n = 3 [/ matemáticas], una escultura, etc.)

Ahora imagine lo que sucede si golpea esa imagen con su permutación [math] \ pi [/ math]. Si [math] \ sgn (\ pi) = +1 [/ math], cualquier persona diestra en la imagen seguirá siendo diestra en la imagen permutada. Pero si [math] \ sgn (\ pi) = -1 [/ math], se convertirán en zurdos.