SUBSTITUTION GROUPS Among the first closed sets of operations to be studied were closed sets of substitutions on letters or symbols. To such a closed set Galois gave the name group. A letter substitution, or, briefly, a substitution, is the operation of replacing a set of sym bols or letters by the same set of symbols or letters arranged in a different order; e.g., the notation indicates that each letter in the upper row is replaced by the letter under it in the second row. The same operation may be indicated by the notation where the first parenthesis means that is replaced by by and by thereby closing the cycle. This notation can be still further abbreviated by writing only the subscript in the cycle. Thus, s = (I (45) Every substitution may be expressed in the cycle notation where no two cycles contain a common letter. If each of the n letters is replaced by itself, the substitution is called the iden tical substitution and is denoted by the figure I. If the n letters be operated on by a given substitution s and the letters in the new order be operated upon by a second substitution t, the result is a new arrangement and the replacing of the letters in the origi nal order by the final order is a third substitution called the product of s and t and denoted by st. Multiplication of two sub stitutions is not in general commutative. For example, if S = and t = st = and is = . A substitu tion consisting of a single cycle of two letters is called a trans position. Every substitution may be resolved into the product of transpositions and in more . than one way. A fundamental property of all substitutions is that the number of transpositions into which a given substitution may be resolved is either always even or always odd. The product of two even, or of two odd substitutions, is even, and the product of an odd and an even substitution is odd.
Multiplication is associative, i.e., (st)u = s(tu), so that the meaning of stu is unambiguous. The product of a substitution s taken m times as a factor is written sm. Since the associative law holds, powers of substitutions follow the index law of ordinary algebra. In symbols, sin sn = sm+n. Moreover, s° = 1. Since the number of possible substitutions on n letters is finite, in the series I, s, there must sometime arise a repetition such that Sm- = sn and consequently sm = I. The smallest positive integer m for which sm= I, is called the order of the substitution. Cor responding to any given substitution s there is another denoted by s-1 such that ss i I . This substitution is called the reciprocal of s. To see that s 1 always exists, it suffices to note that s Sm-1= I, so that The possible n-factorial substitutions on n letters form a group, which contains the iden tical element and an inverse for every element in the group.