Ir ao conteúdo principal

Seção 5.1 Definições e Notação

Em geral, as permutações de um conjunto \(X\) formam o grupo \(S_X\text{.}\) Se \(X\) é um conjunto finito, podemos supor que \(X=\{ 1, 2, \ldots, n\}\text{.}\) Neste caso, escrevemos \(S_n\) no lugar de \(S_X\text{.}\) O seguinte teorema diz que \(S_n\) é um grupo. Chamaremos este grupo grupo simétrico em \(n\) símbolos.

A identidade de \(S_n\) é simplesmente a função identidade que leva 1 em 1, 2 em 2, \(\ldots\text{,}\) \(n\) em \(n\text{.}\) Se \(f : S_n \rightarrow S_n\) é uma permutação, então \(f^{-1}\) existe, pois \(f\) é bijetiva; logo, toda permutação tem uma inversa. A composição de funções é associativa, o que faz da operação do grupo associativa. Deixamos como exercício a demonstração de que \(|S_n|= n!\text{.}\)

Um subgrupo de \(S_n\) se chama grupo de permutações.

Considere o subgrupo \(G\) de \(S_5\) que consiste da permutação \(\identity\) e das permutações

\begin{align*} \sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 5 & 4 \end{pmatrix}\\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 4 & 5 \end{pmatrix}\\ \mu & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 5 & 4 \end{pmatrix}. \end{align*}

A seguinte tabela nos informa como multiplicar elementos no grupo de permutações \(G\text{.}\)

\begin{equation*} \begin{array}{c|cccc} \circ & \identity & \sigma & \tau & \mu \\ \hline \identity & \identity & \sigma & \tau & \mu \\ \sigma & \sigma & \identity & \mu & \tau \\ \tau & \tau & \mu & \identity & \sigma \\ \mu & \mu & \tau & \sigma & \identity \end{array} \end{equation*}

Nota 5.1.3.

Apesar de ser natural multiplicar os elementos em um grupo da esquerda para a direita, as funções são compostas da direita para a esquerda. Sejam \(\sigma\) e \(\tau\) permutações em um conjunto \(X\text{.}\) Para compor \(\sigma\) e \(\tau\) como funções, calculamos \((\sigma \circ \tau)(x) = \sigma( \tau(x))\text{.}\) Isto é, aplicamos primeiro \(\tau\text{,}\) depois \(\sigma\text{.}\) Há diversas formas de resolver esta inconsistência. Nós adotaremos a convenção de multiplicar permutações da direita para a esquerda. Para calcular \(\sigma \tau\text{,}\) faça \(\tau\) primeiro e depois \(\sigma\text{.}\) Isto é, por \(\sigma \tau (x)\) queremos dizer \(\sigma( \tau( x))\text{.}\) (Outra maneira de resolver este problema seria escrever as funções na direita; isto é, em vez de escrever \(\sigma(x)\text{,}\) poderíamos escrever \((x)\sigma\text{.}\) Também poderíamos multiplicar as permutações da esquerda para a direita para coincidir com a forma usual de multiplicar elementos em um grupo. Cada uma destas soluções já foi usada.)

A multiplicação de permutações não é comutativa, em geral. Sejam

\begin{align*} \sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{pmatrix}\\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}. \end{align*}

Então

\begin{equation*} \sigma \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{pmatrix}, \end{equation*}

mas

\begin{equation*} \tau \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \end{pmatrix}. \end{equation*}

Subseção 5.1.1 Notação cíclica

A notação que temos usado até aqui para representar as permutações é incômoda, para dizer o mínimo. Para trabalhar efetivamente com grupos de permutações, necessitaremos um método mais claro de escrever e manipular permutações.

Uma permutação \(\sigma \in S_X\) é um ciclo de tamanho \(k\) se existem elementos \(a_1, a_2, \ldots, a_k \in X\) tais que

\begin{align*} \sigma( a_1 ) & = a_2\\ \sigma( a_2 ) & = a_3\\ & \vdots\\ \sigma( a_k ) & = a_1 \end{align*}

e \(\sigma( x) =x\) para todos os demais elementos \(x \in X\text{.}\) Escreveremos \((a_1, a_2, \ldots, a_k )\) para denotar o ciclo \(\sigma\text{.}\) Os ciclos são blocos básicos para construir todas as permutações.

A permutação

\begin{equation*} \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 6 & 3 & 5 & 1 & 4 & 2 & 7 \end{pmatrix} = (1 6 2 3 5 4 ) \end{equation*}

é um ciclo de tamanho 6, enquanto

\begin{equation*} \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 4 & 2 & 3 & 5 & 6 \end{pmatrix} = (2 4 3) \end{equation*}

é um ciclo de tamanho 3.

Nem toda permutação é um ciclo. Considere a permutação

\begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 1 & 3 & 6 & 5 \end{pmatrix} = (1 2 4 3)(5 6). \end{equation*}

Esta permutação, na verdade, contém um ciclo de tamanho 2 e um ciclo de tamanho 4.

É muito simples calcular o produto de ciclos. Suponhamos que

\begin{equation*} \sigma = (1 3 5 2 ) \quad \text{y} \quad \tau = (2 5 6). \end{equation*}

Se pensamos em \(\sigma\) como

\begin{equation*} 1 \mapsto 3, \qquad 3 \mapsto 5, \qquad 5 \mapsto 2, \qquad 2 \mapsto 1, \end{equation*}

e \(\tau\) como

\begin{equation*} 2 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2, \end{equation*}

então para \(\sigma \tau\text{,}\) lembrando que primeiro devemos aplicar \(\tau\) e depois \(\sigma\text{,}\) deve ser o caso que

\begin{equation*} 1 \mapsto 3, \qquad 3 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2 \mapsto 1, \end{equation*}

ou \(\sigma \tau = (1 3 5 6 )\text{.}\) Se \(\mu = (1634)\text{,}\) então \(\sigma \mu = (1 6 5 2)(3 4)\text{.}\)

Dois ciclos em \(S_X\text{,}\) \(\sigma = (a_1, a_2, \ldots, a_k )\) e \(\tau = (b_1, b_2, \ldots, b_l )\text{,}\) são disjuntos se \(a_i \neq b_j\) para todo \(i\) e para todo \(j\text{.}\)

Os ciclos \((1 3 5)\) e \((2 7 )\) são disjuntos; enquanto os ciclos \((1 3 5)\) e \((3 4 7 )\) não o são. Calculando seus produtos, descobrimos que

\begin{align*} (1 3 5)(2 7 ) & = (1 3 5)(2 7 )\\ (1 3 5)(3 4 7 ) & = (1 3 4 7 5). \end{align*}

O produto de dois ciclos que não são disjuntos às vezes pode ser reduzido a algo menos complicado; o produto de dois ciclos disjuntos não pode ser simplificado.

Seja \(\sigma = (a_1, a_2, \ldots, a_k )\) e \(\tau = (b_1, b_2, \ldots, b_l )\text{.}\) Devemos mostrar que \(\sigma \tau(x) = \tau \sigma(x)\) para todo \(x \in X\text{.}\) Se \(x\) não está em \(\{ a_1, a_2, \ldots, a_k \}\) nem em \(\{b_1, b_2, \ldots, b_l \}\text{,}\) então tanto \(\sigma\) como \(\tau\) fixam \(x\text{.}\) Isto é, \(\sigma(x)=x\) y \(\tau(x)=x\text{.}\) Logo,

\begin{equation*} \sigma \tau(x) = \sigma( \tau(x)) = \sigma(x) = x = \tau(x) = \tau( \sigma(x)) = \tau \sigma(x). \end{equation*}

Não devemos esquecer que estamos multiplicando as permutações da direita para a esquerda,. Agora suponhamos que \(x \in \{ a_1, a_2, \ldots, a_k \}\text{.}\) Então \(\sigma( a_i ) = a_{(i \bmod k) + 1}\text{;}\) isto é,

\begin{align*} a_1 & \mapsto a_2\\ a_2 & \mapsto a_3\\ & \vdots\\ a_{k-1} & \mapsto a_k\\ a_k & \mapsto a_1. \end{align*}

No entanto, \(\tau(a_i) = a_i\) pois \(\sigma\) e \(\tau\) são disjuntos. Portanto,

\begin{align*} \sigma \tau(a_i) & = \sigma( \tau(a_i))\\ & = \sigma(a_i)\\ & = a_{(i \bmod k)+1}\\ & = \tau( a_{(i \bmod k)+1} )\\ & = \tau( \sigma(a_i) )\\ & = \tau \sigma(a_i). \end{align*}

Similarmente, se \(x \in \{b_1, b_2, \ldots, b_l \}\text{,}\) então \(\sigma\) e \(\tau\) também comutam.

Podemos supor que \(X = \{ 1, 2, \ldots, n \}\text{.}\) Se \(\sigma \in S_n\) e definimos \(X_1\) como \(\{ \sigma(1), \sigma^2(1), \ldots \}\text{,}\) então o conjunto \(X_1\) é finito, pois \(X\) é finito. Agora seja \(i\) o primeiro inteiro em \(X\) que não está em \(X_1\) e definamos \(X_2\) como \(\{ \sigma(i), \sigma^2(i), \ldots \}\text{.}\) Novamente, \(X_2\) é um conjunto finito. Continuando desta maneira, podemos definir conjuntos finitos disjuntos \(X_3, X_4, \ldots\text{.}\) Como \(X\) é um conjunto finito, estamos seguros de que este processo terminará e que haverá um número finito destes conjuntos, digamos \(r\text{.}\) Se \(\sigma_i\) é o ciclo definido por

