Chapter I.
On Substitutions.

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 a1, a2, …, an be a set of n 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 n letters. Such a substitution will change any given arrangement

a1,a2,,an
of the n letters into a definite new arrangement
b1,b2,,bn
of the same n letters.

3. One obvious form in which to write the substitution is

a1,a2,,an b1,b2,,bn
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 n letters occurring twice in the expression for the substitution; by the following process, the expression of the substitution may be materially simplified.

Let p be any one of the n letters, and q the letter in the lower line standing under p in the upper. Suppose now that r is the letter in the lower line that stands under q in the upper, and so on. Since the number of letters is finite, we must arrive at last at a letter s in the upper line under which p stands. If the set of n letters is not thus exhausted, take any letter p in the upper line, which has not yet occurred, and let q, r, … follow it as q, r, … followed p, till we arrive at s in the upper line with p standing under it. If the set of n letters is still not exhausted, repeat the process, starting with a letter p which has not yet occurred. Since the number of letters is finite, we must in this way at last exhaust them; and the n letters are thus distributed into a number of sets

p, q, r, , s; p, q, r, , s; p, q, r, , s; . . . . . . . . . . . . . . . . . . . . ;
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

(pqrs)
the operation of replacing p by q, q by r, …, and s by p, the substitution will be completely represented by the symbol
(pqrs)(pqrs)(pqrs).
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 (pqrs) 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

a,b,c,d,e c,b,d,a,e
may be written (acd)(b)(e), or (acd)be, or simply (acd). If for any reason it were desirable to indicate that substitutions of the five letters a, b, c, d, e 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 (qrsp) clearly represents the same substitution as (pqrs), if the letters that occur between r and s 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 (ab) followed by (ac) changes a into b, since b is unaltered by the second substitution. Again, (ab) changes b into a and (ac) changes a into c, so that the two substitutions performed successively change b into c. Lastly, (ab) does not affect c and (ac) changes c into a. Hence the two substitutions performed successively change a into b, b into c, c into a, and affect no other symbols. The result of the two substitutions performed successively is therefore equivalent to the substitution (abc); and it may be similarly shewn that (ac) followed by (ab) gives (acb) 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 s1s2, where s1 and s2 are the symbols of two given substitutions. We shall always understand by the symbol s1s2 the result of carrying out first the substitution s1 and then the substitution s2. Thus the two simple examples given above may be expressed in the form

(ab)(ac) = (abc), (ac)(ab) = (acb),

the sign of equality being used to represent that the substitutions are equivalent to each other.

If now

s1s2 = s4 ands2s3 = s5,
the symbol s1s2s3 may be regarded as the substitution s4 followed by s3 or as s1 followed by s5. But if s1 changes any letter a into b, while s2 changes b into c and s3 changes c into d, then s4 changes a into c and s5 changes b into d. Hence s4s3 and s1s5 both change a into d; and therefore, a being any letter operated upon by the substitutions,
s4s3 = s1s5.

Hence the meaning of the symbol s1s2s3 is definite; it depends only on the component substitutions s1, s2, s3 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 s1s2sn as the product of the substitutions s1, s2, …, sn 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 s1 be the substitution inverse to s, so that, if

s = a1,a2,,an b1,b2,,bn ,
then
s1 = b1,b2,,bn a1,a2,,an.
Let s0 denote the identical substitution which can be represented by
a1,a2,,an a1,a2,,an.

Then

ss1 = s0 ands1s = s0,
so that s is the substitution inverse to s1.

Now if

ts = ts,
then
tss1 = tss1,
or
ts0 = ts0.

But ts0 is the same substitution as t, since s0 produces no change; and therefore

t = t.

In exactly the same way, it may be shewn that the relation

st = st
involves
t = t.

8. The result of performing r times in succession the same substitution s is represented symbolically by sr. Since, as has been seen, products of substitutions obey the associative law of multiplication, it follows that

sμsν = sμ+ν = sνsμ.

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 s, s2, s3, … cannot be all distinct. Suppose that sm+1 is the first of the series which is the same as s, so that

sm+1 = s.

Then

smss 1 = ss1,
or
sm = s 0.

There is no index μ smaller than m for which this relation holds. For if

sμ = s 0,
then
sμ+1 = ss 0 = s,
contrary to the supposition that sm+1 is the first of the series which is the same as s.

Moreover the m 1 substitutions s, s2, …, sm1 must be all distinct. For if

sμ = sν,ν < μ < m,
then
sμνsν(sν) 1 = sν(sν) 1,
or
sμν = s 0,
which has just been shewn to be impossible.

The number m is called the order of the substitution s. In connection with the order of a substitution, two properties are to be noted. First, if

sn = s 0,
it may be shewn at once that n is a multiple of m the order of s; and secondly, if
sα = sβ,
then
α β 0(modm).

If now the equation

sμ+ν = sμsν
be assumed to hold, when either or both of the integers μ and ν is a negative integer, a definite meaning is obtained for the symbol sr, implying the negative power of a substitution; and a definite meaning is also obtained for s0. For
sμsν = sμν = sμνsν(sν) 1 = sμ(sν) 1,
so that
sν = (sν) 1.
Similarly it can be shewn that
s0 = s 0.

