AA XIV

AA XIV

1. Symmetric Groups

   • We shall write Map(A) for the set of functions from A to itself. Then ◦ is a binary operation on Map(A). Map(A) is a group wrt to ◦
     • Let A be a finite set and let f be a function from A to itself. Then f is injective if and only if f is surjective
   • Let A be a set. The identity map on A is the map idA : A → A satisfying idA(x) = x for all x ∈ A
     • Let f : A → A be a function. Then f is invertible if and only if f is a bijection. If f is invertible then f −1 is also a bijection
   • Let A be a set. We shall denote the set of bijections from A to itself by Sym(A).
     • Sn to be the group Sym({1, 2,...,n}). We call Sn the n-th symmetric group.
       • Sn has order n!
         • The elements of Sn are called permutations. Let a1,a2,...,an be the numbers 1, 2,...,n in some order. Then the following represents the unique permutation in Sn that sends 1 to a1, 2 to a2, . . . , and n to an.
         • Understanding Sym(A) with |A| = n is the same as understanding Sn
   • Let A be a set. Then (Sym(A),◦) is a group with idA as the identity element. We call Sym(A) the symmetric group on A

2. Binomial Thm

   • It is not all obvious from this formula that the binomial coefficient is an integer. As an application of Lagrange’s Theorem, we show that it is.
     • Recall that Sn has order n!. If we can find a subgroup H of Sn of order m!(n −m)!, then nCr |Sn|/|H|

3. Cycle Notation

   • Let a1,a2,...,am be distinct elements of the set {1, 2,...,n}. By the notation (XIV.28) (a1,a2,...,am) we mean the element of Sn that takes a1 to a2, a2 to a3, . . . , am−1 to am and am back to a1, and fixes all other elements of {1, 2,...,n}. The permutation (XIV.28) is called a cycle of length m. A cycle of length 2 is called a transposition.
     • Finally (1) is the cycle that takes 1 to itself and fixes all the other elements. Clearly (1) = (2) = (3) = (4) = (5) = id is nothing other than the identity permutation.
     • Every permutation can be written as a product of disjoint cycles
       • What does disjoint mean? Two cycles (a1,a2,...,an) and (b1,b2,...,bm) are said to be disjoint if ai 6= bj for all i, j. What does product mean? The product of two permutation is of course their composition as functions
       • Disjoint cycles commute
         • Every permutation can be written a product of transpositions. Note the absence of the word ‘disjoint’
           • Let n ≥ 2 be an integer. Let x1,x2,...,xn be variables, and let Pn be the polynomial
             • • The polynomial Pn is called the n-th alternating polynomial. It will help us to discover an important subgroup of Sn called the alternating group and denoted by An. The first three alternating polynomials are:
                 • • If σ ∈ Sn then define
                   • Let τ ∈ Sn be a transposition. Then τ(Pn) = −Pn
                     • If σ ∈ Sn then σ(Pn) = ±Pn. More precisely, if σ is a product of an even number of transpositions then σ(Pn) = Pn and if σ is a product of an odd number of transpositions then σ(Pn) = −Pn.
                       • Every permutation in Sn can be written as a product of either an even number of transpositions, or an odd number of transpositions but not both.
                         • Let n ≥ 2. We define the n-th alternating group to be An = {σ ∈ Sn : σ is even}.
                           • An is a subgroup of Sn

Imagens e arquivos do mapa