Factorización de Permutaciones

Factorization of Permutations

Presentamos la implementación de un programa que permite hallar una factorización de los elementos del grupo simétrico S_n, usando el número mínimo de transposiciones simples. Dicha implementación se realizó en el sistema computacional CoCoA. 

INTRODUCCIÓN

El grupo simétrico S_npuede definirse como el conjunto de todas las biyecciones sobre el conjunto { 1 ,2, …,n} con la operación usual de composición de funciones. Los elementos de S_n pueden representarse por medio de ciclos. Por ejemplo, sobre el conjunto { 1,2, … ,5} la función que envía

1 → 5

2 → 1

3 → 2

4 → 3

5 → 4

se puede representar en un ciclo como (1,5,4,3,2). En general un k-ciclo (c₁, … ,c_k) representa la función

(c₁ → c₂)

(c₂ → c₃)

   •    •

   •    •

   •    •

(c_k → c₁)

Los elementos de S_n se llaman permutaciones y también se pueden escribir en notación de una línea. De esta forma, si w ∈ S_n escribimos w = [w₁ ,w₂ , ••• ,w_n] para indicar que w (i) = w_i para todo i =1, … ,n. En el ejemplo anterior, la notación en una línea de la permutación (1,5,4,3,2) es [5,1,2,3,4]. Una transposición es un 2-ciclo y una transposición simple es una transposición que intercambia dos elementos consecutivos. Las transposiciones simples se escriben como S_k= (k,k +1) para k= 1, … ,n - l. Es bien conocido que el número de elementos de S_n es n! y que toda permutación se puede factorizar como un producto de ciclos disyuntos. Además, todo ciclo se puede factorizar como producto de transposiciones simples y por lo tanto, las transposiciones simples generan a S_n. La descomposición anterior en ciclos y transposiciones simples no es única. Sin embargo, el número mínimo de transposiciones simples necesarias para factorizar una permutación  w ∈ S_n se llama la longitud de w·y se denota por l(w).

Ejemplo 1. Para la permutación (1,5,4,3,2) tenemos que

(1,5,4,3,2) = (4,5)(3,4)(2,3)(1,2)

    = S₄S₃S₂S₁

​Note que el producto se hace de derecha a izquierda, en la forma usual como se componen funciones. Como se dijo antes, la descomposición en transposiciones no es única y se tiene que

S_iS_i+iS_i = S_i+lS_iS_i+l

S_iS_j = S_jS_i Si | i — j | > 1.