On Duals of Multiplicative Designs Citation Patenaude, Robert Alan (1972) On Duals of Multiplicative Designs. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/AENB-1V51. https://resolver.caltech.edu/CaltechTHESIS:06132016-081554388 Abstract A multiplicative design is a square design (that is, a set S of n elements called varieties, and a collection of n subsets of S called blocks) in which each block may be assigned a positive number, called the block's weight, less than the size of the block in such a way that the size of the intersection of two distinct blocks is the geometric mean of their weights. A uniform design is a multiplicative design in which the difference between the weight and size of a block is independent of the choice of the block. A λ-design is a multiplicative design with identical weights in which not all of the block sizes are equal. It is conjectured that if a multiplicative design has a multiplicative dual, and if neither design belongs to a specific class of designs, then both are uniform designs. Two cases of this conjecture are proved, one of which is this generalization of a result of K. N. Majumdar: a λ-design with a multiplicative dual has λ = 1. Degenerate multiplicative designs are investigated. A generalization to multiplicative designs of Henry B. Mann's upper bound on the multiplicity of a repeated variety is also proved. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Ryser, Herbert J. Thesis Committee: Unknown, Unknown Defense Date: 3 April 1972 Funders: Funding Agency Grant Number Caltech UNSPECIFIED Army Research Office (ARO) UNSPECIFIED Record Number: CaltechTHESIS:06132016-081554388 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:06132016-081554388 DOI: 10.7907/AENB-1V51 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 9871 Collection: CaltechTHESIS Deposited By: INVALID USER Deposited On: 13 Jun 2016 16:05 Last Modified: 02 Jul 2024 19:41 Thesis Files Preview PDF - Final Version See Usage Policy. 8MB Repository Staff Only: item control page

