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 \(1\) and \(k\) (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 \(\pi\) is one-to-one means, of course, that if \(\pi(1), \ldots, \pi(k)\) are the integers that \(\pi\) assigns to \(1, \ldots, k\) , respectively, then \(\pi(i) = \pi(j)\) can happen only in case \(i = j\) . Since this implies that both the sets \(\{1, \ldots, k\}\) and \(\{\pi(1), \ldots, \pi(k)\}\) consist of exactly \(k\) elements, it follows that they consist of exactly the same elements. From this, in turn, we infer that a permutation \(\pi\) of the set \(\{1, \ldots, k\}\) maps that set onto itself, that is, that if \(1 \leq j \leq k\) , then there exists at least one \(i\) (and, in fact, exactly one) such that \(\pi(i) = j\) . The total number of the integers under consideration, namely, \(k\) , 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 \(\sigma\) and \(\tau\) are arbitrary permutations, a permutation (to be denoted by \(\sigma \tau\) ) can be defined by writing \[(\sigma \tau)(i) = \sigma(\tau(i))\] for each \(i\) . To prove that \(\sigma \tau\) is indeed a permutation, observe that if \((\sigma \tau)(i) = (\sigma \tau)(j)\) , then \(\tau(i) = \tau(j)\) (since \(\sigma\) is one-to-one), and therefore \(i = j\) (since \(\tau\) is one-to-one). The permutation \(\sigma \tau\) is called the product of the permutations \(\sigma\) and \(\tau\) . To say that the order is important. In general \(\sigma \tau \neq \tau \sigma\) , or, in other words, permutation multiplication is not commutative.

Multiplication of permutations is associative; that is, if \(\pi\) , \(\sigma\) , and \(\tau\) are permutations, then \[(\pi \sigma) \tau = \pi (\sigma \tau). \tag{1}\] To prove this, we must show that \[((\pi \sigma) \tau)(i) = (\pi (\sigma \tau))(i)\] for every \(i\) . The proof consists of several applications of the definition of product, as follows: \[((\pi \sigma) \tau)(i) = (\pi \sigma)(\tau(i)) = \pi(\sigma(\tau(i))),\] and \[(\pi (\sigma \tau))(i) = \pi((\sigma \tau)(i)) = \pi(\sigma(\tau(i))).\] 

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 \(\pi\) are defined inductively by writing \(\pi^1 = \pi\) and \(\pi^{p+1} = \pi \cdot \pi^p\) for all \(p = 1, 2, 3, \ldots\) ; the associative law implies that \(\pi^p \cdot \pi^q = \pi^{p+q}\) and \((\pi^p)^q = \pi^{pq}\) for all \(p\) and \(q\) . Observe that any two powers of a permutation commute with each other, that is, that \(\pi^p \cdot \pi^q = \pi^q \cdot \pi^p\) .

The simplest permutation is the identity (to be denoted by \(\epsilon\) ); it is defined by \(\epsilon(i) = i\) for each \(i\) . If \(\pi\) is an arbitrary permutation, then \[\epsilon \pi = \pi \epsilon = \pi, \tag{2}\] or, in other words, multiplication by \(\epsilon\) leaves every permutation unaffected. The proof is straightforward; for every \(i\) we have \[(\epsilon \pi)(i) = \epsilon(\pi(i)) = \pi(i)\] and \[(\pi \epsilon)(i) = \pi(\epsilon(i)) = \pi(i).\] 

The permutation \(\epsilon\) behaves, from the point of view of multiplication, like the number \(1\) . In analogy with the usual numerical convention, the zero-th power of every permutation \(\pi\) is defined by writing \(\pi^0 = \epsilon\) .

If \(\pi\) is an arbitrary permutation, then there exists a permutation (to be denoted by \(\pi^{-1}\) ) such that \[\pi^{-1} \pi = \pi \pi^{-1} = \epsilon. \tag{3}\] To define \(\pi^{-1}(j)\) , where, of course, \(1 \leq j \leq k\) , find the unique \(i\) such that \(\pi(i) = j\) , and write \(\pi^{-1}(j) = i\) ; the validity of (3) is an immediate consequence of the definitions. The permutation \(\pi^{-1}\) is called the inverse of \(\pi\) .

Let \(\mathcal{S}_k\) be the set of all permutations of the integers between \(1\) and \(k\) . What we have proved so far is that an operation of multiplication can be defined for the elements of \(\mathcal{S}_k\) 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 \(\mathcal{S}_k\) 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 \(\mathcal{S}_k\) , in particular, is called the symmetric group of degree \(k\) . Observe that the integers \(1, \ldots, k\) could be replaced by any \(k\) distinct objects without affecting any of the concepts defined above; the change would be merely a notational matter.