Por: Novoa Fernando
|
Fecha: 01/01/2022
Presentamos la implementación de un programa que permite hallar una factorización de los elementos del grupo simétrico Sn, usando el número mínimo de transposiciones simples. Dicha implementación se realizó en el sistema computacional CoCoA. INTRODUCCIÓNEl grupo simétrico Snpuede 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 Sn pueden representarse por medio de ciclos. Por ejemplo, sobre el conjunto { 1,2,
,5} la función que envía1 → 52 → 13 → 24 → 35 → 4se puede representar en un ciclo como (1,5,4,3,2). En general un k-ciclo (c1,
,ck) representa la función(c1 → c2)(c2 → c3) (ck → c1)Los elementos de Sn se llaman permutaciones y también se pueden escribir en notación de una línea. De esta forma, si w ∈ Sn escribimos w = [w1 ,w2 , ,wn] para indicar que w (i) = wi 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 Sk= (k,k +1) para k= 1,
,n - l. Es bien conocido que el número de elementos de Sn 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 Sn. 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 ∈ Sn 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) = S4S3S2S1Note 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 queSiSi+iSi = Si+lSiSi+lSiSj = SjSi Si | i j | > 1.
Fuente:
Revista Virtual Pro
Tipo de contenido:
Otros
