Permutations

The main subject of this book is usually known as linear algebra. In the last three sections, however, the emphasis was on something called multilinear algebra. It is hard to say exactly where the dividing line is between the two subjects. Since, in any case, both are quite extensive, it would not be practical to try to stuff a detailed treatment of both into the same volume. Nor is it desirable to discuss linear algebra in its absolutely pure state; the addition of even a small part of the multilinear theory (such as is involved in the modern view of tensor products and determinants) extends the domain of applicability of the linear theory pleasantly out of proportion with the effort involved. We propose, accordingly, to continue the study of multilinear algebra; our intention is to draw a more or less straight line between what we already know and the basic facts about determinants. With that in mind, we shall devote three sections to the discussion of some simple facts about combinatorics; the connection between those facts and multilinear algebra will appear immediately after that discussion.

By a permutation of the integers between and (inclusive) we shall mean a one-to-one transformation that assigns to each such integer another one (or possibly the same one). To say that the transformation is one-to-one means, of course, that if are the integers that assigns to , respectively, then can happen only in case . Since this implies that both the sets and consist of exactly elements, it follows that they consist of exactly the same elements. From this, in turn, we infer that a permutation of the set maps that set onto itself, that is, that if , then there exists at least one (and, in fact, exactly one) such that . The total number of the integers under consideration, namely, , will be held fixed throughout the following discussion.

The theory of permutations, like everything else, is best understood by staring hard at some non-trivial examples. Before presenting any examples, however, we shall first mention some of the general things that can be done with permutations; by this means the examples will illustrate not only the basic concept but also its basic properties.

If and are arbitrary permutations, a permutation (to be denoted by ) can be defined by writing for each . To prove that is indeed a permutation, observe that if , then (since is one-to-one), and therefore (since is one-to-one). The permutation is called the product of the permutations and . To say that the order is important. In general , or, in other words, permutation multiplication is not commutative.

Multiplication of permutations is associative; that is, if , , and are permutations, then To prove this, we must show that for every . The proof consists of several applications of the definition of product, as follows: and

In view of this result we may and shall omit parentheses in writing the product of three or more permutations. The result also enables us to prove the obvious laws of exponents. The powers of a permutation are defined inductively by writing and for all ; the associative law implies that and for all and . Observe that any two powers of a permutation commute with each other, that is, that .

The simplest permutation is the identity (to be denoted by ); it is defined by for each . If is an arbitrary permutation, then or, in other words, multiplication by leaves every permutation unaffected. The proof is straightforward; for every we have and

The permutation behaves, from the point of view of multiplication, like the number . In analogy with the usual numerical convention, the zero-th power of every permutation is defined by writing .

If is an arbitrary permutation, then there exists a permutation (to be denoted by ) such that To define , where, of course, , find the unique such that , and write ; the validity of (3) is an immediate consequence of the definitions. The permutation is called the inverse of .

Let be the set of all permutations of the integers between and . What we have proved so far is that an operation of multiplication can be defined for the elements of so that (1) multiplication is associative, (2) there exists an identity element, that is, an element such that multiplication by it leaves every element of fixed, and (3) every element has an inverse, that is, an element whose product with the given one is the identity. A set satisfying (1)–(3) is called a group with respect to the concept of product that those conditions refer to; the set , in particular, is called the symmetric group of degree . Observe that the integers could be replaced by any distinct objects without affecting any of the concepts defined above; the change would be merely a notational matter.