Number Theory: An Introduction to Mathematics

6 Designs 247

and

x^2 +y^2 =z^2 +w^2 = 2 n− 2 , xz+yw= 0.

Adding, we obtainx^2 =w^2 and hencex=w. Thusz^2 =y^2 and actuallyz=−y,

sincexy+zw=0.

This shows, in particular, that if the upper bound in Proposition 20 is attained for

m=n≡2 mod 4, then 2n− 2 =x^2 +y^2 ,wherexandyare integers. By Proposi-

tion II.39, such a representation is possible if and only if, for every primep≡3 mod 4,

the highest power ofpwhich dividesn−1 is even. Hence the upper bound in Propo-

sition 20 is never attained ifm=n=22. On the other hand ifm=n=6, then

2 n− 2 = 10 = 9 +1 and an extremal matrixAis obtained by takingW=X=J 3

andZ=−Y= 2 I 3 −J 3.

It is an open question whether the upper bound in Proposition 20 is always

attained whenm =nand 2n−2 is a sum of two squares. It is also unknown if,

when an extremal matrix exists, one can always takeW=XandZ=−Y.

6 Designs....................................................

Adesign(in the most general sense) is a pair(P,B),wherePis a finite set of ele-

ments, calledpoints,andBis a collection of subsets ofP, calledblocks.Ifp 1 ,...,pv

are the points of the design andB 1 ,...,Bbthe blocks, then theincidence matrixof

the design is thev×bmatrixA=(αij)of 0’s and 1’s defined by

αij=

{

1ifpi∈Bj,

0ifpi∈Bj.

Conversely, anyv×bmatrixA=(αij)of 0’s and 1’s defines in this way a design.
However, two such matrices define the same design if one can be obtained from the
other by permutations of the rows and columns.
We will be interested in designs with rather more structure. A 2-designor, espe-
cially in older literature, a ‘balanced incomplete block design’ (BIBD) is a design, with
more than one point and more than one block, in which each block contains the same
numberkof points, each point belongs to the same numberrof blocks, and every pair
of distinct points occurs in the same numberλof blocks.
Thus each column of the incidence matrix containsk1’s and each row contains
r1’s. Counting the total number of 1’s in two ways, by columns and by rows, we obtain

bk=vr.

Similarly, by counting in two ways the 1’s which lie below the 1’s in the first row, we

obtain

r(k− 1 )=λ(v− 1 ).

Thus ifv,k,λare given, thenrandbare determined and we may speak of a 2-(v,k,λ)

design. Sincev>1andb>1, we have

1 <k<v, 1 ≤λ<r.