Chapter 0

INTRODUCTORY REMARKS

0.1 Odd and even numbers: The terms odd and even apply to positive a well a to non- positive numbers, though they were used originally only for positive numbers.. A number which is twice an integer is called even, a non-even integer odd, whence zero is even; if a is even (odd), -a is even (odd) and a ± l is odd (even). The integers form a double sequence, in which the elements are alternately even and odd. The distinction between even and odd - although it involves a very simple principle - has an important role in Algebra and in other branches of Mathematics.

The sum as well as the differences of two odd (even) numbers are even, those of one odd and one even number are odd. In order to generalize these propositions, consider

Let

m_j = 2r_j + 1, if m_j is odd,
m_j = 2r_j, if m_j is even.

Then

is odd or even depending on whether q is odd or even, whence: If in a sum of integral numbers exactly q terms are odd, the sum is odd or even according to q being odd or even.

In particular, set q= n.

A sum of n odd numbers is odd or even, according to whether n is odd even.

Exercise: Let n objects be arranged in a linear manner, and then be rearranged to a second position. In the process, a objects move forward to the right while b objects recede to the left. Out of the a elements moving forward, a₁ are moved by an even number, a₂ by an odd number of places..Similarly, b₁ objects recede by an even and b₂ by an odd number of places. Prove that both a₂ and b₂ are either odd,or even.

0.2 Mathematical Induction In life as well in experimental Science, you draw conclusions in the following manner. A certain observation is made in a. large number of particular cases, you draw from these statements that there exists a general law. This form of conclusion is called conclusion by induction. For example, the statement Palm trees grow higher than bananas is based on an experience derived from a restricted number of plants of both the species. We shall not investigate here why in many cases conclusions of this type are justified . In mathematics, ordinary induction is not admissible: For general rules, a form of conclusion is often applied which for its apparent similarity with ordinary induction is called mathematical induction.

*As a matter of fact, the task of mathematics does not consist mainly of the enunciatioii of statements, but of demonstrating their logical necessity. A mathematical statement based on ordinary induction may be true, but it is of little mathematical value, unless it has a logical foundation.. An example of an obviously false statement reached by ordinary induction is: The number 2520 is divisible by every integer. Of course, it is divisible by 1, 2, 3, 4, 5, 6, 7, 8, 9,10 as well as by some more numbers which may have been selected at random such as 20, 56, 126, 420, 630, whence you may conclude erroneously the truth of the statement by ordinary induction.

Principle of mathematical induction: Let S(n) be a statement concerning the positive integers n = 1, 2,.,.,: Let 1. S(l) be a true statement, 2. let it be possible to demonstrate that if S(m) is a true statement, then S(m + 1) is also a true statement. Then S(n) holds for every positive integral value of n.

Proof: Let S(n) be not true for every positive integral value, then there exist positive integral values for which the statement does not hold. Among these values, there is one smallest integral number, say a + 1. As S(l) is supposed to be true, a is a positive number. Thus S(a) holds, but S(a + 1) does not hold contrary to Supposition 2., whence S(n) holds for every positive integral value of n.

Corollary: If S(n) is true for n = n₀ and Supposition 2. of the proposition above holds, then S(n) holds for n £ n₀.

0.3 Permutations

0.31 Presentations of permutations. You are given n distinct objects, say the numbers

Consider transformations by which the objects (1) are interchanged, called permutations. Any permutation is uniquely determined when it is known into which element each individual element of (1) is transformed, whence a permutation can be represented by two rows containing the n elements (1), ordered in such a way that below every element k in the upper row appears in the lower row the element a_k, into which k is transformed.

The digits (1) need not be given in their natural order in the first row of (2). They may be interchanged in any manner, if the same change is made in the second row; it is only essential that a particular element a_k is placed below a particular k to indicate that k has to be replaced by a_k. In order to check whether two given permutations are identical or not, you may interchange the vertical columns in the corresponding scheme (2) in such a way that the digits in the first row have the natural order in both cases. If after this operation the second rows are the same for the two permutations, they are identical, other- wise they differ. It is however not always convenient to arrange the digits of the first line in their natural order. For example, there exists for every permutation an inverse

The connection between A and A' is such that if A replaces any object c by an object d, then A^-1 replaces d by c. Hence, if you interchange the objects (1) at first according to A and then according to A^-1, every object remains unaltered. Indeed, the permutation which does not alter any object must indeed also be considered to be a permutation; it is called the identical permutation or just the identity:.

Moreover, the following permutations are of special interest :

Cyclic permutations:

in particular, those with m = 2. so-called transpositions:

The transposition (5) is just an interchange of the two objects a and b; the notation on the right hand sides of (4) and (5) will be generalized 0.33.

0.32 Composition of permutations . Consider 3 permutations of the objects(1) in 0.31:

Since a_k takes all the values 1, ··· , n, you can also write