\begin{equation*} \sigma_i( x ) = \left\{\begin{array}{ll} \sigma( x ) & x \in X_i \\ x & x \notin X_i, \end{array}\right. \end{equation*}

então \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_r\text{.}\) Como os conjuntos \(X_1, X_2, \ldots, X_r\) são disjuntos, os ciclos \(\sigma_1, \sigma_2, \ldots, \sigma_r\) também o são.

Sejam

\begin{align*} \sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 3 & 1 & 5 & 2 \end{pmatrix}\\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 1 & 5 & 6 & 4 \end{pmatrix}. \end{align*}

Usando notação cíclica, podemos escrever

\begin{align*} \sigma & = (1624)\\ \tau & = (13)(456)\\ \sigma \tau & = (1 3 6) ( 2 4 5)\\ \tau \sigma & = (1 4 3 )(2 5 6). \end{align*}

Nota 5.1.11.

A partir de agora, nos será conveniente usar a notação cíclica para representar as permutações. Ao usar a notação cíclica, comumente representaremos a permutação identidade por \((1)\) ou por \(()\text{.}\)

Subseção 5.1.2 Transposições

A permutação (não trivial) mais simples é um ciclo de tamanho 2. Tais ciclos se chamam transposições. Como

\begin{equation*} (a_1, a_2, \ldots, a_n ) = (a_1 a_n ) (a_1 a_{n-1} ) \cdots ( a_1 a_3 ) (a_1 a_2 ), \end{equation*}

qualquer ciclo pode ser escrito como o produto de transposições, o que nos leva à seguinte proposição.

Considere a permutação

\begin{equation*} ( 1 6 ) (2 5 3) = (1 6 )( 2 3 )( 2 5 ) = (1 6 )( 4 5 )(2 3 )( 4 5 )(2 5 ). \end{equation*}

Como podemos ver, não há uma única forma de representar a permutação como produto de transposições. Por exemplo, podemos escrever a identidade como \((1 2 )(1 2 )\text{,}\) como \((1 3 )(2 4 )(1 3 )( 2 4 )\text{,}\) e de muitas outras formas. Ainda assim, como ocorre, nenhuma permutação pode ser escrita tanto como um produto de um número par como de um número ímpar de transposições. Por exemplo, podemos representar a permutação \((1 6)\) por

\begin{equation*} (2 3 )(1 6)( 2 3) \end{equation*}

ou por

\begin{equation*} (3 5) (1 6) (1 3) (1 6) (1 3) (3 5) (5 6), \end{equation*}

mas \((1 6)\) sempre será o produto de um número ímpar de transposições.

Procederemos por indução em \(r\text{.}\) Uma transposição não pode ser a identidade; logo, \(r \gt 1\text{.}\) Se \(r=2\text{,}\) está provado. Suponhamos que \(r \gt 2\text{.}\) Neste caso o produto de ao menos duas destas transposições, \(\tau_{r-1} \tau_r\text{,}\) deve estar em um dos casos seguintes:

\begin{align*} (a b)(a b) & = \identity\\ (b c)(a b) & = (a c)(b c)\\ (c d)(a b) & = (a b)(c d)\\ (a c)(a b) & = (a b)(b c), \end{align*}

em que \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) e \(d\) são distintos.

A primeira equação simplesmente diz que uma transposição é sua própria inversa. Se isto ocorre, apague \(\tau_{r-1} \tau_r\) do produto para obter

\begin{equation*} \identity = \tau_1 \tau_2 \cdots \tau_{r - 3} \tau_{r - 2}. \end{equation*}

Por indução \(r - 2\) é par; logo, \(r\) deve ser par.

Em cada um dos outros três casos, podemos substituir \(\tau_{r - 1} \tau_r\) com o lado direito da equação correspondente para obter um novo produto de \(r\) transposições para a identidade. Neste novo produto, a última ocorrência de \(a\) será na penúltima transposição. Podemos continuar este processo com \(\tau_{r - 2} \tau_{r - 1}\) para obter ou um produto de \(r - 2\) transposições ou um novo produto de \(r\) transposições, em que a última ocorrência de \(a\) é em \(\tau_{r - 2}\text{.}\) Se a identidade é o produto de \(r - 2\) transposições, então novamente está provado, pela hipótese de indução; senão, repetiremos o procedimento com \(\tau_{r - 3} \tau_{r - 2}\text{.}\)

