Substitutional Analysis

PREFACE

IN the preparation of this book, I have been much indebted to various colleagues and friends. In particular I have received much helpful advice and constructive criticism over a period of years from Professor H. W. Turnbull, F.R.S., and Dr. W. Ledermann, both of whom have also assisted me in proof reading. I also wish to express my grateful thanks to Professor Sir Edmund Whittaker, F.R.S., and the Edinburgh University Press for their cooperation and invaluable assistance in the production of the book.

D. E. RUTHERFORD

August 1947

INTRODUCTION

THE purpose of this book is to give an account of the methods employed by Alfred Young in his reduction of the symmetric group and to describe the more important results achieved by him.

The problem which first attracted Young’s attention and which initiated the theory developed by him was that of solving certain substitutional equations which arose in his study of the Theory of Invariants. Although this initial problem was never far from his mind, his researches led him to study problems whose significance was deeper than he originally suspected. The keystone of these was the reduction of the symmetric group to its irreducible representations and the presentation of these representations in an explicit form. His published researches on these subjects, extending from 1900 to 1935, reveal some interesting facts. Most remarkable perhaps is the gap of twenty-five years between the second paper in 1902 and the third in 1927. In the first two papers Young had introduced the concept of a tableau which is so fundamental in the subsequent theory and had achieved some interesting results. It seems fairly certain that this brilliant inspiration was arrived at by a close study of the Gordan–Capelli series in the Theory of Invariants. This is borne out by the fact that the first use he made of his newly forged tool was its application to the Gordan–Capelli series.

In the introduction to his third paper Young writes: "When writing the two former papers I suffered from the disadvantage of being unacquainted with the closely related researches of the late Prof. Frobenius, published in the Berliner Sitzungsberichte, and beginning with ‘Ueber Gruppencharaktere’, 1896; a lucid and more elementary exposition of the main features of Frobenius’s theory of group characters was given by Schur". It is uncertain at what date Young’s attention was drawn to the work of Frobenius and Schur, but it is certain that their papers made a great impression on him and spurred him on to develop his own approach to the subject. To enable him to assimilate the papers of Frobenius and Schur he undertook a study of the German language. When one remembers in addition that Young was not a professional mathematician but a country clergyman with numerous clerical duties, the gap of twenty-five years between his second and third papers is not so surprising.

The third paper, when it appeared, was not so much an application of the work of Frobenius and Schur to Young’s previous work as a new and valuable approach to the construction of the irreducible representations of the symmetric group. The essential feature of this new development is the selection from all possible tableaux of a sub-system of what are called standard tableaux. The results achieved in this paper enable certain types of substitutionalequations to be reduced to a system of matrix equations. These matrix equations can in general be solved, although the manipulation in some cases may be enormous.

The fourth paper continues the general development of the third and provides a recipe for writing down the matrices of the natural irreducible representations of the symmetric group. Associated with any irreducible representation there is an infinite number of equivalent representations of which the natural representation is only one. Two others of particular importance, the semi-normal representation and the orthogonal representation, are characterised by the peculiar nature of the invariant quadratics associated with them. These two are obtained in Young’s sixth paper, and the theory is extended still further in the eighth paper.

The fifth paper is concerned with the hyperoctahedral group. This group is treated in much the same way as the symmetric group.

Most of the papers mentioned above have large sections devoted to the applications of the theory to the theory of invariants, and certain other papers listed in the Bibliography on page 101 are exclusively devoted to these topics. These applications, however, are somewhat technical in character and will not be treated in this book. The reader who is interested in these applications should also consult the recent papers of P. G. Molenaar.

As has so frequently happened in other branches of mathematics, the development of the theory of substitutional analysis necessitated from time to time changes in the notation employed. The lack of a comprehensive and systematic survey of Young’s work using a unified notation throughout explains to some extent the comparative neglect which has been accorded to Young’s researches by his contemporaries. In fact, one might say that only two significant contributions have so far been made by other authors to the substitutional theory initiated by Young. The first of these was contained in an oral remark made by von Neumann to van der Waerden and is published in the latter’s Moderne Algebra, vol. 2. This short theorem is the link which connects Young’s substitutional analysis with the Ideal-theory of Abstract Algebra. It also affords a means of simplifying some of Young’s more intricate proofs. The other work mentioned is a paper published by R. M. Thrall in 1941. Adopting the point of view of abstract algebra, Thrall derives Young’s orthogonal representation directly and thereby eliminates a great mass of elaborate detail which Young found necessary in constructing the orthogonal representation from the natural one.

The discoveries of Frobenius and Schur are not without significance in the theory under consideration. Indeed their results embody many of those of Young. The two theories may be regarded as parallel attacks on the same problem, but in this book the emphasis will be laid on the calculus of tableaux as applied to the symmetric group, and this particular aspect of the subject is peculiar to Young’s work and to that of von Neumann, Robinson and Thrall.

Likewise there have been several successful attempts, notably those of Weyl, Murnaghan and D. E. Littlewood, to relate Young’s work to other branches of Modern Algebra. These, however, have already been expounded by their several authors and will not be enlarged upon here.

In this book it was considered desirable to expound the subject in terms of Young’s mathematical language because in this way the theory can be studied by a reader possessing no previous knowledge of the subject apart from those portions of the Theory of Groups and the Theory of Matrices which are familiar to all mathematicians, and because in this way only can the individuality and genius of Young be properly recognised. Nevertheless, the reader who is already familiar with Young’s writings will observe that the presentation here given varies considerably from that of Young. In some cases the order of development has been changed, and in consequence of this, many of the proofs given are new. It is hoped that these changes will contribute to the lucidity and beauty of the underlying theory. It will therefore be understood that the references in the text to Young’s work do not necessarily imply that the proof given is due to Young. While this is so in some cases, in others the reference is quoted only to show that the result in question was also obtained in whole or in part by Young. The references quoted in the text are given in an abridged form. The works cited are given in full in the Bibliography on page 101.

CHAPTER I

THE CALCULUS OF PERMUTATIONS

Argument. The n! possible permutations of n letters occupy a place of basic importance throughout this book. In this first chapter we shall describe some of their more interesting properties and shall introduce certain notations which will facilitate our investigations in later chapters. Most readers will find that much of this chapter is already familiar to them but they should nevertheless pay particular attention to the notations employed, especially in § 6 and § 7.

§ 1. Permutations

It is well known that there are n! different permutations which can be made on n letters. We shall call these letters z1 …, zn, but in most cases it will be more convenient to denote them by their suffixes only. To avoid ambiguity we shall use a special fount of type for this purpose and write z1 …, zn simply as 1, …, n. Thus

where i1, …, in denote the letters 1, …, n in some order, denotes the permutation which changes the letter 1 into the letter i1 and so on. There is no particular reason why the columns of this permutation should be written in any special order. The same permutation might be denoted by

or, more generally, by

where k1, …, kn are the letters 1, …, n in some order. Greek letters σ, τ, … will frequently be employed to denote permutations in cases where the above more precise notation is unnecessary. In particular we shall write

throughout this book, where denotes the identical permutation.

In Group Theory these permutations are considered as elements which have an independent existence, but for many of our purposes they must be thought of as operators which are applicable to functions of