Search

We find the maximum number of orthogonal skewsymmetric anticommuting integer matrices of order n for each natural number n and relate this to finding free direct summands of certain generic projective modules. While studying composition of quadratic forms, Hurwitz [4] and Radon [6] considered families of orthogonal matrices {A1,3L , A,} satisfying the conditions (1) Ai= -At, i= 1, ,s (2) AiAj = -AjAi, i $ j. DEFINITION. (1) A family of orthogonal matrices satisfying (1) and (2) above will be called a Hurwitz-Radon (H-R)family. If n is a positive integer and n=2ab, b odd, then we write a=4c+d where O0d

(resp . partition) the edges of a graph G.We present bounds on m x {re(G)+cc(G)), max {cp(G)+cp(G)), mix {cc(G)ec(G))and mix(cp(G)cp(G))where the miximt are taken over all graphs G on n vertices and G is the complement of G in K„ . Several related open problems are also given

played (i.e., there are no ties). The outcome of the tournament may be represented by an n x n tournament matrix T where lij = 1 if player i defeats player j (symbolically, i -+ j) and zero otherwise. An n x n matrix P with nonnegative entries is a generalized tournament matrix if P + ptr = J I, where J denotes the matrix of l's and I the identity matrix. We interpret the entry Pij as the a priori probability that player i defeats player j when they meet (we assume Pii = 0 since no one plays against himself). Suppose the association organizing the tournament wishes to devise an equitable system of handicaps so as to neutralize the advantage strong players have over weak players. In ? 3 we discuss two general methods for doing this making use of various properties of generalized tournament matrices developed in ? 2. In the first method, each player bets a certain amount of his own money on each game he plays; in the second method the association awards a certain amount to the winner of each game. The bets and awards for each game are to depend on the two players involved. The association is to determine the amounts of the bets or awards in advance so that every player has the same expected net gain. There will be many fair systems in general and we consider the existence of systems satisfying various additional conditions. There are many ways in which a generalized tournament matrix P might arise; Pij could represent the frequency with which team i has beaten team j in some atheletic competition or Pi, might represent the frequency with which certain consumers prefer item i to itemj in a paired comparison test. One important problem is to determine some reasonable ranking of the n objects and, if possible, to obtain some quantitative measure of their relative merit. Several ranking methods have been proposed (see David [5]). The most obvious method is simply to rank the participants according to the number of games they have won. One well-known method is due to Zermelo, Bradley, Terry and Ford and another to Wei and Kendall. We obtain a new rationale for their methods as special cases of our betting and awards systems. Furthermore, in ? 3.3 we show that a parameter appearing in the Wei-Kendall method provides a natural measure of how evenly the participants are matched. Landau [12] has shown when there exists an ordinary tournament matrix with prescribed row sums; in ? 3.4 we obtain an analogous result for generalized tournament matrices. Some of the results in this paper were announced at the IFIP '68 Congress [161; some of these results were also obtained independently by Daniels [41.

The structure of the powers of a square matrix of Boolean zeros and ones has been studied extensively in one form or another in the last several years (see, e.g., [1], [2], [7]). These matrices occur naturally in the study of homogeneous M\1arkov chains. Similarly, infinite products of Boolean matrices occur in the study of inhomogeneous chains; for if we let a(l) = 1 when there is a positive probability of transition from state i to state j at the nth step and let a") = 0 otherwise, then (letting An = [a(n) ]) the ijth entry in A1 . .. An is 1 if and only if transition from state i at step one to state j in n steps occur with positive probability. Although a study of the structure of such products of Boolean matrices would be useful, little has been done in this direction. However, Paz [4] has obtained a graph-theoretic version of a condition on the An which ensures that the chain be weakly ergodic. The purpose of this note is to present an observation (suggested by the results in [5]) about infinite products which shows that some concepts and problems in the theory of powers have analogues for products which have apparently gone unnioticed. We shall discuss some of these at the close of this paper. THEOREM. If {A1 , A2 . , A,t, *I* } is a sequence of ;ltn X m0?n+l matrices ( with 1 ?< in < ?? ) over the Boolean algebra B2 of the two elements 0 and 1 andl at least one of the A,, has only finitely mnany distinct columns, then there is a finite set of in, X 1 matrices, { C1 , C2 , * * c,}, such that for all sufficiently large n: (a) each ci is a columnn of A1A2 ... An; (b) each column of A1A2 ... A,, is a linear coinbination of the ci . For example, if each Ai is a 2 X 2 Boolean matrix of zeros and ones, then