Hence, if you perform at first A, and then B, any object k is replaced by

The thus formed permutation is said to consist of A and B and will be denoted by the product

In general, the products B A and A B will differ. You may ask: Why does the order of the transformation enter into the product written from the right to the left? This mode of notation has analogues in other branches of mathematics; for example, f f(x) indicates that x is to be represented y = (x) and then y by f(y). Due to this similarity, such notation is at times called functional. Many authors employ an inverse mode of notation, proceeeding from the left to the right. Notation is just a convention; both approaches are equivalent and have purely formal advantages and disadvantages.

Applying (1) to the products CB, (CB)A, C(BA), you find

Hence you can omit the brackets on the right hand side and denote (2) by C B A. This permutation is achieved by performing first A, then B, and finally C. Equation (2) yields:

The associative law applies to permutations.

Applying (2) to (2') and (3) of 0.31, you find for every permutation A

Moreover, let A and B be any two permutations, and

multiplying by A^-1 from the left (right) and applying (2) and (4), you find

On the other hand, (6) is a solution of (5), whence (5) has one and only one solution.

0.33 Decomposition of permutations A permutation can be represented as a product of permutations of a special type. We will discuss here two important modes of representation.

Theorem 1 Every permutation of n > 1 objects can be represented by a product of transpositions.

Proof (by mathematical induction): For n = 2, the theorem is obvious. Suppose that the theorem is true for n = m — 1, then it holds also for those permutations of m objects where at least one object remains unaltered. Let A be an arbitrary permutation of m objects, and let A change the object to be changed into b. Then a is not changed by A' = (a, b) A, whence A' is a product of transpositions. Hence

is a product of transpositions.

Exercises:

(1) Prove that the number of the different permutations of n objects equals n!
(2) Represent J as a product of two transpositions.
(3) Show that A ¹ J can be represented as the product of transpositions the number of which is less than n.

The representation of A as a product of transpositions is not unique. For example, you can perform any number of transpositions and then arrange them systematically (cf Ex. 3). Next, consider a different, unique representation.

Let A be any particular permutation and a_i be transformed by A into a₂, again a₂ into a₃, etc. The sequence

is infinite, everyone of its elements determines uniquely the following one as well as the preceding one, whence —as it contains only a finite number of different elements —it is a periodic sequence. The elements, for example,

are interchanged in a cyclic order. Let b₁ be any object which is subject to the permutation and does not belong to the cycle (1), then b₁ is transformed into an element b₂, which does not belong to (1), and thus b₁ generates a cycle which has no element in common with (1). You can repeat this procedure until it stops after r £ n steps. Hence the permutation generates a partition of the given objects into r cycles

where 1 £ r £ n.

The order of the elements in every cycle is determined up to a cyclic permutation which remains arbitrary and the cycles can be interchanged among themselves; however, for a given A, every object determines its cycle uniquely, whence A determines (2) uniquely. The objects which are not displaced by A form cycles, each by themselves. In order to save space, cycles with one element are often omitted. The notation (4) and (5) introduced in 0.31 appears now to be a special case of the present notation. On the other hand, (2) can be considered to be a product of the cyclic permutations corresponding to its cycles, whence you have

Theorem 2: Any permutation A can be represented as a product (2) of cyclic permutations in such a manner that different factors displace different objects. This representation is unique except for the order of the factors which remains arbitrary.

0.34 Even and odd permutations

Definition: A permutation A is said to be even or odd according to the number of even cycles in 0.33, (2) is even or odd.

Theorem: Every product of an even (odd) number of transpositions is even (odd).

Proof: The theorem is obvious if the number of transpositions is zero or one. By the principle of mathematical induction, you have therefore only to prove that composition of a permutation A from the left by a transposition an even A becomes odd and conversely. Let A be represented by cycles as in (2) - cycles with a single element (if any) also being taken into consideration - and (a₁, b₁) be the transposition. Then either a₁ and b₁ occur in the same cycle of A, or in two different cycles. Now

Multiplying from the left by (a₁, b₁) and interchanging the two sides, you obtain

As the other cycles do not change, the left hand factor (a₁, b₁) causes neither a partition of a cycle into two cycles nor conversely an amalgamation of two cycles into a single one. An odd cycle is partitioned into an even and an one odd one, an even cycle into either two odd or two even ones, whence the number of even cycles changes by ±l. The same applies to amalgamation as it is the converse operation.

Corollary 1: A permutation which can be represented as a product of an even (odd) number of transpositions cannot be represented as a product of an odd (even) number of transpositions.

Corollary 2: Composition of two even (odd) permutations yields an even permutations, of one even and one odd permutation an odd permutation.

Exercises.

1. Write down some permutations and determine whether they are even or odd.
2. Show that every even permutation of n > 2 objects can be represented by composition of suitable cyclic permutations of 3 objects.
3. An even cycle is an odd permutation, an odd cycle is an even permutation.

next