Since every power of s0 is the same as s0, and since wherever s0 occurs in the symbol s1s2sn of a compound substitution it may be omitted without affecting the result, it is clear that no ambiguity will result from replacing s0 everywhere by 1; in other words, we may use 1 to represent the identical substitution which leaves every letter unchanged. But when this is done, it must of course be remembered that the equation

sm = 1
is not a reducible algebraical equation, which is capable of being written in the form
(s 1)(sm1 + sm2 + + 1) = 0.

Indeed the symbol s + s, where s and s are any two substitutions, has no meaning.

9. If the cycles of a substitution

s = (pqrs)(pqs)(pqs)
contain m, m, m, … letters respectively, and if
sμ = 1,
μ must be a common multiple of m, m, m, …. For sμ changes p into a letter μ places from it in the cyclical set pq, r, …, s; and therefore, if it changes p into itself, μ must be a multiple of m. In the same way, it must be a multiple of m, m, …. Hence the order of s is the least common multiple of m, m, m, ….

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 ss are similar substitutions, so also clearly are srsr; and the orders of s and s are the same.

Let now

s = (apaqas)(apaqas)
and
t = a1,a2,,an b1,b2,,bn
be any two substitutions. Then

t1st = b1,b2,,bn a1,a2,,an(apaqas)(apaqas)a1,a2,,an b1,b2,,bn = (bpbqbs)(bpbqbs),

the latter form of the substitution being obtained by actually carrying out the component substitutions of the earlier form. Hence s and t1st are similar substitutions.

Since

s2s1 = s11s 1s2s1,
it follows that s1s2 and s2s1 are similar substitutions and therefore that they are of the same order. Similarly it may be shewn that s1s2s3sn, s2s3sns1, …, sns1s2s3 are all similar substitutions.

It may happen in particular cases that s and t1st are the same substitution. When this is so, t and s are permutable, that is, st and ts are equivalent to one another; for if

s = t1st,
then
ts = st.

This will certainly be the case when none of the symbols that are interchanged by t are altered by s; but it may happen when s and t operate on the same symbols. Thus if

s = (ab)(cd),t = (ac)(bd),
then
st = (ad)(bc) = ts.

Ex. 1. Shew that every regular substitution is some power of a circular substitution.

Ex. 2. If ss are permutable regular substitutions of the same mn letters of orders m and n, these numbers being relatively prime, shew that ss is a circular substitution in the mn letters.

Ex. 33. If

s = (123) (456)(789), s1 = (147) (258)(369), s2 = (456)(798),

shew that s is permutable with both s1 and s2, and that it can be formed by a combination of s1 and s2.

Ex. 4. Shew that the only substitutions of n given letters which are permutable with a circular substitution of the n letters are the powers of the circular substitution.

Ex. 5. Determine all the substitutions of the ten symbols involved in

s = (abcde)(αβγδ𝜖)
which are permutable with s.

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

(pqrs) = (pq)(pr)(ps),
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

(pq) = (pp)(pq)(pp),
every transposition, and therefore every substitution of n letters, can be expressed in terms of the n 1 transpositions
(a1a2),(a1a3),,(a1an).

The 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 n letters, which may be written

D = r=1r=n1 s=r+1s=n(a r as) .

The transposition (aras) changes the sign of the factor ar as. When q is less than either r or s, the transposition interchanges the factors aq ar and aq as; and when q is greater than either r or s, it interchanges the factors ar aq and as aq. When q lies between r and s, the pair of factors ar aq and aq as are interchanged and are both changed in sign. Hence the effect of the single transposition on D 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 D must be either to leave it unaltered or to change its sign. If a substitution leaves D 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 D, 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 n letters can be represented as the product of an even number of the n 1 transpositions

(a1a2),(a1a3),,(a1an),
in appropriate sequence and with the proper number of occurrences; and the product of any consecutive pair of these (a1ar)(a1as) is the circular substitution (a1aras).

Now

(a1a2as)(a1a2ar)(a1a2as)2 = (a 1a2as)(a1a2ar)(a1asa2) = (a1aras),

so that every circular substitution of order three displacing a1, and therefore every even substitution of n letters, can be expressed in terms of the n 2 substitutions

(a1a2a3),(a1a2a4),,(a1a2an)
and their powers.

Ex. 1. Shew that every even substitution of n letters can be expressed in terms of

(a1a2a3),(a1a4a5),,(a1an1an),
when n is odd; and in terms of
(a1a2a3),(a1a4a5),,(a1an2an1),(a1a2an),
when n is even.

Ex. 2. If n + 1 is odd, shew that every even substitution of mn + 1 letters can be expressed in terms of

(a1a2an+1),(a1an+2a2n+1),,(a1a(m1)n+2amn+1);
and if n + 1 is even, that every substitution of mn + 1 letters can be expressed in terms of this set of m circular substitutions.