”‘— CONTRIBUTIONS TO THE THEORY AND CONSTRUCTION OF PARTIALLY BALANCED ARRAYS Thesis for the Degree of Ph. D“ MICHIGAN STATE UNIVERSITY JOHN ARTHUR RAFT ER 1971 - .WM. Date 0-7639 This is to certify that the thesis entitled CONTRIBUTIONS TO THE THEORY AND CONSTRUCTION OF PARTIALLY BALANCED ARRAYS presented by John Arthur Rafter has been accepted towards fulfillment of the requirements for Ph.D. degreein Statistics and Probability 5%” Msjor professor August 3; 1971 91132443?" . Michigan State . University. ABSTRACT CONTRIBUTIONS TO THE THEORY AND CONSTRUCTION OF PARTIALLY BALANCED ARRAYS BY John Arthur Rafter A partially balanced array (PBA) (m,N,s,t) of 8 levels, m constraints, and strength t with index set As,t = {x(x1,...,xt)|xi E {O,l,...,s-l}, i = 1,...,t] is an (m X N) matrix with entires from a set of 5 elements such that in every (t X N) submatrix each of the possible st distinct (t x l) vectors, (x1,...,xt)', occurs as a column x(x1,...,xt) times. The PBA can serve as a design for a fractional factorial experiment with m factors each occurring at 3 levels, when the effect of N treatments is under investigation. If the PBA is of strength t = 2n, all interactions involving u or fewer factors are estimable, assuming there is no interaction of more than u factors. If t = 2u + 1, all interactions involving u or fewer factors can be estimated even if interactions of u + 1 factors are present. In addition, the PBA is a "balanced" design in the sense that the resulting variance-covariance matrix of the estimators is invariant under a permutation of the factor symbols. In Chapter I, the analysis of a PBA is given for the special case of s = t = 2. The analysis of the general EBA is a straight- forward generalization. John Arthur Rafter One problem of interest for PBA's is to determine the maximum possible number of constraints for a given N,s,t and A In s,t' Chapter II, it is shown that, for any PBA, m s N. In the event that s = t = 2, better bounds are derived when pi > pouz, pi = pouz, and ”1 = 1. Also, a general result is given which is useful in finding bounds in other cases. In each instance, it is shown that the bounds are attainable. Next, an iterative bound on the maximum number of constraints of a PBA of strength t is given. This depends on the maximum number of constraints for a PBA of strength t-l. Finally, it is shown that the bounds obtained for a PBA in two symbols can be useful for arrays in more than two symbols. Moreover, the bounds are shown to be attainable in certain cases. The first result of Chapter III is a simple set of necessary and sufficient conditions for the existence of a PBA (t+l,N,2,t). These conditions are employed to give a method of construction of a PBA (m,2N,2,t+1) using a PBA (m,N,2,t) when t = 2u. Further- more, when t = 2, conditions are given under which an m+lSt row can be added to the constructed array, and a necessary and sufficient condition for m+l to be the maximum possible number of rows is given. The final result of Chapter III is the construction of a PBA (m,N,s,2) from a PBA (v,b,2,2) with index set {b-2r+1,r-l,l}, where m = r, N = b-r, s = fl, 740,0) = b-r-(s-1)(2r-s-l), b 1:'°°:S'1)a and A(1’j) = 1 (iaj = 1a°°°,5'1)' No.1) = r-8 (i The array (m,N,s,2) is shown to have the maximum possible number of constraints. John Arthur Rafter Chapter IV is devoted to the relation of PBA's to other areas of mathematics. In the first section, the existence of certain PBA's is shown to be equivalent to certain Tactical Configurations. In the second section, conditions under which a PBA will give a strongly regular graph are investigated. In the final section, Hadamard matrices are used to construct PBA's. CONTRIBUTIONS TO THE THEORY AND CONSTRUCTION OF PARTIALLY BALANCED ARRAYS BY John Arthur Rafter A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR 0F PHIIDSOPHY Department of Statistics and Probability 1971 TO CAROLYN AND JOHNNY ii ACKNOWIEDGMENTS I wish to express my gratitude to Dr. Esther Seiden for her guidance and encouragement in the preparation of this manuscript. Her willingness to discuss any problem at any time is deeply appreciated. I would also like to express my gratitude to Noralee Barnes whose skillful typing has been of immeasurable help throughout the research for and preparation of this thesis. Also, I wish to thank Dr. Dennis Gilliland for his help in the final review of the manuscript. Finally, I wish to express my gratitude to the National Science Foundation and to the Department of Statistics and Proba- bility, Michigan State University for their financial support during my stay at Michigan State University. iii TABLE OF CONTENTS Chapter Page I MALYSIS . ........ 0 ...... ........ ............ .00. 1 1.1 Introduction ..... .......... ......... ....... 1 1.2 Factorial Designs .......................... 1 1.3 Partially Balanced Arrays .................. 6 1.4 Analysis of a PBA of Strength 2 .... ........ 8 II SOME BOUNDS ON THE MAXIMUM.NUMBER OF CONSTRAINTS 13 2.1 Definition and Notation . ........... . ....... 13 2.2 PrOperties ............. ..... . .............. l4 2 .3 Diophant ine Equations . . C C . . . . . . . . . . . . . . . . . . 19 2.4 Bounds - PBA'S (m,N,2,2) .. ..... . .......... 24 2.5 Bounds - General Case ....... ....... ........ 36 III CONSTRUQION ....0............................... 39 3.1 Construction of PBA'S of Strength t + 1 from PBA's of Strength t .................. 39 3.2 Construction of PBA'S of Strength 2 in 3 Symbols from PBA's of Strength 2 in Two symbOIS ..................................O. 52 IV RELATION TO OTHER AREAS OF MATHEMATICS ...... .... 56 4.1 Tactical Configurations .................... 56 4 I 2 Graph Theory 0 O . . . . . . . . O O . . . O ..... . . . O O . . . . . 62 4.3 Hadamard Matrices . . . . . O . . . O . .......... . . O O . 71 BIBLIMRAHIY .0................ ........ ...0. ..... 76 iv CHAPTER I ANALYSIS 1.1 INTRODUCTION The basic principles of the subject of Design of Experiments were first presented by R.A. Fisher (see Fisher (1960)). Since that time a great number of researchers in many different disciplines have contributed to the development of the subject. Designs are called two dimensional or multi-dimensional according as they control variation in one or more than one direc- tion. Balanced incomplete block designs introduced by Yates (1936) and partially balanced incomplete block designs studied for the first time by Bose and Nair (1939) are two of the many designs of the first kind. Latin square, Youden square, and lattice square designs are a few of the second kind. In this work, we will be concerned with the existence and properties of a class of designs of the first kind called partially balanced arrays. Moreover, since once a design has been constructed it must be analyzed, we will indicate in this first chapter how one might perform the analysis of a partially balanced array of strength 2. 1 .2 FACTORIAL DESIGNS In experimental design, the variables an experimenter controls are commonly called FACTORS. The number of forms or categories of a factor appearing in an experiment is called the number of IEVELS of that factor. A particular combination with one level from each factor is a TREATMENT. If all possible treatments, or a definite portion of them,is cf interest,the experiment is called a FACTORIAL experiment. A factor can be QUANTITATIVE, such as different temperatures or different doses of a drug, or it can be QUALITATIVE, such as dif- ferent methods of testing or different chemical solutions. There is usually no natural order established among the different levels of a qualitative factor, but the different levels of a quantitative factor correspond to well-defined values of some numerical quantity. In a factorial design, if all possible treatments are included, the experiment is called a COMPLETE FACTORIAL. If repeated measure- ments or observations are made for each treatment, it is called FACTORIA1.WITH REPLICATES. If a complete factorial design has the same number of replicates, every level of a factor or every combina- tion of levels of any given number of factors appears the same number of times, and the design is said to be BAIANCED. Furthermore, the levels of one factor occur with each of the levels of any other factor with equal frequency, and the design is said to be ORTHOGONAL. Suppose a characteristic under study is affected by several factors F1,F2,...,Fm, where each factor can assume two or more different levels. For example, let Fi assume si levels i = 1,...,m. Clearly there are ...-sm possible treatments. $1.82. In case all factors assume the same number of levels,s, (i.e. s 31, i = 1,...,m), we call the design SYMMETRIC. In this case, a complete factorial design will consist of all possible sm m-tuples of 5 elements. It will be called a COMPLETE sm DESIGN. The effect of a treatment in a factorial design is in general regarded as the sum of an over-all mean, u, the effects of the m factors, and the effects of interactions of all orders among these factors. For example, in a 2m factorial design, the 2“1 treatments provide independent minimum variance estimates of the general mean and of the 2m - 1 effects: m main effects .Eiglll 2-factor interaction effects 919:%?§9'2)- 3-factor interaction effects m(m- 1) (m-Z) . . .(m-h+l) h! h-factor interaction effects and a single m factor interaction effect. In a complete factorial design the required number of measure- ments is often beyond the resources of the investigator; or it is not feasible to carry out; or it gives more precision in the estimates of the main effects than necessary; or estimates of higher-order interaction effects are of less interest. For example, in the above 2m design if m = 8, each main effect is an average over 128 combina- tions of the other factors. These considerations have given rise to the use of confounding and fractional replication of complete factorial designs. The general theory of confounding in sm factorial designs was derived by Bose and Kishen (1940) and Bose (1947). This was done . m . . . . by putting the s factorial level-combinations (treatments) into l-to-l correSpondence with the 8m points of the m-dimensional finite Euclidean geometry EG(m,s), based on the finite field GF(s). ’The 3 levels were taken to be in l-to-l correSpondence with the elements of GF(s). Using these correspondences and various other properties and features of EC(m,s) and the associated finite projective geometry PG(m-l,s), the results were obtained. This work was continued by Bose and others to include the theory of fractionally replicated designs of the type sm- , obtained by taking the sm"k level—combinations satisfying a set of k appropriately chosen linear equations over GF(s). The equations were chosen so as to obtain a fractionally replicated design with the pro- perty that all the n-factor and lower order interactions are estimable, assuming that the remaining higher order effects are zero. Such a design is said to be of RESOLUTION 2n+1 (see Box and Hunter (1961)). A design to estimate the n-factor and lower order effects, assuming that (n+l)-factor interactions may be non-zero and interactions of higher order are zero, is said to be of resolution 2n + 2. Consider a 1;. replication of a complete Sm factorial S . m-k . . dealgn, where the 5 treatments chosen satisfy the above mentioned . . m-k linear equations. These treatments can be represented by a m x 3 matrix. Furthermore, it can be shown that this matrix is an orthogonal array of strength t. An orthogonal array (m,N,s,t) of 5 levels, m constraints, strength t, and index 1 is a m x N matrix with entries from a It is not true that every orthogonal array can be obtained as a solution of a set of linear equations of the kind mentioned above. set S of 5 elements, 3 2 2, such that each t X N submatrix contains all possible t X 1 column vectors of S each repeated A times. Orthogonal arrays were first defined and studied by Rao (1947, 1950). Their importance, which was suggested above, derives from the fact that a necessary and sufficient condition that a fraction be of resolution (t + l), where the estimates of various parameters are mutually uncorrelated, is that it be an orthogonal array of strength t. Unfortunately, although orthogonal arrays lead to a reduction in the number of treatments necessary to estimate a given set of factors, this decrease is often not large enough, with the result that they become uneconomic to use. Thus if we insist that the fractional factorial design be such that the estimates are mutually uncorrelated, then, in general, the number of treatments will be much larger than the number of effects to be estimated, and experi- mental costs will rise. The obvious remedy to the situation is to drop the requirement that the estimates are mutually uncorrelated. Let L be the vector of parameters and L its estimate, and let V denote Var (L), the variance-covariance matrix of the estimates. Then if the estimates are mutually uncorrelated, V is a diagonal matrix. In view of the economic conditions discussed above, V must in general be taken to be non-diagonal. We can, however, restrict our attention to a certain class of patterned matrices and still reduce the number of treatments considerably. We shall call a matrix V "balanced" if it is a member of this class. In a fractional factorial design, the variance-covariance matrix of the estimators is called "balanced" if it is invariant under a permutation of the factor symbols. For example, let L' = (u; F1,...,Fm), then V is "balanced" if Var (F1), Cov (fi’fii) and Gov (fii’fij) areindependent of the indices i and j, i i j; i,j = 1,...,m. A fractional factorial design will be called "balanced" if its variance-covariance matrix is "balanced". Srivastava (1970) has indicated that a necessary and sufficient condition for a frac- tional factorial design of resolution t + l to be "balanced" is that it be a partially balanced array (PBA) of strength t. 1.3 PARTIALLY BALANCED ARRAYS A partially balanced array1 (PBA) A with parameters (m,N,2,t) and index set (p0,u1,...,ut) is an m x N matrix with elements 0 and 1 (say) such that in every t X N submatrix every vector containing 1 nonzero elements occurs pi times as a column. (To obtain a "balanced" fractional factorial design from A, simply take its columns as treatments to be included in the design.) It is clear that if pi = I, i = 0,...,t, then A is an orthogonal array of strength t. Thus a PBA is seen to be a generalization of an orthogonal array. Partially Balanced Arrays were first defined and studied by I.M. Chakravarti (1956, 1961, 1963). In addition, a substantial In view of the definition of "balanced" given above, these arrays might better be named Balanced Arrays. Indeed, Chopra and Srivastava have begun doing just that (see for example Srivastava and Chopra 0971a)). On the other hand, if by balanced one refers to the fact that every combination of levels of any given number of factors appears the same number of times, then there is a logical reason for calling them partially balanced arrays, since any combination of t or fewer factors appears the same number of times. In this paper we will refer to the arrays as Partially Balanced Arrays or even less formally as PBA's. amount of work has been done in this area by D.V. Chopra and J.N. Srivastava. We refer the interested reader to the Bibliography. The subject of arrays in general and PBA's in particular covers a rather wide sector of present combinatorial theory, with applications in areas like the construction of statistical experi- mental design, the theory of error-correcting and error-detecting codes, tactical configurations, and graph theory. A good deal of work has already been done in special branches of the general area of PBA's. For example, explicit studies on orthogonal arrays of strength 2 and 3 have been made by Bose and Bush (1952), and on Strength 4 by Seiden and Zemach (1966). Special prob- lems have been studied under other titles as well, such as mutually orthogonal Latin Squares and Hadamard matrices. Another important Special case of PBA's is the much studied area of balanced incomplete block (BIB) designs. The incidence matrix of a BIB design with parameters (v,b,r,k,x) is identical with a PBA in two symbols, v rows, b columns, and of strength 2, ”0 = b - 2r +‘X, p1 = r - 1 and p2 = A- Thus, every BIB design correSponds to a PBA, and conversely every PBA in two symbols and of strength 2 corresponds to a BIB design (with possibly unequal block size). When PBA's are considered as fractional factorial designs, they are preferable to orthogonal arrays. As mentioned above, orthogonal arrays involve an undesirably large number of treatments (columns). For example, an orthogonal array of strength two, six symbols and four rows would require at least 72 columns, but for the same situation, Chakarvarti (1961) has constructed a PBA with 42 columns. 1.4 ANALYSIS OF A PBA OF STRENGTH 2 The analysis given here is presented in a somewhat different form and in more generality by Bose and Srivastava (1964). Consider a complete 2m factorial experiment. Let Fi i - 1,...,m represent the ith factor and fi represent one of the two levels at which Fi can occur; for purposes of clarity this level will be called the second level. We will signify the first level by absence of the correSponding letter. Thus the treatment f f means 1 2 that factors F1 and F2 are at the second level and the remaining m - 2 factors are at the first level. The treatment which contains all factors at the first level is denoted by the symbol 1. When they refer to numbers, the letters Fi’ FiF etc. will represent, j’ FiFij’ respectively, the main effect of Fi’ the first order interaction of F1 and Fj, the second order interaction of Fi’ Fj and Fk’ etc. It is very well known that each interaction can be expressed as a linear contrast of all treatments. For example, a mathematical . . . m . expreSSion for representing the contrasts in a general 2 factorial experiment is (f1 1.1)(f2 i l)...(fm’i_1), where "+" is taken for absence and "-" is taken for presence of the corresponding letter in the interaction under consideration, Let f denote the column vector of all treatments, where I _ . . . . f [l’fl’f2..., f1f2...’ 00., ... flfz...fm]. let F denote the column vector of F's in the same order where the first position represents the mean, u. Then we may represent the above mentioned contrasts in matrix notation as: (1.4.1) F = 6'f where (S'is a Zm'x 2m matrix of plus and minus ones, and any two rows 1 of 6' are orthogonal. Since ‘—a'66' = I m’ multiplying both sides 2 2 of (1.4.1) by 15'6 ' gives N (1.4.2) f = The matrix 6 is sometimes referred to as the Effect Matrix Let A = (m,N,2,2) be a PBA with index set {uo,u1,u2}. Each column of A represents a treatment. For a given column, if there is a one in row i, then the corresponding treatment will have factor i at the second level, and if there is a zero in row i, factor i will be at its first level. Let y be an N rowed column vector, .th . . . where the 1 entry in y represents the yield of the treatment which .th correSponds to the 1 column of A. Using A, we wish to estimate the mean and the m main effects under the assumption that no interactions of two or more factors are present. Thus F' = (B', 16) where B' = [p; F1,F2,...,Fm] and I 0 is a vector of all zeros. Let 6 be the matrix which contains the 0 first m + 1 columns of 6, then from equation (1.4.2) we have 2 It is seen from this equation that each entry in f corresponds to a row of 60. That is, 1 corresponds to the first row of 60, f1 to the second row, and so forth. Using this correspondence, we gen- erate an (N x m+1) matrix X. Consider the jth column of A. Then this column corresponds to a particular treatment, t (say). We take as the jth row of X the row in 60 which correSponds to treatment t. EXAMPLE: Let A = O O O l 1 1 where O l 1 O 0 l 0 l 0 1 0 (f3) (f2) (f2f3) (f1) (f1f3> (flfz) the letters in parentheses are the treatments represented by the = v = . . . columns. Then m 3, f [1, f1,f2,f3, f1f2,f1f3,f2f3, f1f2f3], I _ . B — [11" 171,172,173], 71 -1 -1 -1‘ (1) i1 1 -1 -1 (£1) ;1 -1 1 -1 (£2) 1 = '1 -1 -1 1 f 60 i ( 3) i1 1 1 -1 (flfz) 31 1 -1 1 (£153) :1 -1 1 1 (£253) 1 f d ‘1 l l 14 (f1 2f3) , an I 11 -1 -1 3 (f3) §1 -1 1 -1 (f2) x = 31 -1 1 1 (f2f3) ii 1 -1 -1 (£1) :1 1 -1 1 (f1f3) .1 1 1 -l (flf ) , where the L 3 2 treatments are given next to their corresponding row in 60 and X. Let us make the assumption that the application of the treat- ments represented by the columns of A is done using a completely randomized design with one replication per column. Thus we may assume that there are no block effects. We further assume that Var (y) = oZIN and that the effects are additive. The construc- tion of X then gives that the expected value of y, written E(y), is equal to l‘XB. 2m 11 The normal equations are 1. (1.4.3) m x'xE = x'y, N so that if (X'}()-1 exists, the least-square estimates are given by (1.4.4) B = 2m(x'x)‘1x'y. Consider X'X. We may label the rows and columns of X'X with the elements of 8 taken in order. Thus the first row and first column will be labeled with p, the second row and the second column with F1, and so forth. Let x(e1,e2) denote the element in X'X which stands at the intersection of the row correSponding to e1 and the column corresponding to e2, where c1 and e2 are two not necessarily distinct elements of 5. Following the proof of Theorem 3.1 in Bose and Srivastava (1964) one can show that X(u,Fi) = 11.2 - “'0 X(FiaFj) = “0 - 2u1 +'u2 i # j. Rt 3 = “,2 - “,0 and b = 1,10 - Zpl +112, then N a ... £1 (m+l x m+l) N b . xix = b . L—a b ' ° b N o -1 It is a straightforward calculation to find (X'X) . The interested reader may check to see that (X')()-'1 is given by the following. 12 r' 2 1‘ fil- (1 +§— (mq + m(m-1)r)) -§- «1 + (m-1>r> it; (x'X)'1 = a - ' - 1 LT §_(q + (m l)r)_][n (q r)Im +»er ! where jm is an m rowed column vector of ones Jm is an m X m matrix of ones Im is the m X m identity matrix 2 2 q = N - a (m—l) +-(m-2)Nb and (N2 - azm + (m-1)Nb)(N-b) _ (Nb - a2) 1‘ = o (N2 - 32m + (m-l)Nb)(N-b) The above can also be used to obtain 3:, the sum of squares due to error. Indeed (1.4.5) S: = y'y - Y'XB- The number of degrees of freedom for error is N - (m+l). The expressions (1.4.3) and (1.4.5) can be used, for example, to carry out t-tests for hypotheses that any individual effect is zero. CHAPTER II SOME BOUNDS ON THE MAXIMUM NUMBER OF CONSTRAINTS 2.1 DEFINITION AND NOTATION DEFINITION 2.1.1: Let A (aij) be an m X N matrix, where the elements aij of A are symbols O,1,2,...,s-l. Con— sider the st (1 X t) vectors, X' = (x1,...,xt), which can be formed where xi = 0,1,...,s-l; i = 1,...,t, and associate with each (t x 1) vector X a positive integer x(x1,...,xt), which is in- variant under permutations of (x1,...,xt). If for every t-rowed submatrix of A the st distinct (t X l) vectors X occur as columns x(x1,...,xt) times, then the matrix A is called a partially balanced array (PBA) of strength t in N assemblies with m constraints (factors), 8 symbols (levels) and the specified x(xl,...,xt) parameters. When x(x1,...,xt) = A for all (x1,...,xt), A is called an orthogonal array of index A- The set of all 1(x1,...,xt)'s of an array of strength t in 3 symbols will be called the index set of the array and will be denoted by As,t° The array A will be represented as the PBA (m,N,s,t) with index set AS t' 3 In view of the fact that x(x1,...,xt) is invariant under i1,iz,...,ir permutations of (x1,...,xt), we will denote by A x the X1, 2,...,Xr number of repetitions of a fixed column of any t X N subarray of A, where the column contains i x ' ' x 's,... and i x 's. 13 14 r (xj = O,l,...,s-l, 21-1 ij = t, r = min {s,t}). . o In case 3 = 2, we will denote A; by uét),...,xg-:’l by 9 nit),..., and A: by nit). Where no ambiguity can arise, we will (t) i omit the superscript t from u and write simply pi. Clearly, pi is the number of times a fixed column containing i ones occurs in any t X N submatrix of A. Finally, we will refer to a t X 1 column as a t-tuple. In view of the above we have DEFINITION 2.1.2: (1) Let r = min {s,t}, then 11,...,ir As,t = {kx1’°'°’xr xj = O,l,...,s-l, ij = O,l,...,t, where j = 1,...,r and Z? i = t.} J=1 j (ii) A2,t = {nili = 0,...,t) . 2.2 PROPERTIES PROPERTY 2.2.1: Let AAst! denote the number of elements in As t° Then, for a PBA of strength t in 5 symbols, ’ s+t-l =( t \A ) . 5,11 Proof: The number of elements in As,t corresponds to the number of distinct combinations of 3 elements taken t at a time, where an element may be repeated O,l,...,t times in a given combina- tion, and order is not a factor. Let the 5 elements correspond to 3 cells and the t possible places in a t-tuple to t indistinguish- able objects. Then a distinct "t-combination” can be formed by placing zero, one, or more objects into each of the 3 cells (i.e. corresponding 15 zero, one, or more of the t elements). We can represent 3 cells by the spaces between s + 1 bars. Such a representation must start and finish with a bar. Thus we have s - 1 bars and t objects to position. In other words, we have s - l + t Spaces to fill with s - 1 bars and t objects. This can be done in (8+t-1) ways. COROLLARY: |A2,x+1| = Ax,3‘ . _ x+2 _ x+2 _ Proof: ‘A2,x+ll - ( 2 ) ( x ) ‘Ax,3‘ . PROPERTY 2.2.2: Let A be a PBA (m,N,s,t) with index se . t A t S: t s m"< m, is a PBA with index set A . (m',N,s,t) does not exist, then the PBA (m,N,s,t) Any subarray of A, (m',N,s,t) with m' (m’N ,S,t-1) places available to each of the 8 rows, where Thus, if the PBA cannot exist. s,t) of strength t of strength (t)i1,i2+1,...,is .,x x1,x2,.. S (t)i1,...,it_1+l Proof: This follows directly from the definition. PROPERTY 2.2.3: Iet A be a PBA (m,N, with index set As t' Then A is a PBA 3 t-l, where (i) if s < t, 1 x x = A x x + A 1,..., s 1,..., S (t)i ,...,i +1 +...+ x 1 S ; or X1,...,XS (ii) if s 2 t, (t'1)i ,...,i - (t)i+1,’oo,i - A l t l = k l t l +. X1,...,xt-1 Xl’...,xt-1 (t)i1,...,it_1, 1 +...+ A ..,x x +.. X1" t-l’ t ..+ x x1,...,xt—1 (t)i1,...,it_1,l .+)\ s 0.0 X X1, 3 t-l’xs 16 where for j = t,t+1,...,s C {x1,...,x xj t-1}' Proof: It follows directly from the definition that A is also a PBA of strength t-l. Thus, we have only to show (i) and (ii). It is sufficient to show (ii) since (i) would follow from a similar argument. Consider a (t-l XN) subarray of A. A (t-l)-tuple con- tainin i x 's i x 's ... a d ' ' ‘ ' ' ' g 1 l , 2 2 , , n 1t_1 Xt-l s in fixed pOSitions can occur as a result of deleting an xj (j = 1,...,t-l) from a t-tuple containing the i s ,..., and i 's in the fixed positions 1 . 1 1 x1 3’ 12 x2 c-1 Xt-l and xj in the tth position. Also a (t-l)-tuple could occur by deleting an xj (j = t,...,s) from a t-tuple with i1 x1 s,..., and it-l xt_1's in the fixed positions and xj in the tth position. Thus (ii) follows. COROLLARY 1: Let A be a PBA (m,N,2,t) with A2 t = ’ {u§t)|i = 0,...,t}. Then A is a PBA of strength t-l, where (t-l) _ (t) (t). - = _ pi pi + p'i-hl’ 1 0,...,t 1. COROLLARY 2: Let A be a PBA (m,N,2,t). Then A is a PBA of strength 2, where (2) = c+1-2 t '2 (t) . _ 1 j=i (j_i)p’j 1 - 0,1,2 ' Proof: Apply Corollary 1 repeatedly. Consider a PBA (m,N,s,t). Let Ni (1 = O,l,...,s-l) stand for the number of i's in a given row of A. Then N1 is independent of the row of A which we choose. This follows from the repeated application of Property (2.2.3). 17 COROllARY 3: Let A be a PBA (m,N,2,t) with index set A2,t’ then (i) N0 = 2;}, (film?) (ii) N1 = 21:, (gin?) (iii) N = 23:0 (Em?) . Proof: (1) Consider a PBA in two symbols of strength two. Then the zeros in a given row must occur in 2-tuples with either a O 1 N0 = ”0 +-u1. In view of Corollary 2, for a PBA of strength t in zero or a one. There are ”0 (8)'s and p1 ( )'s so that two symbols ll A n v 4. (ii) As in (i) we see that Z I! 2 2 ”in“? 18 (iii) Since N = N +-N1, we have 0 t-l t-l (c) c c-1 (t) N zjgo (J. ) J +zJ=1 (j_1)11j = 113” + 2;: [(271) + (j_1)]u§t)+ uét) =HL(gt) +23: (gm?) +11?) M = t t (t) 2j___ (jmj . a+l b ), was used , a a Note that the well known relation, (b) + (b-l) = ( throughout the above proof. The above corollary can be generalized to PBA's with s > 2 symbols. However, the notation becomes overwhelming rather quickly. Consider the PBA (m,N,s,2) and let I} I = x i,j = O,l,...,s-l. 1.1 i,j Then _ 5-1 N. —Zj=o Aij 3 1 since 1 occurs in a row in common with j = O,l,...,s-l in some other row xij times. Also, 2:s-l s-l s-1 1 i=0 j=0 ij N=2i=0Ni=z To find Ni and N for an array with 3 symbols and of strength t > 2, one would need to apply Property 2.2.3, which is already quite involved. 19 2.3 DIOPHANTINE EQUATIONS In this section we will be concerned with a set diophantine equations, which form a set of necessary conditions for the existence of PBA's. These equations are given by LEMMA 2.3.1: In the PBA (m,N,2,t) with index set {u0,...,ut}, let n§i> be the number of i-dimensional columns which contain exactly j ones, i = t,...,m, j = 0,...,i. Then i-t+(, (:)<:>u, = Zj=t (i> = 1(u1 +'u2) ; (iii) z;=o “(1) = ”0 + 2e1 +-u2 , 1 = 2,...,m. Proof: (i) We would like to count all of the possible 2-tuples, (i), which can occur in 1 rows of A. We can choose two of the i rows in (i) ways, and since the number of (i)'s 1 in these two rows is ”2’ the total number of (1)'s is (;)u2. On the other hand, a column containing j ones will contribute 20 (2) (i)'3 to the total. Noting that the number of columns contain- ing j ones is n§i), we see that the total number of (i)'s is i j=i 1(1) also equal to zj=2 (2)nj zj=0 (2)nj . Thus, 1 j (i) _ i Zj=0 (2)nj - (2)p'2 ° (ii) This follows in the same manner as (i), where both sides are equal to the total number of ones in 1 rows of A. (iii) This follows, since both sides are equal to N, the number of columns of A. As an example of the usefulness of the above equations con- sider the following. THEOREM 2.3.3: Let A be a PBA (m,N,2,2) with index set {u0,u1,u2}. For m 2 3 we have . . . . . (3) = (3) g (1) pl 3 p0 +~u2 with equality if and only if n0 n3 0. (ii) Let pl = ”O + “2' Then m s 4 with equality if and only if p0 = p2. (iii) Let ”1 = no +-u2 and m = 4. Then A is a PBA of strength . . 3 3 2 3 2 3 3 With index set {us ) = 0, Mi ) = ué ), u; ) = #5 )a u; ) = 0]- . _ . . (3) = (3) _ . (1v) p1 — ”2 if and only if n1 3n3 . ”O — pl if and . (3) _ (3) only if n2 — 3n0 . Proof: (1) By Corollary 2.3.2, for i = 3 we see n2 + 3n3 3H2 n1 + 2n2 +3n3 3H1 +3p.2 n+n +n +n =u0+2p1+p2. Thus (1) n = 302 - 3n3 n = 3p1 + 3p2 - 2n2 “ 3n3 21 (2) = 311,1 - 31,12 +3n3 n0=p0+2u1+u2 -n1-n2-n3 (3) =“0'“‘1‘H"2““3 Since n0 2 0, the last equation gives O‘RO‘R1TR2'“3’ SO p1+n35p0+p2. Since n3 2 0, “I S pl + n3 5 ”0 +'u2. Clearly, if nO - n3 = 0, #1 = ”0 + p2. Conversely, suppose ”I = ”0 +-p2. Then, from equation (3) above, n0 = -n3. Since both n0 and n3 are non-negative, it follows that nO = -n3 = 0. (ii) Since n = = 0, any column of A can have at most n O 3 two zeros and two ones. Thus m s 4. Suppose m = 4, then by Corollary 2.3.2, (4) ___ (4) (4) _ (4) 12p,2 2n2 + 6n3 + 12n4 — 2n2 and = (4) (4) (4) (4) _ (4) 4(p.1 +'H2) n1 + 2n2 + 3n3 + 4n“ 2n2 so that 411.1 “I" 4,1,2 = 1292 or “1 = 2”2 ° Further, since p1 = ”O +-u2, it is clear that ”O = uz. Suppose ”0 = c = ”2 so that ”l = 2c, then A can be written as the juxtaposition of c arrays of the form 22 HHOO HOD-‘0 POOH OHHO OI—‘OH OOHH Since B is a PBA, the juxtaposition will be a PBA. (iii) Since B is a PBA of strength 3 with ”33) = 0 = u§3> 3 3 and Hi ) = a; ) = 1, the juxtaposition of “0 3'3 will be a PBA of strength 3 with the indicated index set. (3) _ (3) 1 ’ 3n3 (iv) That p1 = “2 if and only if n follows from equation (2) above. néB) = 3né3). Then equations (1) and (3) give Suppose 3H2 - 3n3 = 3H0 - Bul +3p,2 - 3n3 i.e. ”0 = pl. Now suppose p0 = ul, then, by (3), n0 = “2 - n3. Multiplying both sides by 3 gives 3nO = 3p - 3n by equation (1). 2 3 = “2’ The equations of Corollary 2.3.2 can be used to find other relations between the elements of the index set. For example, for m 2 4, one can show that Zul 3 min {3pc +~u2, “0 + 3u2}. Further- more, the equations can be generalized to arrays of strength higher than 2 and similar relations may be found. For example, for t = 3 and m 2 4 (3 (3) (3) . _ . (4) __ (4) .- HZ ) s ul +-u3 Wlth equality iff nO — n4 _ 0 #1 S ”0 + ”2 ) with equality iff nO = n3 = 0 . And. for t = 4 with m 2 5, 4 4 4 (4 (4 , . . (5) _- (5) .- “i ) +'H§ ) 5 H6 ) +'u2 ) +'u4 ) With equality iff no — n5 _ S ugh) 5 #54) + ”24) with equality iff n55) = n; ) 23 4 4 4 . . . 5 S u; > 5 pi ) +-u§ ) With equality iff n: ) = n: > = O. A second example of the usefulness of the diophantine equa- tions of Corollary 2.3.2 is that their solutions are useful in the construction of PBA's. EXAMPLE 2.3.4: We wish to construct a PBA (m,5,2,2) with index set {no = 2, p1 = 1, ”2 = l} with as many rows as possible. (i) Without loss of generality we can write down the first two rows as O O 0 l l O 1 (ii) For i = 3, the equations in Corollary 2.3.2 are The solutions are n n n n (b) 2 O 3 O The resulting arrays can be written as (a) (b) 000 0 0 1 CPD 1 l 0 l 0 1 GOO 000 0 l l 1 O 1 l l 0 so that, for example, in (a) there is one column with three ones, three columns with one one, and one column with no ones. (iii) For i 4, the equations are 6 = n +‘3n + 6n 2 3 4 8 = 111 +2n2 + 3n3 + 4n4 5 = no +-n1 + n2 + n3 + n4 . 24 The solutions are n n n n n (d) l 2 O 2 0 . Solution (d) is not compatible with solutions (a) and (b), and solution (c) is not compatible with solution (b). But using solu- tion (a) we find (c) O O O 1 1 0 0 1 0 l O l O 0 1 l O 0 O 1 (iv) For i = 5, the equations are 10 = n2 +3n3 + 6n4 + lOn5 10 = n1 + 2n2 + 3n3 + 4n4 + 5n5 5 = no +n1 + n2 + n3 +-n4 +n5 . The only solution of these equations is nO = 1, n1 = 1, n2 = 1, r13 = 1, n4 = l, and n5 = 0. But this is incompatible with (c) above. Thus the maximum possible value of m is 4, and the PBA (4,5,2,2) with index {2,1,1} is given by (c). 2.4 BOUNDS - PBA's (m,NJLZ) Suppose we are given a PBA, A, with index set AS t' Then 9 the elements of As,t are fixed numbers as are N,s, and t. In fact the only parameter which is not completely fixed is m, the number of constraints (rows) of the PBA. This is clear, since if A has m rows, the PBA obtained from A by deleting the last row is a PBA with the same N,s,t, and As,t (see Property 2.2.2). Moreover, it may be possible to add an m+lSt row to A and obtain a PBA with the same N,s,t, and As, . The problem is to determine t the conditions under which this can be done. A partial answer is 25 given in this section by determining some upper bounds on the value of m for certain PBA's. We start by showing that m s N for all PBA's. IEMMA 2.4.1: Let A be a PBA (m,N,2,t) with index set A2,t = {u§t)‘i = 0,...,t}. Then the eigenvalues of AA' are b +-mc with multiplicity one and b with multiplicity m - l, t-l t-2 (t) _ t t-2 (t) where b = 2j=1 (j_1)u.j c - Zj=2 (j-2)uj 2:33;: Recalling Corollary 2 of PrOperty 2.2.3, we recognize b as the number of times the 2-tup1e (2) (or (3)) occurs in any two rows of A. Likewise, c is the number of times the 2-tuple (1) occurs in any two rows of A. By simple matrix multiplication we see that I .. (1) AA b Im +-c Jm , where Im is the identity matrix and Jm is an m X m matrix of all ones. Consider an orthogonal transformation which diagonalizes Jm. Multiplying the right side of (l) by this transformation gives FRI .. 0] m X m 0 . b I + c ' ' m C . (,0 . .. 03 The eigenvalues of this are b + cm with multiplicity one and b with multiplicity m-l. Hence, AA' has the indicated eigenvalues with the indicated multiplicities. It is well known that AA' and A'A have the same non- zero eigenvalues with the same multiplicities. Thus A'A, which is N X N, has the above given m positive eigenvalues, and it follows 26 that N 2 m. Now, suppose A is a PBA (m,N,s,t) with index As,t° We replace each non-zero element in A with a one, so that A becomes a PBA in two symbols, 0 and 1. Then the above gives that m s N. We have thus shown that m S‘N for any PBA. THEOREM 2.4.2: Let A be a PBA (m,N,2,2) with index set 2 {poaul’u2}' If “'1 > “OF-1'2, then N pl 2 S “1 ‘ p‘0”2 “IS with equality if and only if the number of ones in each column of A. is the same- Proof: Let nj be the number of columns of A which con- tain j ones, and let 7 l J...— 2m 'n N j=1Jj' Since nj 2 0 for all j, it follows that m - 2 m 2 - 2 0s.(‘-'n.=2. 'n.-N‘ 21:0 J J) J J=1 J J (1) Using Corollary 2.3.2, we see that T _ E J - NQ‘LI + “'2) and m 2 ° = -1 + + Thus 1 2 2 2 m 2 = m ”2 +mu1 ' fi_'(”1 +P2) ° Since m > O 27 m 2 0Sm2+u1-§(ul+u2) and N1» 1 2 2 mg,- (1114's,) --N-—) $111 . 2 "1((11'1 + ”2) ' NHZ) S NHI ’ 2 m4», - 110112) 3 N111 . . . 2 Since by hypotheSis pl - ”OHZ > 0 , N ul mS'—2—— o p‘1 ' p'o“2 Suppose that the number of ones in each column of A is m =41 (k n 1321-4 1% N 1.) ”- the same and equal to k. Then 3 = Furthermore, 7 7 2 (J ‘ J) n_ = 0 s m 72 2j=1 (j - J) nj J so that, replacing s with in the first part of this proof gives, m = N “I 2 0 H1 ' ”0H2 Suppose N m "' 2 0 Then, replacing s with = in the first part of this proof and following the argument in reverse order, it is clear that m . 7 2 _ . -. 2 . D U 7 2 Thus (3 - 3) nj = O for each 3 = 0,...,m. Since (j - j) = 0 if and only if j = j, it follows that nj = O for all j # j and 28 that n_ = N, so that the number of ones in each column of A is j - the same and equal to j. EXAMPLE: Consider the PBA (m,6,2,2) with index set {no = 1, p1 = 2, ”2 = 1}. Then by the theorem 4-1 The array is given by O O 0 1 l l 0 1 l O 0 l l O 1 O 1 0 l l O l O 0 As mentioned in Section 1.3, a PBA with an equal number of ones per column (say k) is the incidence matrix of a balanced in- complete block (BIB) design. COROLLARY 2.4.3: A PBA (m,N,2,t) which is also the incidence matrix of a BIB design (m,N,r,k,x) with k < m has the maximum possible number of rows. 2:22;; ‘We need only show that m is a maximum.when the PBA is considered to be of strength 2. As an array of strength 2, the PBA has index set. {no = N - 2r +.x’ “I = r - x, ”2 = A}. 2 2 Thus “.1 - (1.01.12 = (r - A) - )(m - 2r '1' A) = r2 - AN = r2 - )t -:—m = E(rk - )(m) N m(r'7\)>oa where we have used the well known results that for a BIB design, Nk = rm and r(k-l) = x(m-1). Now, since the array has k ones 29 in each column, Theorem 2.4.2 implies that m is the maximum number N u _ of rows possible. (Indeed —2—1— = bg—LL—Ll = m). 111 - 110112 3;; (r'k) The corollary implies the following interesting property. Let A be a PBA of strength t in 2 symbols. If, when A is con- sidered to be a PBA of strength 2, pi s uOuZ, then A cannot have the same number of ones in each column. This follows, since, if A bad k (say) ones in each column, the proof of the corollary would give pi > ”OHZ’ a contradiction. (In the above corollary and property we exclude the case m = k, which would mean ”0 = ul = O and ”2 = N.) THEOREM 2.4.4: Let A be a PBA (m,N,2,2) with index set {110,111,112}. If pi = “0,1,2, then m SN-l. EEQEEF With each column of A we associate a distinct variate. With the column of A, which contains x1,...,xm (xi - 0,1; 1 = 1,...,m) in this order, we associate the variate f(x1,...,xm). We consider certain linear functions of these N variates. Denote by 2 the summation over all columns of A. Then, thN we define the 0 stage function to be §f(x1,...,xm) , the sum of all the variates. Consider two number, c0 and c1, such that (1) ('10 'l' p1)co + (11.1 + 11.2)C1 = 0 and 2 2 (2) ”0 c0 +2p.1 coc1 +-u2 c1 — O . 30 Choose any row, r, of A. Corresponding to this choice, we can con- struct the linear function E ci(r)f(x1,...,xm) . In the column of A corresponding to the variate f(x1,...,xm), the symbol occurring in row r of the array is xr (0 or 1). In the linear function constructed, we make the coefficient of f(x1,...,xm) equal to C1 if xr = i, i = 0,1. The linear functions so defined are called first stage functions. Clearly, there are m first stage functions, one for each row of A. Provided c0 and c1 are not both zero, equation (1) above implies that the first stage functions are orthogonal to the 0th stage functions. Equation (2) implies that each first stage function is orthogonal to each of the other first stage functions. Thus, the m+l functions defined above are all mutually orthogonal and there- fore independent. Since the maximum number of independent linear functions of N variates is N, it follows that N 2 l+m or m s N-l. We now Show that not both c0 and c1 are zero. Equation (1) gives 1» +1» _ l 2 _ Co “‘0 + 111 C1 K C1 (saw Equation (2) gives 2 2 2 2 - 2 = c1(K 110) 111K c1 + CI 11.2 2 2 c1(Kp.O+p,2-2Kp.1) =0. 31 Thus, c1 = 0 as well as CO 2 . 2 as the following shows K no +-u2 - 2K ul if and only if “1 — pouz, 2 = 0, unless K ”O +~u2 = 2K pl. But so that by hypothesis there exist c and c not equal to zero. 0 1 2 K =K2 + LL1 “o “‘2 2 u +u a +u) iff 2p, ———-l 2 = p. 1 2 + p. 2 1 p0 +-u1 O (H +‘H ) 2 0 l ‘ff 2 ( + + - + )2 + + )2 3 2 2 2 2 . + = lff 2R1 + u‘1”0 u‘1“2 ”o“2 +2“‘0“1“”2 T ”o“2 , 2 lff 11-101) = 11011201) 0 2 - THEOREM 2.4.5: Let A be a PBA (m,N,2,2) with index set {p0,l,p2}. Then the maximun value of m is m' = max {p0,u2} + 2 and (m',N,2,2) exists. Proof: Without loss of generality, we write the first two rows of A as no “2 KM A O O 0 1 1 l O ... O 1 O l ... l . Since ”1 = l, the third row must have exactly one one in a column of A which has a zero in the first row of A. Call this column c1. Likewise, the third row must have exactly one one in a column of A which has a zero in the second row of A. Call this column c2. CASE 1: Suppose that c1 and c2 Then, without loss of generality, we write the first three rows of are different columns. 32 LL0 9‘2’1 r“’\‘“\ c1 C2 c3 ,r-’\~—\ o o o 1 1 1 1 o 1 o 1 1 1 o ... 1 1 o 1 ... 1 . In adding a fourth row, we note that there cannot be more than one one in the first “0 columns, else ”1.: 1 would be contradicted. Suppose there is one one in the first ”0 columns. Then, since ”1 = 1, there cannot be a one in column c1, c2, or c3. But this leaves only ”2 - 1 places in which to place ”2 ones. Thus, in the fourth row we must put zeros in the first columns and one H“0 zero and “2 +~1 ones in the last “2 +-2 columns. Suppose we place the zero in one of c1, c2, or c3 (c1 (g)'s occurring in the first and fourth rows of A is ”0 +11, a contradiction. It therefore follows that say). Then the number of the zero must be in a column which has ones in the first three rows. Using similar arguments, we can continue to add rows as long as there are columns containing all ones. A will thus have the form of ”0 columns of zeros and ”2 + 2 columns containing one 0 and the rest ones, where each row has exactly one zero in the last p2 + 2 columns. Clearly the number of rows of A is ”2 +’2. CASE 2: Suppose c and c are the same column. Then 1 2 without loss of generality, we write the first three rows of A as ““o'1 ”2 ’0 0‘ o o 1 ‘1 1‘ o o :1 o 1 1 ... (1 1 o o 1 ... 1 33 Using similar arguments to those used in case 1, we see that A has the first ”0 +-2 columns with one one and the rest zeros, where each row has exactly one one. The remaining ”2 columns contain all ones. Clearly, the number of rows of A is ”0 + 2. Since cases 1 and 2 are the only ones possible, the theorem follows. EXAMPLE: Recall Example 2.3.4 of Section 2.3. A is a PBA (4,5,2,2) with index set {2,1,1} and was shown to have the form 0 O 0 l l O 0 1 0 l O 1 O 0 1 l 0 0 O 1 . THEOREM 2.4.6: Let A be a PBA (m,N,2,2) with index set {u0,u1,u2}. If L is the number of ones in some column of A, we have 2 2 2 2 2 + {a (411.0“:2 - 4131 - “'0 + 2H1 " M2) . Egggfg Without loss of generality, we may assume that the first column of A contains L ones. Consider any two rows of the array. If the first column contains (3), it appears ”0 - l more times. Likewise, a (2) or a (3) appears p1 - l more times and a (1) appears ”2 - 1 more times. Since there are L ones in the first column, the number of ways to choose two rows so that the (8) is (";L). The number of ways to choose two rows so that the first column contains (2) or (3) is L(m-L), first column contains. and the number of ways to choose two rows so that the first column 34 contains (1) is (L). 1 2‘ Let T be the total number of 2-tup1es appearing in columns other than the first which are identical with the corresponding 2- tuple in the first column. Then T = (”o - 1>(mgf) +0»1 - 1>2 - 21:0 <2)f<1) . so that m i , _ _ m-L _ _ _ L zi=0<2>f(1> — (no 1)< 2 > + (pl 1>2(m a) + (u, 1)<,) , m . . . _ 2 or 21:0 1(1 - 1>£(1> - m (no - 1) - m(u0 - 1) + 2mL(u1 - no) 2 + L (1&0 ' 2111 + 112) +£(u0 - 112) In a similar manner we can show 111 (“'0 +141 - 1)(m '11) + (H1+H-2 - 1)!’ Also, clearly m zi=0 f(i) =N - 1 . i f(i), then, since f(i) 2 O for all i, For definition see, for example, Bose and Bush (1952). 35 o s 210(1 - E)2£(1) .2 . = 2:0 1 f(l) - (13%;)(210 i f(i))2 2 Thus, 0 S (N-1)[m (”0 - l) +mp,1 + 2mL(u1 - H ) O 2 2 2 +‘L (IJ'O "' 2H1 +152)?!" [4: (“'2 - “0) + 2 2 me,(p.2 - “0)(1-50 +131 ' 1) +m (“'0 +1J'1 " 1)] 2 2 = “1410112 - u, - uz) +m1m - 1) 2 + 2m(2u1 ' 2150142 + ”‘2 ' H1) 2 2 + L (AUOHZ - 41"]. - “'0 + 211-1 ' U2) COROLLARY 2.4.7: Let A be a PBA (m,N,2,2) with index set {u0,u1,u2} then: (N'l)p'1 2 (i) If L = O, m s 2 provided pl - “2(u0 - l) > 0 - -1) “'1 “2(1-50 (N'1)p'1 2 (ii) If L = m, m s 2 provided p1 - “0(u2 - l) > O . “‘1 ' “0(“2'D In the following, let 2 C1 “”0““2 '“1 ' ““2 “film ' 1) O I O l 2 3 2(2W1 ‘ 2%“2 + ”2 ' ”1) 2 C4 " 4in0““2 ' 4p‘1 ' ”o + 2“1 ‘ “2 ’ 2 2 so that 0 s m C1 +~m C2 +-mL C3 +'L C4 . 36 EXAMPLE: Let A be the PBA (m,9,2,2) with index {3,2,2}. Then C1 = 0, C = 16, C = 8, and C = 7, so that 2 3 4 0 5 16m - 8mL +'7L2 or 7&2 m S 8(1-2) ’ where since ”2 > 0, we take L so that 3 s L s m. The right side is minimized when L = 4. Thus, since the maximum value of m is a constant, 519;:7. 8(2) Indeed we can express A as follows. {> II C) c> c><3 c: c: G) <3 hi P‘ c> h' c> c: H O O H H O 0 rd C) F‘ C) C) F' min (mj) + l = mi + 1 (say), then by the proof of Theorem 2.5.1, Ai has at least mi + 1 rows in contradiction to the hypothesis that m1 is the maximum 38 number of rows of Ai' EXAMPLE: Consider the PBA. (m,10,3,2) with index set {2,1,1,2}. Then by Corollary 2.5.2 A0 = (m-1,5,2,2) with index set {2,1,1} A1 = (m-1,5,2,2) with index set {1,1,2}. The maximum possible number of rows for A0 is 4. The maximum possible number of rows for A is also 4. Thus, the array 1 can have at most 5 rows. We give the array as follows. 0 O O 0 O 1 1 1 1 1 O 0 O 1 1 0 O 1 1 l O O 1 O 1 O 1 O 1 1 O 1 O 0 1 O 1 1 0 1 1 O O O 1 O 1 l 1 O The bounds derived in Section 2.4 can also be useful when directly applied to PBA's of strength 2 in more than 2 symbols. For example, let A be the PBA (m,20,3,2) with 100 = 4, X01 = 3, 102 = 3, 111 = 1, 112 = l and, 122 = l. Replacing all nonzero elements in A with 1 gives a PBA (m,20,2,2) with ”O = 4, ”l = 6, ”2 = 4. By Theorem 2.4.2 m S %%§1% = 6. Thus A can have at most 6 rows. Indeed A can be expressed as follows: 0 0 O O O 0 0 O O 0 1 1 1 l l 2 2 2 2 2 0 O O O 1 1 1 2 2 2 O 0 O 1 2 O O O l 2 A = O 2 1 1 1 2 O 2 O O O O 2 O 1 O 2 1 O O 2 1 2 1 O O 1 2 O O 2 1 0 O O O O 0 2 l 2 1 1 O O O 2 O 1 2 O O 2 1 O 1 O 2 O O l 0 0 2 1 2 O O 1 2 2 1 O O O 2 l 0 O O CHAPTER 111 CONSTRUCTION We have already seen in Section 2.3 how one might go about constructing a PBA directly. In this chapter we will consider ways of constructing PBA'S of strength t in 8 symbols from arrays of strength t' S t in 3' symbols, where s' s s. 3.1 CONSTRUCTION OF PBA'S OF STRENGTH t + 1 FROM mA's OF STRENGTH t. THEOREM 3.1.1: Let A be a PBA (t+l,N,2,t) with index set A2 t = {ui|i = 0,...,t}. Consider the (t:1) possible distinct ’ (t+lxl) vectors which contain k ones. Then each of these vectors appears as a column of A the same number of times,mk (say). Moreover, “‘k = “'k “ "‘k+1’ where k = 0,...,t. Proof: Let (x1,...,xt+1)' be a column of A containing k ones, where each xi assumes the value 0 or 1. Let H-X-H-36- ,...,x contains (k+l) ones. Then, if xj = 0, (X1,...,xi,...,x t+1) * J Let n(x1,...,xt+1) .be the number of times the column containing ) appears. Finally, aSSume x = 1, x = 0. (X1"'°’xc+1 1 j 39 40 Consider the t-rowed array formed from A by excluding row j. Then, since A is of strength t, “(xl’ooo,Xi,ooo,xj-1,xj+1,ooo,xt+1) = uk 0 Thus, * (l) n(x1,...,xi,...,xj,...,xt+1) + n(x1,...,xi,...,xj,...,xt+l) — pk. Consider the t-rowed array formed from A by excluding row i. Then, since A is of strength t, * n(X1’°°"Xi-l’xi+l"°°’xj’°°°’xt+l) = pk. Thus, 2 * * + * _ () n(x1,...,Xi,.oo,Xj,.o.,Xt+1) “(X1,.oo,Xi,...,Xj,...,Xt+1)—p,k. Subtracting (2) from (1) gives _ * * n(x1,...,xi,...,xj,...,xt+l) — n(x1,...,xi,...,xj,...,xt+l). Proceeding in this manner, we can show that every column containing k ones must occur the same number of times, mk (say). Moreover, from (1) it is clear that or "’k = “'k " “1+1 ' PROPERTY 3.1.2: mk = pk - mk+1 for all k = 0,...,t if and only if 41 = j _ i _ j+l “‘k 231=o( 1) “’k-i-i + ( 1) mk+j+1’ k=0,...,t,j=0,..o,t'k. Proof: Setting j = O in = j _ i _ j+1 mk z31=0( 1) “‘k+i + ( 1) mk+j+1 gives rnk=“‘k'mk+1° Conversely, m - m and m m imply k = ”k k+l k+1 ' ”'k+1 ' k+2 "‘k = “k ' “H1 + mk+2° Proceeding in this way we find that = j _ i _ j+l “‘k zi=0( 1) p‘k+i + ( 1) mk+j+1 ’ k = o,...,: and j = 0,...,t-k. EXAMPLE: Let A beaPBA (m,N,2,2). Then Theorem 3.1.1 0 0 gives that, in every three rows of A, the 3-tup1es O , 1 , and l O l 0 each appear the same number of times, m1 (say). (m1 can vary 0 depending upon the three rows chosen.) Likewise, in every three 1 1 0 rows of A, the 3-tup1es l , 0 , and 1 each appear the same 0 1 1 number of times, m2 (say). Moreover, given three rows, Property 3.1.2 gives 42 Let A be given by O 0 0 O 1 1 l 0 O l 1 O O 1 0 1 1 O l O O 1 1 O O 0 0 1 . Then for rows 1, 2, and 3 m0 = 1, m1 = 1, m2 = 1, m3 = 0 , but for rows 1, 2, and 4 m0 = 0, m1 = 2, m2 = 0, m3 = 1 . Notice further that the above are the only two possible solutions of such that mi 2 O, i = 0,1,2,3. We next give a converse to Theorem 3.1.1. THEOREM 3.1.3: Given a set A = {ui‘i -= 0,...,t} of positive integers, a PBA (t+l,N,2,t) exists with A as its index set if there is a solution to the equations for i = 0,...,t, where m1 is a non-negative integer for all i. Proof: Without loss of generality, we can write down the st first t rows of the array. We add the t+1 row as follows. In the first t rows, there are columns containing k ones “'k in fixed positions. We put a zero in the t+lSt row of mk of these , st .. columns and a one in the t+l row of the rema1n1ng m of these k+l columns. Call the resulting array A. 43 To show A is a PBA, we must show that each choice of t-l . . St . . out of the first t rows together Wlth the t+l row satisfies the property that a column containing k ones occurs times. ”R Without loss of generality, we show this for the first t-l rows of A together with the t+lSt row. Let (x1,...,xt_1,xt+l) contain k ones. CASE 1: Suppose (x1,...,xt_1) contains k-l ones, then n(x1,...,xt_1,0,1) + n(x1,...,xt_1,l,1) m +-m (by construction) k k+1 “k (by hypothesis) , where the notation is as used in Theorem 3.1.1. Thus n(x1,...,xt_1,xt+1) = n(x1,...,xt-1,l) = uk' CASE 2: Suppose (x1,...,xt_1) contains k ones, then n(x1,...,x 0,0) + n(x1,...,x l O) t-l’ t-l’ ’ = "'k + mR+1 uk° Thus n(x1,...,xt_1,xt+1) = n(x1,...,xt_1,0) = pk . Since cases 1 and 2 exhaust the possible situations, the result follows. It is interesting that Theorem 3.1.1 and Theorem 3.1.3 taken together give necessary and sufficient conditions for the existence of a PBA of strength t and t+l constraints. 44 THEOREM 3.1.4: Let S be an ordered set of 3 elements, e0,e1,...,es_1. For any positive integer t, consider the st dif- ferent ordered t—tuples of the elements of 8. These can be divided into s - sets, each set consisting of s t-tuples and closed under cyclic permutations of the elements of S. Denote these sets by Si’ i = 1,2,...,st-1. Suppose that it is possible to find a scheme T of m rows with elements belonging to S such that, in every t-rowed submatrix, the number of columns belonging to an S1 is constant and greater than zero, with the restriction that if Sj contains a column which is a rowwise permutation of a column in Si’ then the number of columns occurring in a t-rowed submatrix from Sj is the same as the number of columns occurring in a t-rowed submatrix from Si' Then, one can use this scheme to construct a PBA, A = (m,N,s,t), with index set As t' ' 3 Proof: We can define the sets Si’ 1 = 1,...,st-1, as follows. Consider the 8 distinct (t-l)-tuples formed from elements of S. Let the first t-tuple of each Si be (e,ei ,...,ei )', where e 1 t-l is a fixed element arbitrarily chosen from S, and (e ,...,e, )' is one of the distinCt (t-1)-tup1es formed from elements of S. The additional 5-1 t-tuples of each of the sets Si are obtained from the first by cyclic permutation of the elements of S. A can now be constructed. Append to the columns of the scheme T all the transformations of these columns consisting of cyclic permutations of the elements of S. Choosing any t rows, we see that each of the possible st t-tuples occurs. Furthermore, because of the restriction that, if Sj contains a permutation of 45 a column in Si’ then the same number of columns must occur from each, it follows that a permutation of a t-tuple will occur the same number of times as the t-tuple. Finally, the number of occurrences is independent of the t rows chosen. EXAMPLE: Let S = {0,1} and t = 3. The 4 distinct 2-tuples, 0 l l which can be formed from S are (8) (1) (O) (1). Pick 0 as the element e of the proof, then [0 r1 (0 1 sl=,o 1; , 32={o 1} k0 , 1, 1 , 0 1x (0 1\ o , and s ==< 1 o ' . 1) 4 , 0,? 0 .3 is, Let HOOD HHOO OHOO HOHO OOHO OHHO HOOH OOOH OHOH OOHH and let 51 be the number of times columns from S1 occur in any three rows of T. Then one can check that Thus we have a PBA of strength 3 given by HOOO HHOO OHOO HOHO OOHO OHHO id c> C) P4 OOOH OHOH OOHH OHHH C) C) P“ P‘ P‘ c> F‘ F‘ OHOH P‘ F‘ c> P‘ P‘ c: c: F‘ OHHO HHHO HOHO HHOO A close look at T in the above example reveals that it is a PBA of strength 2. We are thus lead to ask whether it is always 46 true that a PBA of strength 2 forms a scheme for the construction of a PBA of strength 3. This is answered by the following. THEOREM 3.1.5: Let t = 2n. Then a PBA (m,N,2,t) with index set {u§t)\i = 0,...,t} forms a scheme for the construction of a PBA (m,2N,2,t+l) with index set {u§t+1){i = O,...,t+l], where (t+l) = t-2k i (t) “t+1-k 2i=0 ('1) LLk+i ’ uit+1> k S u Proof: A set Si is composed of vectors )' and < I — (x1,...,xt+l * * * v — (X1,...,Xt+1) ’ * where if v has k ones, then v has t+l-k ones. Suppose v contains k ones, then, by Theorem 3.1.1, v will * appear in t+l rows of (m,N,2,t) mk times, and v will appear in those t+l rows m Moreover, by PrOperty 3.1.2 t+1-k' t-2k i t t-2k+1 Since t ~ 2k+l = 2(u - k) + l is odd, we have = t-2k i (t) mk +""1:+1-R 2i=0 ('1) u‘1c+i ’ which is independent of the t+l rows chosen from (m,N,2,t). Suppose Sj contains a permutation of v. Call it u. * * Then u is a permutation of v , and, since mk and mt+l~k are independent of order, the number of columns of Sj occurring in any t+l rows of (m,N,2,t) is t-2k i (t) 2i=0 ('1) ”k+i ’ 2k 5 t ’ 47 the same as for Si' Thus (m,N,2,t) forms a scheme satisfying Theorem 3.1.4. It is clear from the construction of (m,2N,2,t+l) that a (t+l)-tuple containing k ones will appear mk + mt+l-k times. Likewise, a (t+1)-tup1e containing t+l-k ones will appear . t _ mt+l-k +mk times. Thus, where k S 2 — u, we have (t+l) 2 (t+1) = t-Zk i (t) ”'k p't+1-R zi=0 ('1) p'R+i° COROLLARY 3.1.6: A PBA (m,N,2,2) with index set 2 2 {H5 )9“; ) ,u(2)} forms a scheme for the construction of a PBA 3 3 3 3 ( ) ( ) ( ) u( )} 0 ,ul ’“2 , if either (m+l,2N,2,3) with index set {u Hi2) = “52) or uéz) = piz). Furthermore, if m' is the maximum number of constraints of (m,N,2,2), then m'+l will be the maximum number of constraints of (m+l,2N,2,3). Proof: Without loss of generality, we assume (2) _ (2) p0 _ “1 ° 2 (If pi ) = uéz), we can interchange zeros and ones in (m,N,2,2) and obtain an array where ”82) = uiZ). ) Let T be the PBA (m,N,2,2) and T* be the array obtained from T by interchanging zeros and ones (i.e. by a cyclic permutation of the elements of S = {0,1}). Let TT* represent the juxtaposition * * of T and T , then, by Theorem 3.1.5, TT is a PBA (m,2N,2,2) (3) ___ (2) (3): <2) (3) __ (2) (3) = (2) 0 “2 9 U1 ”0 ’ H2 - HO 9 H3 ”2 }' * We add the nfldst row to TT by placing a zero in each with index {n * column of T and a one in each column of T. Call the reSulting array A. Consider any two of the first m rows of A together with the m+lSt row of A. In T 48 n(0,0) - héz), n(0,1) = n(l,O) = ”32), and n(1,1) - ng). In T n(0,0) a héz), n(0,1) = h(1,0) a “62), and h(1,1) = ”32). Thus for the three rows “(0,031) 3 H32). “(0,191) = “(19031) = H32), n(1,1,1) 8 H52) n(0,0,0) g u§2)) “(03190) = “(1,0,0) 3 ”32), n(1,l,0) = M32) Since this is independent of the two rows chosen from TT*, A is a PBA (m+l,2N,2,3). The remainder of the theorem follows from‘Theorem 2.5.3. EXAMPIE: Consider A in the example following Ienma 3.1.3. A is a PBA (4,20,2,3) with index set {l,3,3,1}. By placing ones under the first 10 columns of A and zeros under the remaining 10 columns, we obtain a PBA (5,20,2,3) with index set {1,3,3,1}. Corollary 3.1.6 has application in the following kind of situation. Suppose that, after an experiment has been performed, it becomes desirable to include an additional factor, where the original design was a PBA (m,N,2,2). Then instead of performing an entirely new experiment, we consider the original experiment to be half of an array, (m+1,2N,2,2), and add the remaining half in which the new factor will appear constant at the 1 level. The problem may arise that, while, in the original experi- ment, there were no interaction effects, the introduction of a new factor makes this assumption questionable. The corollary shows that the additional treatment combinations may be designed so that the 49 augmented experiment is of strength 3, which will allow estimation of main effects in the presence of first order interactions. Consider now a PBA A of strength 2 in 3 symbols with index set A3’2 = {xoo’xll’KZZ’XOI’XOZ’212}° If we Wish to construct a PBA of strength 3, we must consider the sets Si of Theorem 3.1.4. These can be given as 'o 1 2\ o 1 2\ o 1 2) 81:10 1 2 32: o 1 2) s3={o 1 2 0 , 1 , 2 1 , 2 , 0,5 2 , o , 1) r0 1 2\ 1 2x [1. 2 03 34:” 2 0, SS= 2 o 1 S6=.0 1 2) Lo, 1, 2) 10 ,1 ,2, to ,1 ,2/ f2 o 1\ o 1 2} {o 1 2x 5 = o 1 2 ( s = 1 2 o ‘ s = 2 o 1 a 7 1b ,1, 2; 8 {2 ,0, Li 9 L1, 2,11) Consider three rows of A. Let 31 be the number of times columns of Si appear in these three rows. Then, since n(0,0,0) + n(0,0,1) + n(0,0,2) + n(l,l,l) + n(l,l,0) + n(l,l,2) + n(2,2,0) + n(2,2,l) + n(2,2,2) = 100 + 111 + in , we see + A >‘00 11+A22= 1 2 3 Similarly A + A 00 11+A22' 1 4 5 and A01‘1"02J"‘12=‘°‘2"Li’sl’sa 101 +'*02 + 112 z 83 +'Se +'Ss Moreover, these equations are independent of the three rows chosen from A. Solving, we find (1) $2 +-33 = 84 + 35 (2) $2 + $5 = 53 + 36 (3) 82 +85 = 34 + 57 (4) 54 +55 = 36 +57 (5) $2 + 33 = 36 + 37 (6) 32 f 88 = 56 + 59 . (1) and (2) imply (3) and (4) imply 23 = s + s . 4 2 6 .Thus, (I) 82 = 84 = 36 . (l), (5) and (1) imply (II) 33 = 35 = 57 . And, (6) and (1) imply (III) 88 = 59 If A is orthogonal, then 51 s +rs + s = s + s + s so that (111') s = s = s . We now prove THEOREM 3.1.7: A PBA (m,N,3,2) with index set {200’211’212’201’202’xlz} forms a scheme for construction of a PBA (m,3N,3,3) if 81 and one of s of the three rows chosen from A. i’ i = 2,...,7 are independent Proof: Suppose s and s are constant. Then s and l 2 4 36 are also constant, by (1). Furthermore, 82 + S5 + 58 ' (51 + S2 + 53) = A01 + 102 + A12 ' (A0 + 11 +"‘2) = K (say) Thus, 88 = 81 + K , so 88 and, by III, 39 are constant. Finally, 33 = x0 + x1 + 12 - (51 + $2) , so 53 and, by II, SS and 37 are constant. Now, by Theorem 3.1.4, the theorem follows. Note that the resulting array will have A111 = 1222 x000 x001 = A112 = 1220 A002 = A110 = A221 52 and if A is orthogonal Aooo = 1111 = A222 = A012° 3.2 CONSTRUCTION OF PBA'S OF STRENGTH 2 IN s SYMBOLS FROM PBA'S OF STRENGTH 2 IN TWO SYMBOLS THEOREM 3.2.1: Consider a PBA which is also the incidence matrix of a BIB design (v,b,r,k,x = 1). The existence of this array is equivalent to the existence of a PBA A = (m,N,s,2) with index set As,2’ where m=r N = b - r s = k loo = b - r - (k - l)(2r - k - 1) 101 = r - k i = 1,...,k-1 ij = 1 i,j = 1,...,k-1 . ‘nggfz Let T be the incidence matrix of the BIB design (v,b,r,k,l). Then T is a PBA (v,b,2,2) with index set {no = b - 2r + 1, p1 = r - l, u2 = 1}. Interchanging columns and flows as necessary, we can put T into the following form. The first column contains ones in its first k rows and zeros elsewhere. The second column contains a one in its first row, ones in rows k+l through 2k-l, and zeros elsewhere. (Since ”2 = 1, once we put a one in the first row of column two, there can be no ones in rows 2 through k of column two.) In gen- eral, for i = 1,...,r, the ith column of T contains a one in its first row, ones in rows i(k-l) - (k-3) through i(k-l) + l, and 53 zeros elsewhere. Let Ki represent the k-l rows from row i(k-l) - (k-3) through row i(k-l) + l, i = 1,...,r. Consider column cj, j = r+l,...,b. Since ”2 = 1, cj can have at most one one in the rows of Ki’ where the other entries are zero. If the one occurs in the first row of ,Ki’ enter a one in row i and column j-r of A. If the one occurs in the second row of Ki’ enter a two in row i and column j-r, and so on. If no one occurs in the rows of Ki’ enter a zero in row i column j-r of A. Clearly, m = r, N = b-r, and s = k, so that we must now show that A is a PBA of strength 2 with the indicated index set. Consider K“. and Kv, u,v = 1,...,r, u # v. Each row of Ku (Kv) contains r-l ones in the columns from r+l through b. Since “2 = 1, each row of Ku must have exactly one of these ones in common with each row of RV. Thus for rows u and v of A, xi,j = l i,j = 1,...,k-l and 101 = r - 1 - (k-l) =r'k , 1:1, oo,k'lo Moreover, _ k-l k-l k-l A00 — (b r? 2 2i=1 xOi zi=1 zj=1 xij b - r - 2(k-l)(r-k) - (k-l)(k-1) b - r - (k-l)(2r - k - 1) . Since u and v were arbitrary, the X's are independent of the two rows of A. Thus A is a PBA with the indicated index set. 54 Given the PBA, A, we can reverse the construction and derive T. EXAMPLE: Consider the BIB design (13,26,6,3,1), then we write T in the indicated form and A below T, where K1 contains rows two and three, K2 contains rows four and five,..., and K6 contains rows 12 and 13. l l l 1 l l O 0 O O O O O O O 0 0 0 0 O 0 0 O 0 O 0 l O O 0 0 0 l l 1 l 1 O 0 O O 0 O O O 0 0 O O O O 0 l O O 0 O 0 0 0 0 O 0 l l 1 1 l O O O O O O O O O O O l O O 0 O 1 0 O 0 O l O O O O 1 1 l O O O O 0 0 O O l O 0 0 O O l 0 O 0 O l 0 O O 0 O O 1 1 1 O O O O O 0 1 0 O 0 0.1 O O 0 0 O 1 O O l 0 0 0 0 O l l O 0 T = O 0 1 O O 0 O O 1 O 0 O O 0 l O O l O l O 0 0 O l O O 0 O 1 O O O 0 0 l O O l O 0 O O O l O O O l O l 0 O 0 O l O 0 O O 0 0 l l O O O O 0 0 0 l O O O l O l O 0 0 0 l O l O 0 0 0 0 O O 0 l O 0 O O l 0 O l 1 O O 0 0 0 1 O 0 0 1 0 O 0 0 l 0 0 O O 1 0 O l O O O l 0 O 0 O 0 1 0.0 O l O O O O l 0 l 0 0 O l 0 0 O O 1 O O 0 0 O 1 O O 0 0 1 0 0 0 O 1 O l O 0 O l l 0 O O l 1 l 1 l 2 2 2 2 2 O O O 0 0 O O O O O l 2 O O O l 2 0 O O l 1 1 2 2 2 O O O O A = O l 2 O O 0 0 l 2 O 1 2 O 2 0 O l l 2 O O 0 O l 2 2 1 0 O O O O 1 2 O O l 2 l 2 l 0 2 0 0 0 O 2 O l O 0 2 O l 2 0 l l 2 0.0012000121200122001 Clearly A is a PBA (6,20,3,2) with x00 = 4, 101 = 3, i = 1,2 and xij = l, i,j = 1,2. Moreover, as was shown in the example on page 38, A has the maximum number of rows possible. We state this formally as THEOREM 3.2.2: The PBA A in Theorem 3.2.1 has the maximum possible number of rows. 55 Proof: This is clear since T has the maximum possible number of rows as shown in Corollary 2.4.3. CHAPTER IV RELATION TO OTHER AREAS OF MATHEMATICS 4.1 TACTICAL CONFIGURATIONS DEFINITION: A complete a - t - k - m configuration is an arrangement of m elements into blocks of size k so that each set of t elements occurs in exactly 0 blocks. Let b be the number of blocks in the configuration. Further- more, let Ni denote the number of sets each of which contains a fixed set of 1 elements, where i = 0,...,t. Then N0 = b and NC = a, and in general we have (M) IEMMA 4.1.1: 0 t-i i = 0,...,t _Ni = (k-i) t-i Proof: Let Si be a fixed subset containing i elements. As noted above, if i = t, then St will appear in exactly 0 sets. If i < t, then Si can be part of several different sets each , m i . . . haVing t elements. There are ( _) sets of Size t containing Si' However, there are (5‘?) sets of size t, containing 5,, in m-i 1 ' o’(t-i) a block of size k (2 t). Thus St occurs in __k:T_ of the ( .) t-1 blocks of the configuration. EXAMPLE: Consider the triple system, 1 - 2 - 3 - 7, given by l l 2 3 4 6 4 5 4 5 3 5 7 7 6 , 57 where the blocks are column vectors, and a = 1, t = 2, k = 3, m = 7. Then 2 m 7 N = = (1) —— = 7 0 (k) (3) t 2 N1 = 3 N2 = 1 The following theorem is due to Chakravarti (1961). The proof given here is somewhat less complicated than the one given by him. THEOREM 4.1.1: The existence of an a - t - k - m configura- tion implies the existence of a PBA A = (m,N0,2,t) with index set {”111 = 0,...,t}, where t'i j t-i J=0 +3 provided ”1 2 0, i = O,l,...,t. Proof: We form A as follows. Let al,az,...,am denote the m elements and S ,S ,...,8 denote the N sets of the con- 1 2 N0 0 figuration. Then, we place a one in the ith row and jth column of A if a1 E 31. If ai 4 Sj we place a zero in the ith row and jt column of A, i = 1,...,m, j = 1,...,N0. Consider any t-rowed submatrix of A, and from its NO columns choose a column containing r ones. We show that this column occurs _ _ t-r — t-r _ , , , ur - Nr ( 1 )Nr+1 + ( 2 )Nr+2 ... times. By renaming a s as necessary we may assume that the ones in the column correspond to a and the 0's correSpond to a a . a 0.. 0.. 1) 3r r+1, 3 t 58 Recall that ‘Nr is the number of sets, Sj’ which contain the fixed set a1,...,ar. Also included in this number are those 3 s a‘ ' a ... a a d a i = r+l ... t. here are et cont ining 1, , r n i’ , , T Nr+1 . . t-r sets containing a1,...,ar, ai, and there are ( 1 ) ai's. Thus t-r N - ( 1 )Nr is the number of sets containing 31,...,ar excluding those which contain a1,...,a , a, i = r+l,...,t. However, r i t-r . . . ( 1 )Nr+1 counts tWice those sets containing a1,a2,...,a ,a ,a, r i i # j i,j = r+l,...,t. It counts three times those sets containing al"°°’ar’ai’aj’ak’ i # j # k i,j,k = r+l,...,t. In general, it counts L times those sets containing L of ar+1,...,at in addi- . t-r a o o o a o I e e - a tion to 1, , r Ther for , Nr ( 1 )Nr+1 excludes one too m ny of the sets of type a1,...,ar,ai,aj, it excludes two too many of the sets of type a1,...,a a, a a In general, it excludes L-l too many of the sets containing L of ar,...,at in addition to a .00 a O 1’ ’ r . There are N sets containin a ... a a a i ' r+2 g 1, S #J, r, i, j, i,j = r+l,...,t, and there are (tgr) possible aiaj combinations. However, (tgr)Nr+2 counts those sets which contain a1,...,ar,ai,aj, k 3 (2) = 3 times,... . Continuing in this way, we find that the number of sets con- taining 81,...,ar and not containing any of ar 1,...,8t is t-r t-r t-r - + -...+ - . N ( 1 )Nr 1 ( 2 )Nr 2 ( l) Nt’ and the result follows EXAMPLE: Consider the example following Lemma 4.1.1. The PBA generated by the 1 - 2 - 3 - 7 configuration is OOOOHHH OOHHOOH HHOOOOH OHOHOHO HOHOOHO HCOHHOO OHHOHOO where ”2 = N2 = l . COROLLARY 4.1.2: The PBA A in Theorem 4.1.1 has the maximum possible number of rows. {Egggfz Since each column of A has k ones, by Theorem 2.4.2 it follows that A has the maximum possible number of rows. In view of this, it is clear that A is the incidence matrix of a BIB design, (v,b,r,k,x). In fact, v = m b = N0 r = N1 k = k A = N2 . We now give a converse to Theorem 4.1.1. THEOREM 4.1.3: Let A be a PBA (m,N,2,t) with index set {”111 = 0,...,t}. If A has a constant number of ones per column, 60 k (say), the existence of A implies the existence of a complete pt - t - k - m configuration and a complete no - t - (m-k) - m configuration. Proof: Number the rows of A one through m and the columns of A one through N. Then i is in set j, if there is a one in row i and column j, i = 1,...,m, j = 1,...,N. Since the number of ones in a column is constant and equal to k, we have N sets each containing k elements, where the total number of elements is m. Consider any fixed set of t elements. This set corresponds to t specific rows of A. Since A is of strength t, the number of columns containing ones in each of these rows is ”t' Thus, the set of t elements will appear in exactly pt sets. It now follows that the above sets form a complete pt - t - k - m configuration. To obtain a complete “0 - t - (m-k) - m configuration, inter- change the zeros and ones in A and proceed as above. COROLLARY 4.1.4: Let A be a PBA (m,N,2,2) with index set {uo,u1,u2}, where ”I = ”2 (or ”O = pl), then, if the number of ones in each column of A is constant, the existence of A implies the existence of a complete ”0 - 3 - k - 2k configuration, where 2n k = 1 . Proof: By Corollary 3.1.6, the existence of A implies the existence of a PBA (m+l,2N,2,3), where in this circumstance p§3> = ”0. Let k be the number of ones in a column of A. Then + 2 mm1 ”2) ”1 m k: h =T‘— 61 But _ Nul _ N m— 2 —u '1» ’ “1.110112 1 0 so 21» k = 1 . p'1'“0 * . Let A be the array obtained from A by interchanging * * zeros and ones. Then the number of ones per column in A , k , is k* ="‘(”o +HL1)2“L0 +HL1 Thus, By the construction of Corollary 3.1.6, it now follows that (m+l,2N,2,3) has k ones in each column. Thus, by the above theorem, there exists a complete ”0 - 3 - k - 2k configuration. COROLLARY 4.1.5: Let A be a PBA (m,N,2,2) with index set {H0:H1»H21: where ”O = “2. Then, if the number of ones in each column of A is constant, the existence of A implies the existence of a complete (2p.O - pl) - 3 - k - 2k configuration, where “'1 k=-—-—— ”1'“? Proof: By Theorem 3.1.5, the existence of A implies the 3 existence of (m,2N,2,3) where H; ) = 2n0 - ul. Let k be the number of ones in a column of A. Then 62 m 2,11 ”1'”2 4.2 GRAPH THEORY In this section we will be concerned with ordinary graphs which are undirected, without loops or multiple adjacencies, and of a finite order. A graph will be represented by a pair {V,M}, where V is a set of v vertices and M is the adjacency matrix of the graph. va M = (m(xiy)) , | where 63 -1 if x and y are adjacent m(x,y) = 1 if x and y are nonadjacent 0 if x = y x,y E V. Let x be a vertex of a graph. Let n1(x). be the number of vertices adjacent to x and n2(x) be the number of vertices nonadjacent to x. Then n1(x) + n2(x) = v - 1 , where v is the number of vertices of the graph. A graph is called REGULAR if n1(x) (and thus n2(x)) is independent of the choice of x. Let x and y be any two distinct vertices of a graph. Let 1 if x and y are adjacent h: 2 if x and y are nonadjacent. . h h . . Then we define p, as follows. p is the number of vertices ij 11 which are adjacent to x and to y. p22 is the number of vertices which are adjacent to x and nonadjacent to y. p21 is the number of vertices which are nonadjacent to x and adjacent to y. p22 is the number of vertices nonadjacent to x and to y. A graph is called STRONG if it is nonvoid and noncomplete and if 1 1 P12 (X :Y) + P21 (X ’3') and 2 2 p12(X.y) + 921(X.y) 64 are independent of the choice of x and y. A graph is called STRONGLY REGULAR if it is both strong and regular. EXAMPLE: PETERSEN GRAPH. Let v = {vdi = 1,...,10} and M be given by o -1 1 1 -1 -1 1 1 1 1 -1 o -1 1 1 1 -1 1 1 1 1 -1 o-1 1 1 1-1 1 1 F 1 1 -1 o -1 1 1 1 -1 1 :11, -1 1 1 -1 o 1 1 1 1 -1 M ' -1 1 1 1 1 0 1 -1 -1 1 q 1 -1 1 1 1 1 o 1 -1 -1 in” 1 1 -1 1 1 -1 1 o 1 -1 i; 1 1 1 -1 1 -1 -1 1 o 1 1 1 1 1 -1 1 -1 -1 1 0 Then we may represent the graph pictorially as follows: This graph is strongly regular, where n = 3 , 1 n2= 6 , 1 1 p12 + p21 ' 2 2 p12 +'921 1 b and = 4 C We next investigate the relation between graphs and PBA's. 65 DEFINITION: Consider any two columns of a PBA, A. If there are exactly c rows in which each column has a one, we say they have c ones in common. A is called a.Quasisymmetric Partially Balanced Array GQPBA) if the number of ones in common to two columns of A can take exactly two values, c and c2 (say), where c > c . l l 2 EXAMPLE: Let A be given by P‘ P‘ c> c> c: P‘ F‘ c> F. c: be c: c> p. C) P‘ P‘ c> c> ex c> c> r1 h: Then the first and second columns have one one in common, but the first and last columns have zero ones in common. In fact, it can be verified that any two columns of A have either zero ones or one one in common. Hence A is a QPBA. QPBA's are not difficult to find, as the following shows. THEOREM 4.2.1: Let A be a PBA (m,N,2,2) with index set {u0,u1,u2 = 1} and m < N. Then A is a 1, there are columns which have one one in common. To show that there are columns which have no ones in common, we suppose there are none. Let X be any column of A, and suppose that X contains k ones. Corresponding to the first one in X, there are ”1 columns which have a one, and there are no +-u1 columns which have a zero. CorreSponding to the remaining k-l ones in X, there are (k-l)p.1 columns which have a common one. Since we assume that every column 66 in A has exactly one one in common with X, it follows that (k’lhll = “'0 + ”‘1 ' Thus, 11 +211 _ k=_0_____l.=N__l H1 “1 and is independent of the choice of the column X. Therefore A -l is the incidence matrix of a BIB design (m,N,r = u1+l, k = §;_31)2 l where m < N and (i) r(k-l) = m-l (ii) Nk = mr (iii) rk-k = N-l . (i) and (iii) give (iv) r+m = N+k . Suppose N = m + C , then (iv) gives r+m m + C + k so (v) C = r-k . (ii) gives (m+C)k mr so that ll 3 NH i (vi) C 67 Thus, by (v) and (vi), r-k mgr-k) k k . which implies that each column of A contains all ones. Since m 2 2, this implies p1 > 1, a contradiction. Therefore, X must have no ones in common with at least one column of A, from which it follows that A. is a.QPBA with c1 = 1, c2 = O. THEOREM 4.2.2: Let A be a.QPBA (m,N,2,2). Then the existence of A implies the existence of a graph on N vertices. Proof; Since A is atQPBA, any two columns have either c1 or c2 ones in common. Choose x and y (0 < y S x) so that x+y = c1 and x-y = C2 Also, let kj be the number of ones in column j of A. Then we write A'A = '. + x(J - IN) - yM, . N kN where JN is the N x N matrix of all ones, IN is the N x N .1 identity matrix, and M is an N X N matrix with zeros on the diagonal and plus or minus one off the diagonal. Thus, M is the adjacency matrix of a graph on N vertices, and the result follows. In view of this theorem and the above definitions of strong graphs and regular graphs, we make the following definitions. 68 DEFINITIONS: (i) Let x be a column of a QPBA, A. let n1(X) be the number of columns of A which have c1 ones in common with X, and let n2(X) be the number of columns of A which have c2 ones in common with X. Then, A will be called REGULAR if n1(X) and n2(X) are independent of the choice of X. (ii) Let X and Y be columns of a QPBA, A. If X and 1 p1,2 number of columns of A with c1 ones in common with X and c Y have c1 (c2) ones in common, let (X,Y) (pi 2(X,Y)) be the 3 2 ones in common with Y. Let p; 1(X,Y) (p: 1(X,Y)) be the number 9 S of columns of A with c2 ones in common with X and c ones in 1 common with Y. Then A will be called STRONG if 1 1 2 2 p1,2 are independent of the choice of X and Y. EXAMPLE: Let 0 0 0 l l l O l l O O l A: 1 o 1 o 1 o l l O 1 O 0 , then A is strongly regular, where c1 = 1, c2 = 0, n1 = 4, n2 = 1, l + - 2 , p1,2 p2,1 and THEOREM 4.2.3: Let A be a