Grupos de Permutação e Ciclos: Exercícios e Propriedades

n elementos Isso não deve causar problemas pois como In Im quando m n então podemos ver uma permutação de Sn como uma permutação de Sm que fixa os naturais maiores que n Assim a permutação 1 4 por exemplo pode ser considerada em ambos S5 e S8 mas em tese são permutações distintas S5 1 4 1 2 3 4 5 4 2 3 1 5 1 S8 1 4 1 2 3 4 5 6 7 8 4 2 3 1 5 6 7 8 2 A vantagem dos kciclos é que eles podem ser denotados de maneira mais concisa Se f é um kciclo como na definição denotamos f a1 a2 ak Como f atua como a identidade nos demais elementos estes podem ser omitidos da notação Exercício 1 Seja f um kciclo dado por a1 a2 ak Verifique que f a2 a3 ak a1 ak a1 ak1 Essa propriedade da notação junto com a Figura 1 justifica o uso do termo ciclo para se referir a tais permutações Grupos de Permutação Vinicius Martins Teodosio Rocha Observações Atualizado 9 de agosto de 2022 Sugestões ou erros viniciusrochaifpbedubr Cada erro encontrado no texto ou nos exercícios vale 02 de ponto 2 pontos na escala de 0 a 100 para a avaliação seguinte Apenas para o primeiro aluno que encontrar 1 4 32 4 1 2 3 14 Como f84 4 então o ciclo iniciando em 4 deve terminar no próprio 4 Nossa permutação portanto é 2 3 14 Pela definição e como foi visto no Exercício 2 4 Id Assim omitimos o 4 e escrevemos apenas f8 2 3 1 afinal ninguém escreve 6 1 no lugar de 0 ou 2 0 ao invés de 2 Como vimos no Exercício 4 nem sempre ocorre o produto de dois ciclos resultarem em um ciclo A ideia é continuar o mesmo processo que fizemos com o 4 no exemplo acima Vejamos um exemplo Exemplo 2 Seja f 1 4 3 e g 1 4 2 Iniciando pelo 1 temos que fg1 f4 3 prosseguindo o ciclo fg3 f3 1 Resultando no ciclo 1 3 prosseguimos com os elementos que não estão no primeiro ciclo tome 2 por exemplo temos que fg2 f1 4 e fg4 f2 2 resultando no ciclo 2 4 Assim temos que 1 4 31 4 2 1 32 4 Note que se iniciássemos com 2 por exemplo o resultado seria ligeiramente diferente apenas na notação obviamente a permutação seria a mesma faça isso Uma explicação para isso está no exercício a seguir Antes precisamos de uma definição dados ciclos f a1 a2 ak e g b1 b2 bl são discos disjuntos se ai bj para qualquer i 1 k e j 1 l Exercício 7 Seja f uma permutação escrita como produto de ciclos de comprimento l e k prove que ordf mmclk O tipo de ciclo mais simples é o 2ciclo a1 a2 que apenas troca a posição dos elementos a1 e a2 tais permutações são chamadas de transposições Um fato interessante e muito importante é que toda permutação pode ser escrita como um produto de transposições 1 Ao converter uma permutação da forma matricial para produtos de ciclos já vimos como escrever uma permutação qualquer como produto de ciclos Basta verificar portanto que todo ciclo pode ser escrito como um produto de transposições Esse fato segue de identidade a1 a2 ak a1 aka1 ak1 a1 a3a1 a2 Para se convencer disso note que ao analisar o efeito da permutação à direita em determinado ai notese que ai aparece a primeira e única vez na transposição a1 ai a1 ak ai1a1 ai a1 a2 Assim ai a1 proseguindo lembrese da direita para a esquerda temos que a transposição à esquerda faz a1 ai1 como ai1 não aparece mais temos que ai ai1 como esperado Exercício 8 Escreva as permutações a seguir como produto de transposições Você consegue escrever algumas delas como produto de transposições de formas diferentes a 1 2 3 4 5 b 2 31 2 4 c 4 31 5 d 1 34 2 32 4 Exercício 9 Liste todos os elementos de S3 como produtos de transposições Seja f a1 a2 ak um kciclo Pelo que observamos f pode ser escrito como um produto de k 1 transposições Vale notar que essa representação como produto de transposições não é única Por exemplo 3 22 41 31 2 1 4 3 1 31 4 No entanto note que essas duas representações têm a mesma quantidade de transposições mod 2 isto é a paridade é a mesma O teorema a seguir garante que isso ocorre sempre Teorema 1 Se duas representações de uma permutação como produto de transposições têm r e l transposições então r e l tem a mesma paridade Demonstração Em breve À luz do teorema acima se f Sn podemos definir a paridade de f como a paridade da quantidade de transposições em qualquer representação de f em transposições Se f for um kciclo então a paridade de f será a paridade de k 1 Por exemplo Id é uma permutação par já que é o produto de zero transposições ou se preferir como uma transposição e sua própria inversa Id a1 a2a1 a2 Já uma única transposição é uma permutação ímpar e um 3ciclo a1 a2 a3 a1 a3a1 a2 é par etc É conveniente expressar essa propriedade através de uma função Definição 2 Seja f uma permutação definimos o sinal ou paridade de f como sgnf 1 se f é par 1 se f é ímpar Em outras palavras seja f escrito como um produto de transposições como f σ1 σk então sgnf 1k Exemplo 4 Nesse exemplo discutimos outra forma de se calcular sgnf Toda permutação f Sn induz um reordenamento da sequência 1 2 n Consideramos todos os pares de elementos i j 1 i j n e contamos a quantidade de vezes em que há inversões isto é quando fj fi Chamamos esse número de Nf e é possível mas não trivial provar que sgnf 1Nf Vejamos um exemplo suponha que f 1 2 3 4 2 4 1 3 Há 6 pares i j com as condições desejadas destacamos onde ocorre uma inversão 12 7 24 13 7 21 inversão 14 7 23 23 7 41 inversão 24 7 43 inversão 34 7 13 Portanto há 3 inversões logo sgnf 13 1 e f é ímpar como já esperávamos uma vez que f é um 4ciclo 7 Exemplo 5 Ainda uma outra forma de definir a paridade Sejam x1 x2 xn variáveis independentes Considere o polinômio de Vandermonde Pnx1 xn ij xi xj Por exemplo P2x1 x2 x1 x2 P3x1 x2 x3 x1 x2x1 x3x2 x3 P4x1 x2 x3 x4 x1 x2x1 x3x1 x4x2 x3x2 x4x3 x4 Dada uma permutação f Sn definimos o polinômio P f n por P f nx1 xn ij x f i x f j Assim se f é a transposição 1 3 em S3 por exemplo então P f 3 x1 x2 x3 x3 x2x3 x1x2 x1 Se f 2 41 3 em S4 então P f 4 x1 x2 x3 x4 x3 x4x3 x1x3 x2x4 x1x4 x2x1 x2 Dos exemplo acima observe que a ação de f no polinômio Pn é apenas trocar os fatores lineares xi xj de posição o que não muda o polinômio e para certos fatores lineares trocar a posição do xi e xj de forma que podemos ter um fator da forma xj xi i j Essa última ação de fato muda o polinômio mas apenas por um fator 1 já que xj xi xi xj Como os polinômios Pn e P f n possuem os mesmos fatores lineares a menos de uma mudança no sinal temos que o quociente entre tais polinômios é 1 Na verdade temos que sgn f Pnx1 xn P f nx1 xn Esse fato pode ser facilmente verificado observando que as trocas de sinal acontecem justamente nos fatores em que xi xj com i j para os quais f j f i isto é quando ocorre uma inversão portanto há 1N f mudanças de sinal o que coincide com o sgn f como discutido no exemplo anterior Observação O polinômio de Vandermonde é bastante importante em álgebra Ele aparece no determinante de uma matriz com muitas aplicações chamada matriz de Vandermonde det 1 1 1 x1 x2 xn x2 1 x2 2 x2 n x3 1 x3 2 x3 n xn1 1 xn1 2 xn1 n 1 nn1 2 ij xi xj 8 A demonstração desse teorema não é muito simples e ocuparia algumas páginas então vamos ignorála por enquanto Alguns textos definem o polinômio de Vander monde trocando a ordem do xi e xj nos fatores lineares ij xj xi Isso faz com que para certos valores de n o sinal mude em comparação com a nossa definição e como consequência na fórmula acima o fator 1 nn1 2 desaparece isto é detxi1 j ijxj xi Portanto ao pesquisar sobre esse assunto certifiquese que sabe qual das definições o autor está usando Observe que essa definição alter nativa não muda o que discutimos sobre o sinal uma vez que estamos considerando o quociente de Pn por P f n como a mudança de sinal que ocorreria em Pn também ocorre em P f n o sinal do quociente é o mesmo em ambas as definições Exercício 12 Sejam α1 α2 as raízes de px ax2 bx c e b2 4ac o seu discrimi nante Prove que aP2α1 α22 a2α1 α22 O exercício acima motiva a definição de discriminante para um polinômio de grau qualquer Definição 3 Seja px um polinômio de grau n com coeficientes em um corpo k qualquer k R por exemplo Suponha que o coeficiente líder de px isto é o coeficiente que multiplica xn seja an e tome α1 αn as raízes não necessariamente distintas de px Definimos o discriminante de px como Discp a2n2 n ij αi αj2 a2n2 n Pnα1 αn2 Em particular se o polinômio for mônico isto é an 1 o discriminante é simples mente o quadrado do polinômio de Vandermonde aplicado nas raízes de px como estamos elevando ao quadrado a ordem em que tomamos as raízes α1 αn não importa Exemplo 6 Seja px x3 px q então Discp 4p3 27q2 Exercício 13 Prove que o discriminante de um polinômio px se é zero se e só se px possui raízes repetidas Referències