up | next | prev | ptail | tail |
A mong the various notations used in the following pages, there is one of such frequent recurrence that a certain readiness in its use is very desirable in dealing with the subject of this treatise. We therefore propose to devote a preliminary chapter to explaining it in some detail.
2. Let , , …, be a set of distinct letters. The operation of replacing each letter of the set by another, which may be the same letter or a different one, when carried out under the condition that no two letters are replaced by one and the same letter, is called a substitution performed on the letters. Such a substitution will change any given arrangement
of the letters into a definite new arrangement of the same letters.3. One obvious form in which to write the substitution is
thereby indicating that each letter in the upper line is to be replaced by the letter standing under it in the lower. The disadvantage of this form is its unnecessary complexity, each of the letters occurring twice in the expression for the substitution; by the following process, the expression of the substitution may be materially simplified.Let be any one of the letters, and the letter in the lower line standing under in the upper. Suppose now that is the letter in the lower line that stands under in the upper, and so on. Since the number of letters is finite, we must arrive at last at a letter in the upper line under which stands. If the set of letters is not thus exhausted, take any letter in the upper line, which has not yet occurred, and let , , … follow it as , , … followed , till we arrive at in the upper line with standing under it. If the set of letters is still not exhausted, repeat the process, starting with a letter which has not yet occurred. Since the number of letters is finite, we must in this way at last exhaust them; and the letters are thus distributed into a number of sets
such that the substitution replaces each letter of a set by the one following it in that set, the last letter of each set being replaced by the first of the same set.If now we represent by the symbol
the operation of replacing by , by , …, and by , the substitution will be completely represented by the symbol The advantage of this mode of expressing the substitution is that each of the letters occurs only once in the symbol.4. The separate components of the above symbol, such as are called the cycles of the substitution. In particular cases, one or more of the cycles may contain a single letter; when this happens, the letters so occurring singly are unaltered by the substitution. The brackets enclosing single letters may clearly be omitted without risk of ambiguity, as also may the unaltered letters themselves. Thus the substitution
may be written , or , or simply . If for any reason it were desirable to indicate that substitutions of the five letters , , , , were under consideration, the second of these three forms would be used.5. The form thus obtained for a substitution is not unique. The symbol clearly represents the same substitution as , if the letters that occur between and in the two symbols are the same and occur in the same order; so that, as regards the letters inside the bracket, any one may be chosen to stand first so long as the cyclical order is preserved unchanged.
Moreover the order in which the brackets are arranged is clearly immaterial, since the operation denoted by any one bracket has no effect on the letters contained in the other brackets. This latter property is characteristic of the particular expression that has been obtained for a substitution; it depends upon the fact that the expression contains each of the letters once only.
6. When we proceed to consider the effect of performing two or more substitutions successively, it is seen at once that the order in which the substitutions are carried out in general affects the result. Thus to give a very simple instance, the substitution followed by changes into , since is unaltered by the second substitution. Again, changes into and changes into , so that the two substitutions performed successively change into . Lastly, does not affect and changes into . Hence the two substitutions performed successively change into , into , into , and affect no other symbols. The result of the two substitutions performed successively is therefore equivalent to the substitution ; and it may be similarly shewn that followed by gives as the resulting substitution. To avoid ambiguity it is therefore necessary to assign, once for all, the meaning to be attached to such a symbol as , where and are the symbols of two given substitutions. We shall always understand by the symbol the result of carrying out first the substitution and then the substitution . Thus the two simple examples given above may be expressed in the form
the sign of equality being used to represent that the substitutions are equivalent to each other.
If now
the symbol may be regarded as the substitution followed by or as followed by . But if changes any letter into , while changes into and changes into , then changes into and changes into . Hence and both change into ; and therefore, being any letter operated upon by the substitutions,Hence the meaning of the symbol is definite; it depends only on the component substitutions , , and their sequence, and it is independent of the way in which they are associated when their sequence is assigned. And the same clearly holds for the symbol representing the successive performance of any number of substitutions. To avoid circumlocution, it is convenient to speak of the substitution as the product of the substitutions , , …, in the sequence given. The product of a number of substitutions, thus defined, always obeys the associative law but does not in general obey the commutative law of algebraical multiplication.
7. The substitution which replaces every symbol by itself is called the identical substitution. The inverse of a given substitution is that substitution which, when performed after the given substitution, gives as result the identical substitution. Let be the substitution inverse to , so that, if
then Let denote the identical substitution which can be represented byThen
so that is the substitution inverse to .Now if
then orBut is the same substitution as , since produces no change; and therefore
In exactly the same way, it may be shewn that the relation
involves8. The result of performing times in succession the same substitution is represented symbolically by . Since, as has been seen, products of substitutions obey the associative law of multiplication, it follows that
Now since there are only a finite number of distinct substitutions that can be performed on a given finite set of symbols, the series of substitutions , , , … cannot be all distinct. Suppose that is the first of the series which is the same as , so that
Then
orThere is no index smaller than for which this relation holds. For if
then contrary to the supposition that is the first of the series which is the same as .Moreover the substitutions , , …, must be all distinct. For if
then or which has just been shewn to be impossible.The number is called the order of the substitution . In connection with the order of a substitution, two properties are to be noted. First, if
it may be shewn at once that is a multiple of the order of ; and secondly, if thenIf now the equation
be assumed to hold, when either or both of the integers and is a negative integer, a definite meaning is obtained for the symbol , implying the negative power of a substitution; and a definite meaning is also obtained for . For so that Similarly it can be shewn thatSince every power of is the same as , and since wherever occurs in the symbol of a compound substitution it may be omitted without affecting the result, it is clear that no ambiguity will result from replacing everywhere by ; in other words, we may use to represent the identical substitution which leaves every letter unchanged. But when this is done, it must of course be remembered that the equation
is not a reducible algebraical equation, which is capable of being written in the formIndeed the symbol , where and are any two substitutions, has no meaning.
9. If the cycles of a substitution
contain , , , … letters respectively, and if must be a common multiple of , , , …. For changes into a letter places from it in the cyclical set , , , …, ; and therefore, if it changes into itself, must be a multiple of . In the same way, it must be a multiple of , , …. Hence the order of is the least common multiple of , , , ….In particular, when a substitution consists of a single cycle, its order is equal to the number of letters which it interchanges. Such a substitution is called a circular substitution.
A substitution, all of whose cycles contain the same number of letters, is said to be regular in the letters which it interchanges; the order of such a substitution is clearly equal to the number of letters in one of its cycles.
10. Two substitutions, which contain the same number of cycles and the same number of letters in corresponding cycles, are called similar. If , are similar substitutions, so also clearly are , ; and the orders of and are the same.
Let now
and be any two substitutions. Thenthe latter form of the substitution being obtained by actually carrying out the component substitutions of the earlier form. Hence and are similar substitutions.
Since
it follows that and are similar substitutions and therefore that they are of the same order. Similarly it may be shewn that , , …, are all similar substitutions.It may happen in particular cases that and are the same substitution. When this is so, and are permutable, that is, and are equivalent to one another; for if
thenThis will certainly be the case when none of the symbols that are interchanged by are altered by ; but it may happen when and operate on the same symbols. Thus if
thenEx. 1. Shew that every regular substitution is some power of a circular substitution.
Ex. 2. If , are permutable regular substitutions of the same letters of orders and , these numbers being relatively prime, shew that is a circular substitution in the letters.
Ex. 33. If
shew that is permutable with both and , and that it can be formed by a combination of and .
Ex. 4. Shew that the only substitutions of given letters which are permutable with a circular substitution of the letters are the powers of the circular substitution.
Ex. 5. Determine all the substitutions of the ten symbols involved in
which are permutable with .The determination of all the substitutions which are permutable with a given substitution will form the subject of investigation in Chapter X.
11. A circular substitution of order two is called a transposition. It may be easily verified that
so that every circular substitution can be represented as a product of transpositions; and thence, since every substitution is the product of a number of circular substitutions, every substitution can be represented as a product of transpositions. It must be remembered, however, that, in general, when a substitution is represented in this way, some of the letters will occur more than once in the symbol, so that the order in which the constituent transpositions occur is essential. There is thus a fundamental difference from the case when the symbol of a substitution is the product of circular substitutions, no two of which contain a common letter.Since
every transposition, and therefore every substitution of letters, can be expressed in terms of the transpositionsThe number of different ways in which a given substitution may be represented as a product of transpositions is evidently unlimited; but it may be shewn that, however the representation is effected, the number of transpositions is either always even or always odd. To prove this, it is sufficient to consider the effect of a transposition on the square root of the discriminant of the letters, which may be written
The transposition changes the sign of the factor . When is less than either or , the transposition interchanges the factors and ; and when is greater than either or , it interchanges the factors and . When lies between and , the pair of factors and are interchanged and are both changed in sign. Hence the effect of the single transposition on is to change its sign. Since any substitution can be expressed as the product of a number of transpositions, the effect of any substitution on must be either to leave it unaltered or to change its sign. If a substitution leaves unaltered it must, when expressed as a product of transpositions in any way, contain an even number of transpositions; and if it changes the sign of , every representation of it, as a product of transpositions, must contain an odd number of transpositions. Hence no substitution is capable of being expressed both by an even and by an odd number of transpositions.
A substitution is spoken of as odd or even, according as the transpositions which enter into its representation are odd or even in number.
Further, an even substitution can always be represented as a product of circular substitutions of order three. For any even substitution of letters can be represented as the product of an even number of the transpositions
in appropriate sequence and with the proper number of occurrences; and the product of any consecutive pair of these is the circular substitution .Now
so that every circular substitution of order three displacing , and therefore every even substitution of letters, can be expressed in terms of the substitutions
and their powers.Ex. 1. Shew that every even substitution of letters can be expressed in terms of
when is odd; and in terms of when is even.Ex. 2. If is odd, shew that every even substitution of letters can be expressed in terms of
and if is even, that every substitution of letters can be expressed in terms of this set of circular substitutions.
up | next | prev | ptail | top |