ON DUALS OF MULTIPLICATIVE DESIGNS Thesis by Robert Alan Patenaude In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1972 (Submitted April 3, 1972) ii ACKNOWLEDGMENTS This dissertation would likely not have been possible had it not been for the encouragement and advice of my supervisor, Professor Herbert J. Ryser, and I am indebted to him, I would a lso like to thank Professors James E. Householder and Donald E. Kib bey for their part in my earlier mathematical development. I would like to acknowledge the California Institute of Technology and the Uni t ed States Army Research Office at Durham for their financial support in the form of a teaching and a research assistantship, respectively. Finally, and perhaps most vaguely, I want to acknowledge Caltech for what I have learned it to be, a truly humane research institution. friendships. It has allowed me to learn much and to develop the greatest iii ABSTRACT A multiplicative design is a square design (that is, a set S of n elements called varieties, and a collection of n subsets of S called blocks) in which each block may be assigned a positive number, called the block's weight, less than the size of the block in such a way that the size of the intersection of two distinct blocks is the geometric mean of their weights. A uniform design is a multiplicative design in which the difference between the weight and size of a block is independent of the choice of the block. A \-design is a multiplicative design with identical weights in which not all of the block sizes are equal. It is conjectured that if a multiplicative design has a multi- plicative dual, and if neither design belongs to a specific class of designs, then both are uniform designs. Two cases of this conjecture are proved, one of which is this generalization of a result of K. N. Majumdar: a \-design with a multiplicative dual has A.= 1. ate multiplicative designs are investigated. Degener- A generalization to multiplicative designs of Henry B. Mann's upper bound on the multiplicity of a repeated variety is also proved. iv TABLE OF CONTENTS Page Acknowledgments 11 Abstract . • . . . 111 SECTION 1 Introduction • . . . . • • . . . . . . 1 2 Degenerate Multiplicative Designs 5 3 The ;>. -Designs with Multiplicative Duals . 9 4 A Second Case of the Conjecture . . . 20 5 A Generalization of Mann's Inequality 28 Refe rences 35 1 SECTION 1 INTRODUCTION By a combinatorial design, or simply a design, we mean a finite set S = [a , ..• , am} and a finite indexed collection S , ..• , Sn of 1 1 Traditionally the elements a. are called varieties and subsets of S. 1 the subsets S., which need not be distinct, are called blocks. We J define the following integers commonly associated with a design: variety order m r.1 = IU:a.1 ES.}! J 1 ~ i µ ij = replication numbers ~ m I f e: [a i, a j} ~ s £} I linkage numbers 1 s: i, j ~ m, i -:# j block order n k. = J \ .. = lJ j 1 ls.I, J Is.1 n s.IJ ~ ~n block sizes overlap numbers 1 :s; i, j ~ n, i -:# j To each design we associate the (0, 1)-matrix A = [a lJ. .] of size m by n in which a .. = 0 or a .. = 1 according as a. f. S. or a. ES .. lJ lJ 1 J 1 J This matrix representation is quite useful and we will often identify a design with its incidence matrix whenever no confusion could result. If A is the incidence matrix of a design, a dual of the design is a design whose incidence matrix is AT' the transpose of A. We have 2 AT A = diag [k - ;\ l l , ••• , k - ;\ ] + [ ;\ .. ] 1 n nn lJ , AA T = diag [r 1-µl l '.•.'rm -µmm]+ [µi) ' where µ .. for 1 s: i s: m and;\ .. for 1 s: j s: n may be given arbitrary 11 JJ values. We define some axiomatically restricted designs. Suppose the overlap numbers ;\ .. of a design have a constant value ;\for i :f. j and lJ that k. > ;\ for 1 s: j s: n. It is known [9, 11 J then that the block order n J of the de sign cannot exceed the variety order m, that is m :::= n This relation is known as Fisher 1 s inequality. m ( 1. 1) • If in addition when = n and the block sizes k. of the design also have a common value k, J the design is called a (v, k, ;\)-design where v = m = n. Conditions imposed on a (v, k, ;\)-design to exclude degeneracies are v > k + 1, k > ;\ + 1, and ;\ > O. A useful necessary condition [8 J on the param- eters of a (v, k, ;\}-design is k If m 2 - ;\v =k - A ( 1. 2} = n, if the overlap numbers have a common value ;\, and if the block sizes are~ all equal, the design is called a ;\-design [8]. The conditions imposed here to exclude uninteresting degener- ac ie s are k. > ;\ > 0 for 1 s: j s: n. J Suppose that in a certain design we can associate with each block S. a positive number ;\ ., called its weight, such that the (i, j)J J overlap 3 A.. . = lJ for all i -:/. j. Is.1 n s J.1 = ./A..1 ./A. J. If in addition the block order n and variety order m are equal and m = n :2: 3, the design is called a multiplicative design. The conditions imposed here to exclude degeneracies are k. >A.. > 0 for J J 1 s j s n. A multiplicative design in which k. - A.. is constant for J J 1 s j s n is called a uniform design. Ryser [10] defined these designs and constructed several classes of them. Degenerate multiplicative · designs are not without interest and these are discussed in some detail in Section 2. Define a multiplicative design to be bordered if, through row and column permutations, the incidence matrix A of the design can be brought to the form A=[T.J where X and Y are column matrices, each consisting entirely of zeroes or entirely of ones, and where Bis a (v, k, A.)- design, possibly a degenerate one. Several classes of bordered multiplicative designs may be immediately constructed in terms of (v, k, ;\)-designs. It is known [8] that the dual of a (v, k, ;\)-design is also a (v, k, ;\)-design. designs. Ryser [10] proved this generalization to uniform 4 Theorem~ [Ryser]. The dual of a uniform design is a uniform design. A weak converse to Theorem 1. 1 might be: If a multiplicative design has a multiplicative dual, then both the design and its dual are ur.iform. This is seen to fail for many bordered multiplicative designs, but there is some evidence that for all other designs the converse is true. Conjecture ~· If a nonbordered multiplicative design has a multi- plicative dual, then both the design and its dual are uniform designs. Sections 3 and 4 prove certain cases of Conjecture 1. 2, '.2here is less hard evidence for the following conjecture. Conjecture . 1, 3. A multiplicative design has at most two distinct weights. But if Conjecture 1. 3 holds, then the results of Sections 3 and 4 go a long way in establishing Conjecture 1. 2. If in the definition of a multiplicative design we do not neces sarily require that m = n, then we call the design a partial multiplicative design. An inequality of Fisher type [10] implies m ::<: n, however. If in addition k. - A. is constant for 1 ~ j ~ n, it is called a partial J J uniform design. These are investigated in Section 5, and in particular we prove a generalization of an upper bound due to H. B. Mann [ 7, 5] on the multiplicity of the repeated variety. 5 SECTION 2 DEGENERATE MULTIPLICATIVE DESIGNS By a (nondegenerate) multiplicative design on the parameters k , ... , kn and \ , .•. , \n we mean a (0, 1)-matrix A of order n 1 1 satisfying AT A = diag [k -\ , ••• , k -\ ] + [/\ . J\ .] 1 1 n n 1 J (2. 1) and 0 < \. < k. 1 1 1 s: i for s: n (2. 2) The intent of the conditions (2. 2) is to exclude unimportant degenE>rate cases. Analogous conditions for (v, k, \)-designs and \-designs exclude only readily identifiable degenerate configurations. The instances of A in which (2. 1) holds and .(2. 2) fails are not as clear, however, and the following discussion will describe many of them. Condition (2. 1) and the structure of A require that 0 s; \. and 1 0 s: ki for 1 s: i s: n. Then k. ~ J\. J\ . 1 hold. 1 1+ 1 With no loss of generality we set \ :<:A.. for 1 s: i < n, but k 1 n ::::: \ n 1 s: •.. s: A.n. does not necessarily Indeed if B is a (v, k, \)-design and if A is formed in tre follow- ing way from B 1 B A = l 1 . . . 1 1 6 then A satisfies (2. 1) with n = v+ 1, k 1 = • • • = k n- 1 = k+ 1 , k n 2 A. 1 = · ·• =A.n- 1 = A.+l and A.n = (k+l) /P,.+l). and k n s; A. n for k < 2A.+ 1. But k n <?: A. n = v+ l , for k <?: 2 \+ 1 If a (v, k, A.)-design satisfies one of the con- ditions k <?: 2A.+l, k < 2A.+l, its complement satisfies the other. Assume now that k. 1 i, 2: A.. :? 0 for 1 s; i ~ n. If k. = A.. = 0 for some 1 1 1 the ith column consists entirely of zeros and its presence does not affect the rest of the matrix. We hence take k. > 0 for 1 s; i s; n. 1 Call the column i of A to be type 1, 2 or 3 according ask.> A..> 0, 1 k. =A.. >0, or k. >A.. =O. 1 1 1 1 1 Ifk. =A.. >Oandk.= A..>OwithA.. :?A.. 1 1 J J 1 J then the inner product JA.. JA.. cannot exceed the column sum A.., w !1e nce 1 A.. s; A. .. 1 J J J Hence A.. = A.. for columns of type 2. 1 J We now see that A must have the form type 1 type 2 type 3 ( " - \ ("-\ ("-\ 1 c 0 0 r... 1 ... A= 1 ,.____ 0 0 .. (2. 3) ) ·~ e 1 0 ... 1 Note that e :? f. If e = f, it is possible that no columns of type 2 occur, in which case A has the form 7 where I is an identity matrix of arbitrary order and A 1 is a nonde ge ne rate multiplicative design. If e > f, however, columns of type 2 must occur. Otherwi s e C in (2. 3) would be a nondegenerate partial multiplicative design of a si ze that violates the Fisher inequality. cannot be square. When columns of type 2 occur , If C were square, say with parameters C kJ., ... , k~ I an d '11.I , •.. , '11.g we co uld f ormasquare D , 1 1 1 D = c }k~+I I = Ag+ 1 0 0 0 ..• 0 0 A column of type 2 is adjoined and then a row of zeros. The deter- T minant of D D may be computed explicitly to be whe n ce det D -:/:. O. a contradiction. But D contains a row of zeros and hence is sing ul a r, 8 Constructions exist where columns of type 2 occur and C is of size g by g-1. Replace the last column of a projective plane P of order m by its complement. the altered P = 1. denote Then the first g-1 = m 2 + m columns of C with k~ = · · · = k g- .1 = m+ 1 and A'1 = • . • : : The last column is of type 2 with k 1 1 g = ;\ 1 g 2 = m • A question on degenerate multiplicative designs remains unanswered. Under what conditions can a partial nondegenerate r.oulti- plicative design of size n by r, with n > r, be augmented by a degenerate column of type 2? 9 SECTION 3 THE \ -DESIGNS WITH MULTIPLICATIVE DUALS In [6 ] K. N. Majumdar (alias Majindar} showed essentiall y 1 that a \-design whose dual is a \ -design satisfies \ = \ well-known [3, 9] that there is 1 = 1. It is exactly one 1-des ign for each o rder n > 3, apart from block and variety labeling, and that this may be represented in matrix farm as 0 1 •.• 1 1 I ( 3. 1} n-1 1 Now I n- 1 is a degenerate (v, k, \}-design with (v, k, \} = (n-1, 1, 0), so ( 3 . 1) satisfies the conditions of a bordered multiplicative design ~ iven in Section 1. It is also immediate that (3. 1) is the only bordered multiplicative design that is also a \-design. A \-design is a non- uniform multiplicative design, so that Conjecture 1. 2 in the case of a \ -design becomes: If a \-design A has a multiplicative design as its dual, then A is a bordered multiplicative design, and hence \ = 1. This is the special case of Conjecture 1. 2 proved in Theorem 3. 2 below. A few facts are needed first. Ryser [9] and Woodall [ 11] proved that a \-design (speaking now in matrix-theoretic terms} h as 10 precisely two distinct row sums r 1 and r 2 , and that these numbers satisfy ( 3. 2) With no loss of generality we henceforth insist that r that the first e row sum r 1 1 1 > r 2 > 1, ard rows of the incidence matrix A of the \.-design have , and the last e 2 rows of A have row sum r 2 , where Lastly for each j in 1 s: j ~ n let k • and k~~ respectively J J denote the sum of the first e entries, and the sum of the last e 1 2 e 1 + e 2 1 = n. entries of column j. Following Ryser, the sum of the inner prod11cts of column j with all other columns may be computed in two ways to get ( 3. 3) Relation (3. 2) was used in the last equality. Division of {3. 3) by r 2 - l then yields pk 1• + k~c J J where p = (r 1 - 1) / ( r 2 = \.{ p+ 1) {3. 4) - 1) > 1. W. G. Bridges [2] has constructed a \.-design in tre following way from each matrix B which is the incidence matrix of a degenerate (v, 1, 0)-design I 1 v or of a nondegenerate (v, k, \. )-design with 1 (v,k,\. ) 'f. {4t-l,2t-l,t-l) for all t ;:: 2. The rows of B are permuted so that the k ones of the first column appear initially. quadrants as shown The matrix B is then partitioned into 11 1 ....'•' 1 B = 0 -·- '•' 0 and all but the lower right quadrant of B is complemented. The resul- tant matrix A can directly be shown to be the incidence matrix of a !.._-design with A_ = k - t.._'. multiplicity 1, and k The column sums of A are k 1 = v - k with. 1 2 = 2{k-A_ ) of multiplicity v - 1. {The Hadamard (v, k, !.._')-designs Bare excluded above because, precisely in those instances, k = k , and A is a (v, k, !.._)-design and not a !.._-design.) 2 1 Furthermore, v-k ~k+A' k- t.._' k v-2 v-k AAT = ( 3. 5) k- t.._' k~l v-k t. _ k+l It has been conjectured that this remarkable kind of derived !.._-design, called type.!_ by Bridges, characterizes all !.._-designs. He and others have shown this to be the case for A_ ~ 9. A theorem of Kramer [ 4] and Woodall [11] is given next; it is needed for the proof of Theorem 3. 2. It is given again here because 12 this version is more direct and more suited to our purposes. In the proof of Theorem 3. 2 we also employ some techniques of Majumdar [ 6]. Theorem 3. 1 (Kramer and Woodall): A A. -design in which the rnter- section of two rows depends only on the row sums of those rows is of type I. Proof: We know that the matrix form of the ;... .. design A= [ a .. ] h a s lJ precisely two distinct row sums r there exist numbers A. 11 , ;... 12 r 1 AAT= , A. and r 1 22 2 , and by assumption that such that All ~ rl r2 "'12 el "'12 All "'22 ~ r2 e2 "'22 In addition we have assumed AT A = diag [k - A., ••• , kn - A.] + A.J 1 where J denotes the matrix of ones of order n. or e 1 According as 1 s; i $; e 1 < i $; n, the (i, j)-entry of the identity A(A TA) = (AA T)A may be computed explicitly to be a .. (k.-A.) + r A. 1 lJ J ( 3. 6) or (3. 7) 13 where k 1• and k'~ are respectively the sum of the first e entries, and 1 J J . the sum of the last e 2 If 0 < kj < e , that is, if 1 entries, of column j. there is both a zero and a one among the first e then we conclude from (6) that kj - A.= r implies k. - A. = r J . 2 - A. 22 1 - A. 11 1 • entries of column j, Similarly 0 < kJ< < e Hence for each j in 1 ~ j by (7). ~ n, 2 at least one of (a), (b), (c) holds, and at least one of (d), (e), (f) holds, where (a) k'. = 0 J (b) k'. = e 1 J ( d) .... k''.' = 0 J (e) k~< = e2 ( f) J k j - A. = r 2 - A. 2 2 Call a column j of A of special type if one of (a) or (b) holds, and if one of (d) or (e) holds, for j. First note that (a) and (d) cannot both hold for column j, since then k. = O. J hold for column j, since then k. = n. J Also (b) and (e) cannot both Either (a) and (e), or else (b) and (d), hold for a column j of special type. Two columns of A, say columns 1 and 2, cannot both be of special type, for then either A. or k 1 = k 2 = A. would result. =0 Thus there is at most one column of special type in A. Suppose some column not of special type, say column j = 1, satisfies (a), so that (f) must also hold for j = 1. for j = 2, then A.= 0, a contradiction. for then k 1 = A.. Also (e) cannot hold for j = 2, Thus if (a) and (f) holds for j all columns j not of special type. If in addition (d) holds = 1, then (f) holds for In general all columns not of special type have the same column sum if any one of them satisfies (a). same is true if any one of them satisfies (d). The 14 Suppose instead that (b) and (f) hold for j = 1, but that neither (a) nor (d) hold for any column not of special type. If (e) holds for column j = 2 not of special type, then A cannot contain a column of special type, for it would be contained in column 1 or else in column 2. (b) holds for j Now n "'= 3 by definition, and column 3 is not of special type. for j = 3. For then e But from k 'i + k~ conditions. We claim (e) cannot also hold by the inner product of columns 2 and 3. = A. and k'~ > 0 we have k~ < A. whence by (3. 4) e a contradiction. S: A. 2 = 1, (e) holds for j = 2, 2 = k~ = A. - p( k~ - A.) > A. Similarly (b) does not hold for j = 3 under thes e Because now (c) holds for j = 2 and j = 3 and (f) holds for j = 1 and j = 3, all three columns have the same column sum. In all remaining cases, either (c) holds for all columns j not of special type, or (f) does, or both. In either case, not of special type have the same column sum. all columns The upshot of this and the preceding two paragraphs is that all columns not of special type have the same column sum. Not all of the column sums of A are equal, for then by a standard theorem [9] a (v, k, A.)-design results for A, not a ;\-design. So necessarily a unique column of special type occurs. either We have 15 1 Al el 1 = A (3. Sa) 0 A2 }2 Al }I 0 or 0 0 = A ( 3. 8b) 1 1 wher e k 2 = • • • = kn. Suppose that A has the form (3. Sa). Columns 1 and j, where 1 < j s n, have inner product :\ , and so k • = :\for 1 < j ~ n. J we conclude that 1 From (3. 4) ' ....... k:' = :\ - p(k.-:\) = :\ J J Take 1 < j < J., s: n, and let x be the number of solutions i 1 s: i ~ e a.. lJ 1 of a .. = a. ~ = 1. lJ l .N in the interval Using k • = k >'.< = :\ it is not hard to show that J J 1 = a.1 J., = 0 has e 2 - :\ - x solutions i in the interval e 1 <is: n. If A is transformed into A" as shown, 0 0 A" = 1 1 it is clear that A" is a {v, k, :\)-design with {v, k, :\) = (n, e , e - :\). 2 2 16 Similarly, if A has the form (3. 8b), the matrix formed by complementing all elements in (3. 8b) except those of A , is a (v, k, \)-design with 2 With either form A is a \-design of type L (v, k, A.)= (n,e ,e -A.). 1 1 The proof is finished. Theorem 3. 2. If a \-design has a multiplicative design as its dual, then A_ = 1. Proof: Let A = [a .. ] denote the incidence matrix of the \-design. ' lJ For 1 ~ i ~ n there are appropriate parameters k., r., A.. such that 1 1 1 AT A = diag [k -A., ••• , kn -A.] + A.J 1 AA T = diag [r 1 - A. 1 , •.• , r n - A.n J + [J\ JA.j J where J denotes the matrix of ones of order n. matrix of ones of size n by 1. Let J' denote the 1 The equality A T(AJ ) = (AT A) J' yields ( 3. 9) Premultiplication of (3. 9) by A then gives ~\ /AJj r~ ll = ~A(n~ l)r ll + r~l l A r n r n A.(n- l)r n Similarly the equality A(A T J') = (AA T)J' yields k n (3. 10) 17 r 1 + s ..f"A 1 - "A 1 k1 = A k r r n where s -- ;A 1 + · · · + ,!An • ( 3 . 11) n +s /).. Now (3. 10) and (3. 11) together imply 2 +t JA - r A 1 1 1 1 A(n-l)r 1 +s ..fA 1 - Al + A(n- l)r 1 r 1 = wher e t = r - A n n ..fA1 + • • · + r n ..fAn • n (3. 12) r n + s ..fA n - A n The ith column entry of (3. 12) m ay b e r e written as 2 (r . -l) A. + (s-t)..fA. + r . + A(n-l)r. - r. 1 1 1 1 1 1 =0 (3. 13 ) We haver . > 1 by nondegeneracy assumptions, so that (3. 13) is a 1 quadratic equation in /).. .. 1 Permute the rows of A so that ri = s f o r e < i ~ n, where s g uaranteed in (3. 2). 1 and s 2 1 for 1 ~ i ~ e, and r i = s 2 are the two distinct row sums of A Then ..fA , ... , ..fAe each satisfy the same qua d1 ratic equation (3. 13), and so have among themselves at most tw o distinct values. Suppose that both roots of (3. 13) are assumed, so that for some i f. j, ..fA . + ..fA. 1 J But we have n ~ 3 and d > O. This is a contradiction. Hence A , ... , Ae 1 hav e a common value µ 1 , and similarly Ae+i•· .. , An have a comm o n 18 value µ • 2 We have shown that the intersection of two rows of A, say rows i and j with i =/. j, depends only on the row sums of those rows; this intersection is namely l-L1 if l-L2 if /µ l /µ 2 if r. = r. = sl 1 J r. = r. = S2 1 J fr., r J·} = [s1,s2} . 1 By Theorem 3.1, A is of type I. Suppose A is derived not from the degenerate (n, 1, 0)-design I , but from a nondegenerate (v, k, A.')n design B whose parameters satisfy (v, k, A.) =/. ( 4t- l, 2t- l, t-1). From the description ( 5) of AA T, and from the nondegeneracy conditions k > 1, v - k > 1 on B, we see that µ 1 µ2 = A.' + I =v-2k+A. 1 , or essentially the same situation with µ 1 and µ 2 interchanged. , We evaluate µ µ in two ways to get 1 2 (k-A.') 2 = (v-2k+A.')(A.'+l) ( 3. 14) If the usual necessary condition for (v, k, A.)-designs, k(k-1) = A.'(v-1) (3. 15) is subtracted from (3. 14) we have v = 3k - 2A.' (3. 16) 19 Together ( 3 . 15) and (3. 16) show that (k-f..')(k-2)...'-l) = 0 whence k = 2 ). _ 1 + 1 because k > ). _ 1 for nondegenerate (v, k, ). _ }-de sig ns, This and ( 3 . 16) imply that, for some t;;:: 2, (v, k, f..') = (4t-l, 2t-l, t-1) a contradiction. Hence A is derived from the degenerate (n, 1, 0)-design I . n It is routine to show that the construction gives an A of the form (3. 1), a form which characterizes 1-designs. finished. Hence ). _ = 1, and the proof is 20 SECTION 4 A SECOND CASE OF THE CONJECTURE In Section 3 the case of the conjecture was proved in which the multiplicative design has exactly one distinct weight and its multiplicative dual has arbitrarily many distinct weights. The cas e which suggests itself next is that case in which both the design and its ciual have precisely two distinct weights. Theorem 4. 1 below proves this with an additional assumption on the block sizes of the design and its dual. Theorem 4. 1. Suppose the dual of a nonbordered multiplicative design is also a multiplicative design. Suppose also that each design hc.s exactly two distinct weights, and that for each design, the size of a block depends only on the weight of that block. Then the design cind its dual are both uniform designs. Proof: We have assumed that there are invariants n, e , e , f , f , 1 2 1 2 k , k , A , A , r , r , µ , µ with Ali A and µ i µ , and a (0, 1)1 1 2 1 1 2 2 2 2 1 2 matrix A = [a . .] of order n satisfying lJ 21 Partition the matrix A into quadrants as shown: A = Lets~ and s'}<be respectively the sum of the first f 1 last f 2 1 entries, of row i of A. the sum of the first e of A. 1 J entries, and of the last e Note thats~+ s~'< is r and that Likewise let l 1 or r 2 1 entries, and of the and £,~'< be respectively J entries, of colurrm j 2 according as 1 s:: is: e 1 or e 1 <is: n, tj + tj is k 1 or k 2 according as 1 ~ j s: f 1 or f 1 < j ~ n. In the matrix equality A(A TA} = (AA T)A, the upper left quad- rant of size e 1 by f 1 may be written explicitly as (k 1 -A 1 }A 11 + Al ·diag[s~, ••• ,s: 1 J· J+ A12 • diag[s!•··· ,s: J. J 1 = (r 1-µ.l}All + µ.l • J • diag [,e,~' ••• ' ,e,;l J + µ. 12 • J·diag[ ,e,r •••. , t£'< J ( 4. l} 1 where J denotes here the matrix of ones of size e 1 by f , and where 1 A = / A JA and µ. = Jµ. J µ. is written for brevity. 12 12 1 2 1 2 First suppose that k - A = r -µ. in (4. l}. 1 1 1 1 and tj'< = k f With s:~ = 1 tj. this supposition allows us to write (4. l} as ( A1 - A. 12) • diag [s ~, .•. , s: l] · J + r 1 A. 12 J = ( µ. 1- µ. 12> • J· diag [,el'···' .e; 1J + klµ.12 J • (4. 2) 22 Note that A. µ 1 - LL 12 1 f. A. 2 and µ 1 f. µ , respectively imply that A. 1 - )_12 and 2 are nonzero. The entries of the matrix on the left side of (4. 2) are constant within the same row, and those of the matrix en the right side of (4. 2) are constant within the same column. the entries are constant within each matrix, and A 11 Hence has constan t row sums and constant column sums. Suppose instead that k -A. f. r -µ . 1 1 1 1 for A 11 Then (4. 1) may be solved with the result that ( 4. 3) for some real numbers a , ... , a and b , •.. , bf . 1 1 e1 1 (0, 1)-matrix All is greater than 1, A (0, 1)-submatrix of order 2. 11 If the rank of the must contain a nonsingular Apart from row and column permuta- tions, these submatrices are characterized by L~J (4. 4) where the asterisk::< denotes either 0 or 1. matrix of A 11 Because (4. 4) is a sub- , (4. 3) implies that the lower right entry::< is 2. contradiction implies that the rank of A 11 is 0 or 1. This By similar reasoning ( 4. 3) excludes [] as a possible submatrix of A 11 . ( 4. 5) It is straightforward to show that a 23 (0, 1)-matrix of rank 0 or 1, containing no submatrix which by row and column permutations could be brought to ( 4. 5), has one of the forms (a) J (b) 0 (c) This argument for A [ Oj J] (d) DJ ( 4. 6) can be similarly applied to each quad- 11 rant A .. with 1 $: i ~ 2 and 1 ~ j ~ 2. . lJ Then either (1) r.- µ . = k.- :\ . and l l J J A .. has constant row sums and constant column sums, or (2) A . . has lJ lJ one of the forms (4. 6a,b,c,d). If (1) holds for any pair of adjacent quadrants (that is, for All and A A 21 and All) then r 1 -µ 1 12 , A 12 and A 22 , A and A 22 21 , or = r 2 -µ 2 or k 1 -:\ 1 = k 2 -:\ 2 may be deduced. These are respectively the conditions for the uniformity of AT and of A. By Theorem 1. 1, if one of A and AT is uniform, they both are. In this instance we are done. Apart from row and column permutations the remaining instances fall into three cases, (I) 'no ro no] J (II) [no no no yes no J (III) lyes no Lno yes ( 4. 7) where a quadrant is marked yes or no according as condition ( 1) above does or does not hold for that quadrant. In cases (I) and (II), the row sums of A column sums are constant, or both. holds. Say at least the first possibility Since AT is a nondegenerate design, A does not have repeated rows. Hence 1 = 1 here. 11 and A are constant, or the has the form (a), (b) or (c). e Then each of A 11 Similarly if A 21 12 has constant row sums, then e 2 = 1. 24 But n = e s tart. 1 +e 2 Then A Hence f 1 = 2 contradicts n <!: 3, a condition assumed at the out21 has constant column sums, so that A = 1 for the same reason that e 1 = 1. entire argument can be applied to quadrant A the conclusion that e 2 = f 2 11 does as well. In case (I) alone the 22 instead of A , with 11 = 1. Again the contradiction n = e + e 1 2 = 2 results. In case (II) alone we still have e 1 = f constant row sums and column sums, A and A 21 has constant row sums. 12 1 = 1. Because A has 22 has constant column sums Hence A may by row and column permutations be brought to the form where a 11 is of course either 0 or 1, X and Y are column matrices, each consisting of either n-1 zeros or else of n-1 ones, and A (v, k, A.)-design with v = n - 1. 22 is a This describes the form of tre bordered multiplicative designs discussed earlier and excluded by hypotheses of the theorem. In case (III) we gather that A 11 and A 22 each have consta:at row sums and constant column sums, and hence that A 12 have constant row sums and constant column sums. A 21 then has form (a) or form (b). Note that A 11 and A 21 each Each of A 12 then has constant inner products between distinct rows and constant inner products between distinct columns. and Fisher's inequality (1. 1) may now be 25 applied twice, to A e 1 s f • 1 wise A Hence A 11 T 11 , to get respectively e is a (v', k'\')-design with v' = e is a (v':<, k>:<, \>:<}-design with v>:< = e 22 If A 12 and A whence either \ of A. and to A 11 If A 12 1 21 21 ~ f = f . 1 1 a;:i.d Like-· = f . 2 are both of the form (a), clearly J \ = 0 or \ 2 = O. and A 2 1 1 1 J), 2 = 0, This contradicts the nondegeneracy are both of the form {b) we may calculate explicit! y whence \ \ may be evaluated in two ways to get 1 2 ( 4. 8) The condition ( 1. 2) for (v, k, \)-designs, applied respectively to A and A 22 11 , yields k 12 1 1 - \ v = k 1 -\ 1 With these equalities, (4. 8) may be rewritten as 1 [v':<(v 1-k 1) - (k':<+l)(k - \ 1)] + [k 1(v':<_k':<) - (\ +l)(k':<_\':<)] 1 =0 ( 4. 9) The number of (0, O) entries in two distinct columns of a (v, k, ), }-design is v - 2k + \. Hence v - k ~ k- ),, a nd it can be shown that the inequality is strict for nondegenerate designs. If both A 11 26 and A 22 are nondegenerate (v, k, \)-designs, observe that v'-k' >k k 1 1 1 -\ 1 > \ +1 , · imply that the left side of (4. 9) is positive, a contradiction. At least one of All and A must have 22 is then degenerate, say All. Here A 11 the form 0, I, J, or J-I, apart from row and column permutations. It has neither the form 0 nor the form J, for then case (II) applies instead, and v' > 1 for the same reason. If A 11 has the form I, so that (v , k , \ ) = (v , l, 0), equation ( 4. 9) becomes I I I I In any case v':' - Zk'~ + \'~ ;;;: 0, so that v is degenerate. In fact A 22 = 2 and v'~ = k':' + 1. Hence A necessarily has the form J - I. The total 1 design A then has the form J- I and is inadmissible because A. If A 11 = A. 2 . 1 instead has the form J-I, (4.9) gives We again conclude that v'~ = k':' + 1, and that A has the form J - I. Finally we consider the case when A A 21 is of the form J. 12 is of the form 0 and The case with 0 and J interchanged is essen- tially the same. Still with A 1 11 1 1 a (v , k , \ )-design and with A (v~:', k':', \':' )-design, we compute 22 a 22 27 1 Equate the two evaluations for A. A. to get A. A.':' = k':' 1 2 2 - A.':'v':', whence by the usual necessary condition (1. 2) for (v, k, \.)-designs, A.'A.':' = Multiplicativity for AT gives the dual statement A.\':' = k k':' - A.':'. 1 1 - A. • Hence we have (4. 10) From (4. 10) we see that r 1 - µ , 1 r . .!< ...1..oo r •.t.. r ..,,. = k - A. = k'' - A.''' = (v + k''') - (v + A.''') = r 2 - µ 2 These are respectively the conditions for the uniformity of the designs T A and A • This completes the proof. This argument is by no means delicate. In fact it seems likely that Theorem 4. 1 can be proved without the condition that the size of a block depends only on the weight of the block in both the design and its dual. If this could be done, it would follow from Theorem 3. 2 and the strengthened Theorem 4. 1 that Conjecture 1. 3 implies Conjecture 1. 2. 28 SECTION 5 A GENERALIZATION OF MANN'S INEQUALITY In the definition of a multiplicative or of a uniform design, the requirement that the variety order m and the block order n are equal is highly restrictive. m ~ n in any case. An inequality [10] of Fisher type implies If we replace m = n by the requirement m ~ n, we If in addition k. - A. is J J constant for 1 ~ j ~ n, it is called a partial uniform design. We can call the design a partial multiplicative design. also reasonably require that the row sums of the design are at least two, since a row with no ones or with a single one does not contribute to column intersections. Partial multiplicative designs can of course be created by simply deleting columns of a multiplicative design. To illustrate how easily other partial multiplicative designs can be constructed if m is allowed to grow much larger than n, we let Al, ... , An be any n positive numbers such that JA.. JA.. is integral for 1 s: i < j ~ n. l J Let R . . be the lJ row vector of length n whose ith and jth entries are one and whose other entries are zero. Let A be a matrix containing as its rows pre- cisely JA. A. copies of R .. for each pair i, j satisfying 1 s: i < j s; n. l we sets J lJ = JA 1 + • • · + /An' then m = (s 2 - Al - · · · - An} /2 and k. = s A. - A. for 1 s: j s: n. J J J uniform only when This partial multiplicative design A is If 29 (a) A = ..• = A n' 1 (b) n = 4 (c) A1 -J A2 = ••• = An and or else, Al = A2 -J A3 = A4' 2 Al = (n-3) A2 and ( 5. 1) (n > 4) This example suggests that the study of partial multiplicative designs might profitably be restricted to partial multiplicative designs in which m is not much larger than n, or in which the design is a partial uni- form design. A block design is a design in which the overlap numbers A. are J all equal, and the replication numbers r. are all equal. Of course 1 m 2: n. H. B. Mann [7] and van Lint and Ryser [5] have shown that a variety (row) of a block design is repeated in the design at most m/n times. (A variety of a design is said to be repeated s times in the design if there are precisely s - 1 other varieties in the design which belong to precisely the same blocks as the given variety.) This upper bound m/n can actually be assumed when a block design is formed by repeating each row of a (v, k, A.)-design, with v = n, a constant number u of times. Then u = min. There are partial uniform designs which do not satisfy this bound m/n, such as the design given by (5. lb) when A. A. 3 = A. 4 = 4, for instance. 1 = A. 2 = 1 and Another, more interesting, incidence of failure for partial multiplicative designs is sketched in Figure 1. A 1 1 Here 1 and A':', respectively denote a (v , k', A. )-design and a (v':', k':', :>-..':')- design, and J and 0, respectively denote appropriate matrices of ones and of zeros. I ,. x y A.''' . I Choose the parameters of A':' so that A.':' k':' and If the parameters of A' are given by 30 A' J x repetitions y repetitions 0 A':' Figure 1 1 I v 1 ' then A is a partial multiplicative design. = 1 k (k -l) AI +1 ' Each row is repeated either x or y times, and Clearly min(x, y) ~ min, but max(x, y) :!i: m/n does not always hold. For instance, take I I I 1 1 1 (v':\ k':', \.':' ) = (3, 2, 1) (v,k,\.}=(7,3,l}, x=l, y=2, ( v >!' ' k':' ' \. .:, ) = ( 7 ' 3 ' 1) (v , k , \. ) = (16,6,2), x = 1, y = 2 In either case y .;,, m/n. or The above examples are in fact partial uni- form designs. Mann's proof, however, suggests how a correct analogui:: to his inequality can be constructed. 31 Theorem 5. 1. In a {nondegenerate) partial multiplicative design of variety order m and block order n, let a given variety z with replication number e be repeated s times. Let z belong to the blocks s , •.• , Se' and set 1 K = kl + · · · + ke , L = {/Al + ... + /1e)2 -0.1 +···+A.) e Then s ... ;:a m{K+ L) - K 2 2 {5. 2) me +K+ L- ZKe Proof: Consider the incidence matrix of size m by n of this partial multiplicative design. Permute the rows of A so that the s copies of the row corresponding to z occur initially. Also permute the columns of A so that the e ones of the first s rows occur initially. The matrix A then has the form e m n where J and 0 denote appropriate matrices of ones and of zeros. 6 denote here summation over j in the range 1 S: j S: e, and 6 summation over i in the range s+ 1 s: i s: m. Let I denote Let as+ , ... , am be the 1 32 row sums of A 21 . The number of ones in A 21 can be computed in two ways as 1 6 a.1 = 6 k.J - se = K - se The number of ordered pairs of ones on the same row of A (5. 3) 21 can also be computed in two ways as 6 I (6 JA. .) 2 - 6 A.. - se(e -1) a.(a.-1) = 1 1 J J = L - se(e-1) (5. 4) The sum of (5. 3) and (5. 4) is "'\'I u a. 2 1 = K + L - se 2 We see there are K - se ones distributed among them - s rows of A The Cauchy-Schwartz inequality implies that 6 the a. are all equal. 1 1 21 . a~1 is minimized when Hence K+ L - se 2 ;::: (K - se) 2 /(m - s) The quadratic term in s vanishes upon multiplication of this inequality by m - s, so we conclude that (5. 2) holds. This completes the proof. From the Cauchy-Schwartz inequality we also gather that equality holds in ( 5. 2) when and only when the a. are all equal. 1 This condition is met, for example, when A consists of s copies of each row of a bordered design 33 A' =ITT and when the distinguished variety z corresponds to the first row of the matrix A I shown above. The inequality (5. 2) does not have the same great usefulness of Mann's inequality s s.: m/n because the numbers e, K, and L depend on the choice of the variety z in the design, where of course, n do not. m and For completeness we deduce Mann's result from Theorem 5. 1. If, in Theorem 5. 1, the overlap numbers :\. J of the partial multiplicative design have a common value :\, and its Corollary 5. 2 (Mann). replication numbers r. have a common value k, thens s.: m/n. l Proof: A partial multiplicative design so defined is in fact a block design. It is known [8 J that the block sizes k. have a common l value r, and that bk where b = rv , = m and v = n. r - A = rk - :\v , With k. l = r, e = k, K = rk and L = :\k(k-1), inequality ( 5. 2) becomes 2 br+b:\k-b :\ -r k k s ~ k • bk+ r + :\k- A- 2rk whenc e ( 5. 5) 34 - s(bk+ r - A_- 2rk} + r(bk+ A.k+ r - A - 2rk} 2 ;;:: - (br+ bA.k-bA_- r k} + r(bk+ A.k+ r - A_- 2rk} whence (r-s} [(bk-rk} - (r-A.}k + (r-A_}] :::: (b-r}( r - A_}(k- l} ( 5. 6) The identities (5. 5} may be applied to the left side of (5. 6) to obtain (r-s) [(rv-rk} - (r-A.)k + (rk- A_v} J ;;:: (b-r}( r - A_}(k- 1) that is, (r-s} [r-A.}(v-k}] ;;:: (b-r}(r-A.}(k-1) ( 5. 7} The partial multiplicative design of Theorem 5. 1 is nondegenerate, so that r > A. Hence ( 5. 7} becomes (r -s }(v- k} ;;:: (b-r }(k- l} whence r k (k-1} . We finally have r r b s s: r - - (k-1} = - = k k v The first of the identities (5. 5} is invoked again at the last equality. Hence s s: b /v = m/n, and we are finished. 35 REFERENCES [l] R. C. Bose, "A Note on Fisher's Inequality for Balanced Incomplete Block Designs", Ann. Math. Stat. ~ ( 1949) 619-620. [2] W. G. Bridges, "Some Results on A.-Designs", J. Combinatorial Theory ~ ( 1970), 3 50-3 56. [3] N. G. de Bruijn and P. Erd6s, "On a Combinatorial Problem", Indagationes Math . .!..£ (1948), 421-423. [4] Earl Stanley Kramer, On A.-Designs, Ph.D. Thesis, University of Michigan ( 1969). [5] J. H. van Lint and H. J. Ryser, "Block Designs with Repeated Blocks", to appear in Discrete Math. [6] K. N. Majumdar (alias Majindar), "On Some Theorems i!l Combinatorics Relating to Incomplete Block Designs 11 , Ann. Math. Stat. 24 ( 1953), 377-389. [ 7] Henry B. Mann, "A Note on Balanced Incomplete Block Designs", Ann. Math. Stat. 40 (1969), 681-687. [8] H. J. Ryser, Combinatorial Mathematics (Carus Monograph No. 14), Wiley, New York, 1963. [ 9] H. J. Ryser, "An Extension of a Theorem of de Bruijn and Erdos on Combinatorial Designs", J. Algebra 10 (1968), 246-261. ~ [ 10] H. J. Ryser, "Symmetric Designs and Related Configurations", J. Combinatorial Theory~ (1972), 98-111. [11] D. R. Woodall, "Square A.-Linked Designs", Proc. London Math. Soc. (Ser. l) 20 (1970), 669-687.