Em algum momento, teremos duas transposições adjacentes iguais, que se cancelarão, ou apenas \(a\) estará presente na primeira transposição. Mas este último caso não pode ocorrer, pois a identidade não fixaria \(a\) nesta situação. Portanto, a identidade deve ser o produto de \(r-2\) transposições e, novamente pela hipótese de indução, está provado.

Suponhamos que

\begin{equation*} \sigma = \sigma_1 \sigma_2 \cdots \sigma_m = \tau_1 \tau_2 \cdots \tau_n, \end{equation*}

com \(m\) par. Devemos mostrar que \(n\) também é um número par. A inversa de \(\sigma\) é \(\sigma_m \cdots \sigma_1\text{.}\) Como

\begin{equation*} \identity = \sigma \sigma_m \cdots \sigma_1 = \tau_1 \cdots \tau_n \sigma_m \cdots \sigma_1, \end{equation*}

\(n\) deve ser par pelo Lema 5.1.14. A demonstração do caso em que \(\sigma\) pode ser expressa como o produto de um número ímpar de transposições é deixada como exercício.

À luz do Teorema 5.1.15, definimos que uma permutação é par se pode ser expressa como o produto de um número par de transposições e ímpar se pode ser expressa como o produto de um número ímpar de transposições.

Subseção 5.1.3 Os Grupos Alternantes

Um dos subgrupos mais importantes de \(S_n\) é o conjunto de todas as permutações pares, \(A_n\text{.}\) O grupo \(A_n\) se chama grupo alternante em \(n\) símbolos.

Como o produto de duas permutações pares é também uma permutação par, \(A_n\) é fechado. A identidade é uma permutação par e portanto está em \(A_n\text{.}\) Se \(\sigma\) é uma permutação par, então

\begin{equation*} \sigma = \sigma_1 \sigma_2 \cdots \sigma_r, \end{equation*}

em que \(\sigma_i\) são transposições e \(r\) é par. Como a inversa de uma transposição é ela mesma,

\begin{equation*} \sigma^{-1} = \sigma_r \sigma_{r-1} \cdots \sigma_1 \end{equation*}

também está em \(A_n\text{.}\)

Seja \(A_n\) o conjunto de permutações pares em \(S_n\) e \(B_n\) o conjunto de permutações ímpares. Se pudermos mostrar que existe una bijeção entre estes conjuntos, demonstraremos que contém o mesmo número de elementos. Fixemos uma transposição \(\sigma\) em \(S_n\text{.}\) Como \(n \geq 2\text{,}\) tal \(\sigma\) existe. Defina

\begin{equation*} \lambda_{\sigma} : A_n \rightarrow B_n \end{equation*}

como

\begin{equation*} \lambda_{\sigma} ( \tau ) = \sigma \tau . \end{equation*}

Suponhamos que \(\lambda_{\sigma} ( \tau ) = \lambda_{\sigma} ( \mu )\text{.}\) Então \(\sigma \tau = \sigma \mu\) e assim

\begin{equation*} \tau = \sigma^{-1} \sigma \tau = \sigma^{-1} \sigma \mu = \mu. \end{equation*}

Portanto, \(\lambda_{\sigma}\) é 1-1. Deixaremos a demonstração de que \(\lambda_{\sigma}\) é sobrejetiva como exercício.

O grupo \(A_4\) é o subgrupo de \(S_4\) que consiste das permutações pares. Há doze elementos em \(A_4\text{:}\)

\begin{align*} & (1) && (12)(34) && (13)(24) && (14)(23) \\ & (123) && (132) && (124) && (142) \\ & (134) && (143) && (234) && (243). \end{align*}

Um dos exercícios ao final do capítulo será encontrar todos os subgrupos de \(A_4\text{.}\) Você descobrirá que não há nenhum subgrupo de ordem 6. Isso te surpreende?

Subseção 5.1.4 Note Histórica

Lagrange foi o primeiro a pensar nas permutações como funções de um conjunto em si mesmo, mas foi Cauchy quem desenvolveu os teoremas básicos e a notação para as permutações. Ele foi o primeiro a usar a notação cíclica. Augustin-Louis Cauchy (1789–1857) nasceu em Paris durante o apogeu a Revolução Francesa. Sua família deixou Paris e foi para o povoado de Arcueil para escapar do Reino do Terror. Um dos vizinhos da família era Pierre-Simon Laplace (1749–1827), que o motivou a iniciar uma carreira na matemática. Cauchy começou sua carreira como matemático resolvendo um problema de geometria que Lagrange o entregou. Cauchy escreveu mais de 800 trabalhos em diversos tópicos, como equações diferenciais, grupos finitos, matemática aplicada e análise complexa. Foi um dos matemáticos responsáveis por dar rigor ao Cálculo Diferenciável. Provavelmente há mais teoremas e conceitos na matemática associados ao nome de Cauchy que a qualquer outro matemático.