V 43 )5! ' ‘ TI‘I'TI‘M'WIWIXW {4 ~ _; . H .
-'7T=ILEIiiII§I§II§IIIIITIwat?{‘e§,':“"«-<é:<:z‘aés2:46:51": , I

' I

CONTRIBUTIONS TO CONSTRUCTION
OF GENERALIZED YOUDEN DESIGN.
ON CONSTRUCTION OF ORTVHOGONAL
LATIN SQUARES USING THE METHOD
OF SUM COMPOSITION

Thesis for the Degree of Ph. D.
MICHIGAN STATE UNIVERSITY
FELIPE RUIZ
1971

 

 

Yap-“I!

LIBRARY

Michigan State
University

 

This is to certify that the
thesis entitled

CONTRIBUTIONS TO CONSTRUCTION OF GENERALIZED YOUDEN
DESIGN. 0N CONSTRUCTION OF ORTHOGONAL LATIN SQUARES
USING THE METHOD OF SUM COMPOSITION

presented by

Felipe Ruiz

has been accepted towards fulfillment

of the requirements for
Ph.D. Statistics &

Probability

degree in

 

 

M

Ihmupnmuuu

Date February 18, 1972

0-7639

    
       

wn'
. . , IIERII INC.
LIBRARY BINDERS
Sllllfllfllfl IICIIBAI

   

ABSTRACT

CONTRIBUTIONS TO CONSTRUCTION OF GENERALIZED YOUDEN DESIGN.
ON CONSTRUCTION OF ORTHOGONAL LATIN SQUARES
USING THE METHOD OF SUM COMPOSITION

By

Felipe Ruiz

The present thesis deals with two independent problems.

In the first part (Chapters I and II) we investigate generalized
Youden designs while in the second part (Chapter III) we further
study the method of sum composition of Latin Squares introduced

by Hedayat and Seiden (1969).

Generalized Youden designs were introduced by Kiefer (1958)
who proved E-optimality and, in the presence of some divisibility
conditions, D-Optimality. In Chapter I we study optimality in
detail and investigate relationships among the parameters; several
necessary conditions for existence of GY-designs are found, and
the chapter closes with the usual analysis of these designs.

Chapter II is devoted to the construction of GY-designs;
using well-known combinatorial systems such as finite geometries,
symmetric balanced incomplete block designs, Latin squares, etc.
We construct several infinite families of GY-designs; the last
construction of this chapter provides an infinite family of GY-
designs whose parameters do not satisfy Kiefer's divisibility con-

ditions and which are not D-optimum.

Felipe Ruiz

The method of sum composition of Latin Squares allows us
in certain cases to construct O(n,2) sets by composition of a
O(n1,2) and a O(n2,2) set, n = n1 + n2. It is assumed that
O(n1,2) is based on GF(n1) and formed by A(x), A(y), where
for any r E GF(n1), r i O, A(r) is the n1 X n1 square with

element rai +-a in its (i,j) cell, 01,0 6 GF(n1).

J J
2
Hedayat and Seiden have further assumed that xy = a
for some a E GF(n1); we free ourselves from that restriction
and obtain further constructions. We also prove that the con-

dition xy = 02 is a necessary one in 12 of the 24 possible

patterns of composition of O(pa,2) and 0(3,2),

2
Removal of the restriction xy = 0 produces compatibility
equations which are non-linear in both x and y, therefore
allowing the possibility of extending the method of sum composi-

tion to construction of O(n,3) sets.

CONTRIBUTIONS TO CONSTRUCTION OF GENERALIZED YOUDEN DESIGN.
ON CONSTRUCTION OF ORTHOGONAI.IATIN SQUARES
USING THE METHOD OF SUM COMPOSITION

By

Felipe Ruiz

A THESIS
Submitted to
Michigan State University

in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Statistics and Probability

1971

ACKNOWLEDGMENT

I express my gratitude to the Department of Statistics
of Michigan State University for their infinite patience with
my rather unorthodox ways; to the Michigan Department of Public

Health for their lavish economical support.

To Dr. Esther Seiden I owe more than I could possibly

say here.

iii

Chapter

II

III

TABLE OF CONTENTS

ANALYSIS OF GENERALIZED YOUDEN DESIGNS ...........

Introduction .................... ...... ......
Optimality of GY-designs ....................
Properties of GY-designs ....................
Analysis of GY-designs ......................

Q

H‘F‘P‘P‘
O
#th-A

CONSTRUCTION OF GENERALIZED YOUDEN DESIGNS .......

GY-designs with b 0 or k = O .....

O 1 =

(V) (V)

2.2 Geometric Construction of GY-designs ........
2.3 A Class of Non D-optimum GY-designs .. .......

SUM COMPOSITION OF LATIN SQUARES .................

1 Introduction and Definitions .. ........... ...
2 The Method of Sum Composition .. ..... ........
.3 Sum Composition of O(n,2) Sets ............
4 Construction of O(n,2) Sets by the Method
of Sum Composition ..... .. ............. . .....
3.5 Composition of O(pa,2) and O(3,2) Sets

BIBLIOGRAPHY .. ...................................

iv

Page

I-‘

NUth—a

17

20
38

44
44
46
48

52

66

CHAPTER I

ANALYSIS OF GENERALIZED YOUDEN SQUARES

1.1 Introduction

Frequently in scientific investigations the experimenter
wishes to study the effect of several variables that he can control
on a response or dependent variable which he can observe and measure.
The variables under the control of the experimenter are called
FACTORS and they would appear at various categories or IEVELS; a
situation in which every factor appears at some level is a
TREATMENT. Clearly if a design contains m factors F1,F2,...,F ,

m

where F assumes si levels, i = l,2,...,m, there are 31.32 ... s

i m

possible treatments. A design which includes exactly one observation
on each of the 31,...,sm possible treatments is called a COMPLETE
FACTORIAL DESIGN; if several observations are made on each treat-
ment it is called a FACTORIAL DESIGN WITH REPLICATES; if all factors
assume the same number of levels (i.e. ai = s, i = l,2,...,u0 the
design is SYMMETRIC; a COMPLETE SYMMETRIC DESIGN consists therefore
of all sm m—tuples of the 3 levels.

If the number of factors is large, the number of treatments
necessary for a complete design becomes prohibitive; hence the need
for fractional replication and confounding.

Fractional replication was studied, among others, by Finney

(1945), Plackett and Burman (1946) and Plackett (1946). Essentially

a l/sn replication of a complete sm factorial design is a partition
of the 3m treatments into blocks of sm-n treatments each; the
partitioning is said to be of STRENGTH t if no effect of interaction
of t or fewer factors is confounded with the block effect. By

using fractional replication the experimenter can discover cheaply

at the early stages of his research which factors among many have

an important effect on the product.

Balanced Incomplete Block designs are an example of fractional
replication of complete two-factor designs, while Latin Squares,
Youden Squares and Generalized Youden designs are fractional
replications of three-factor designs.

Definition 1.1.1: A (v,b,k,r,x) Balanced Incomplete Block (BIB)
design is an arrangement of v elements (varieties) in b subsets
(blocks) of k varieties each, such that any two distinct varieties
occur together in I blocks.

Then any variety occurs in r blocks and
vr = kb , x(v-l) = k(r-l)

If v = b the BIB design is said to be Symmetric.
Definition 1.1.2: A Latin Square g£_9£gg£_ g_ is a square matrix
of order n on a set of n varieties such that every row and
every column is a permutation of the set of varieties.
Definition 1:1;25 A (v,k) Youden design is a k X v matrix on
v varieties such that with the columns as blocks it is a (v,k,x)
symmetric BIB design, and each row is a permutation of the varieties.

Definition 1.1.4: A (v,b,k,r,x1,x2) Generalized Youden (GY)

 

design is a k X b matrix on a set of v varieties such that the

following conditions are satisfied:

a) Every variety occurs r times.

b) Every variety occurs either m or mml times in each row,
as well as either n or n+1 times in each column, where

b
m is the integer part of 3' and n is the integer part of
k

V

c) Every two distinct varieties occur together X1 times in the
same row and X2 times in the same column.
Generalized Youden designs were first introduced by Kiefer
(1958), who proved some optimality prOperties of those designs
and gave two examples with two and four varities respectively;
however he made no attempt to construct GY-designs.

In the next paragraph we examine closely the Optimality

properties of GY-designs.

1.2 Optimality of GY-designs

Let the linear hypothesis to be tested be R8 = 0, where
a is the p-rowed vector of parameters to be estimated and R is
a q X p matrix of rank q s p; by means of an apprOpriate linear
transformation this hypothesis can be reduced to the canonical

form

The covariance matrix of the best linear estimate of B is

cov(§) = (xTX)‘1xT cov(Y)X(XTX)-1 = (xTxflo2

where X is the matrix of the design and Y is the vector of
2
observations with covariance matrix a I.
We restrict ourselves to the use of the F-test whose power

function is a monotonically increasing function of the parameter

x = 1; BTPTIP (XTXYLPTJPe

Q

where P = ( ), 0 being a r X 3 matrix of zeros (see,

I ,0
q q,p-q r93
for instance, Tang 1938).
2

It is known that the minimum value of o X on the unit
sphere (PB)T(PB) = l is equal to the smallest eigenvalue of
P(XTX)-1PT; similarly the greatest eigenvalue equals the maximum
value of 02X on the sphere. Therefore we maximize the minimum
power of the F-test on the contour (PB)T(PB) = l by maximizing
the smallest eigenvalue of P(XTX)-1PT.

. . * T -1PT

For a given design d we will de31gnate Ad = P(X X)
Remembering that the determinant of a square matrix equals the
product of its eigenvalues, we are naturally led to the following
criteria.

Definition 1.2.1: A design d is said to be E-optimum in a class

A of available designs if

* *
min E(A ) = max min E(A ,)
d , d
dEA
where for any square matrix A, E(A) represents the set of eigen-
values of A.

Definition 1.2.2: A design is said to be D-optimum in a class A

of available designs if

*
det(Ad) = max det(A:.) .
d'EA

Both criteria of optimality were introduced by Wald (1943),
who also proved D-optimality of Latin Square designs. Keifer (1958)
has proved that GY-designs are E-optimum, and also that they are
D-optimum if either k or b is a multiple of v. We will show
in the next chapter that if neither k nor b are mutliples of
v the GY-design may fail to be D-Optimum. The problem presents
itself of determining, in the absence of the divisibility condition,
whidh cases give D-optimum GY-designs and which cases do not; we
were so far unsuccessful in solving this problem but hOpe that

further research will overcome the difficulties.

1.3 Properties of GY-designs

The row-incidence matrix of a GY-design is a v X k matrix

A = (a ), where a, is the number of times that the i-th variety

ij ij
appears in the j-th row; of course aij € {m,m+l}.

Similarly, the column-incidence matrix of a GY-design is

 

13

that the i-th variety appears in the j-th column; evidently,

a v X b matrix B = (bij)’ where b, is the number of times

b ,m+ .
ij E {m 1}
Notation: The quotient and remainder of the division of an integer

a by another b will be written [3] and a respectively.

(b)
Theorem 1.3.1: In a GY-design
i) The number of rows containing a given variety m+1 times

is the same for all the varieties, and equals r(k).

ii) The number of columns containing a given variety n+1 times

is the same for all the varieties, and equals r

(b)°

iii) The number of varieties occurring mfil times in a given row
is the same for all rows, and equals b(v)'

iv) The number of varieties occurring n+1 times in a given
column is the same for all columns, and equals k(v)°

2529;: Let 0(1) be the number of rows which contain the i-th

variety m+1 times. We must have

a(i)(m+1) + (k - 01(1))m = r , or

(1) 01(1) + km = r
therefore 0(1) is independent of i. Obviously kb = rv, therefore
[E1 = [g] = m, and thus r = mkn+ r(k). Substituting in (1) we
obtain the desired result
(1)
= r .
0’ (k)

The proofs of ii), iii) and iv) are entirely similar and

therefore omitted.

Theorem 1.3.2: Let A be the row incidence matrix of a GY-design.

Then
(1) AAT = (b - v)I + J
r kl v N1 v
(2) A' = AT' = b‘
Jk er ’ JV Jk

where AT is the transpose of A, I is the unit matrix, J =.J
v v v,v
is the v X v matrix of 1's, jn is the n X 1 vector of 1's.

Similarly for the column incidence matrix B,

T
BB = (rk - szflv + XZJv

Proof: Let a(1) be the l X k vector whose j-th component is

811; then the element in the i-th row and L-th column of AAT is

(i)a(L); clearly a(i)a(L) = A if

1
mac)

let us count the number of occurrences

 

the inner product a i # L.
In order to obtain a
in the same row of the design of pairs containing a particular

variety vi; on the one hand V1 is paired 11 times with each

of the remainder v-l varieties; on the other hand if vi appears

aij times in the j-th row of the design it will form pairs with
each of the b - aij varieties (not necessarily different) left in
the row, each pair being counted 3, times, for a total over the

k U
rows of 2 (b - a,j)aij = (bjk - a(i))a(i); the two counts provide

i=1 1
us with

. (i) (i) _
(ka - a )a - 11(v-1)
which gives
a(1)a(1) = rb - x1(v-1)

and therefore the result
AAT - (rb - )I -I- J
11V v I1 v'

Part (2) is self evident.

Theorgm_l.3.3: In any GY—design
2

(l) Xik s r

(2) x21. 5 3

Proof: For real numbers a1,a2,...,an it is always true that

n 2
( 2 81) s n
i=1 i

2
a .

1 i

IIMD

Applying this inequality to the components of the vector a(1)

and using the previous theorem we obtain
2
r 5 k(rb - x1(v-l))

which, remembering that kb = rv, gives

0 s (v-l)(r2 - ilk)

and therefore the theorem.

Part (2) is proven in the same fashion.
Theorem 1.3.4: In any GY-design
xlv s rb

yzv s rk .

Proof: Schwartz inequality gives

(a<i)a<t>)2 S (a<i>a(i))(a<t)a<t>)

By Theorem 1.2.2 this gives

TI s [rb - x1(v-1)]2

2

or o s [rb - x1<v-1)]2 - 11

0 S [rb - x1(v-l) + x1][rb - xlv] .

The first factor of the product is always positive, since

(i) (i)
rb - x1(v-1) + N1 = a a + N1 > 0, and hence so is the second,
giving the theorem.

Part (2) is similarly proven.

Theorem.1;§;§; Let (vi’YL) be a pair of distinct varieties;
let ab, a1, 20 be the number of rows containing the pair
(v1,vL) m2, (m&1)2, m(m&l) times respectively, and similarly
let 80’ 81’ 23 be the number of columns containing the pair
(vi,vL) n2, (n+1)2. n(n+l) times respectively. Then a0, a1,
a, 60’ 51, B are independent of the pair (vi,vL) and

a=rb-)‘1v B=rk-)‘2v
a0 = k - r(k) - rb + Alv 60 = b - r(b) - rk + xzv
01 = r(k) - rb +-x1v 61 = r(b) - rk + xzv .

Proof: Looking at the row-incidence matrix we easily establish

the following relations among a, 00, a1:

Zq+a0+a1=k

a+a1 =r(k)
(1)

ll
>4!

0101112 + a1(nrl-1)2 4' 2a m(m+l)

(01 + 0.0)an2 + (a + 011) (m+1)2 rb - Mew-1) .

The first equation expresses the fact that the row-incidence matrix
has k columns, the second gives the number of rows which contain
the i-th variety mnl times, which we know by Theorem 1.2.2 to be

r(k), while the last two are immediate consequences of
a(l)a(L) = 11 a(1)3(1) = rb _ x1(v-1)
Subtracting the 3rd equation from the last one we obtain directly

a=rb-)(1v

10

independent of i,L; substituting in the first two equations we

obtain

= r - rb + xlv

“1 (k) =k'r

- b + ,
“o (k) r T1"

In exactly the same way we will obtain the corresponding expressions

for 5, BO, 81'

Theorem 1.3.6: In any GY-design

 

3’ vr(k) ‘ kb(v) br(k) = rb(v)
(I) b) (V-1)(rb - XIV) = b(v) (k - r(k))
r (b - l)
_ (k) (V)
c) 11 - m(r + r(k)) + v-l
8’ vr(b) = bk<v> kr(b) = rk(v)

(II) b) (V‘1)(rk - sz) = k(V) (b " r(b))

r (k - 1)
c) 12 = m(r + r (b) (v)

(b)) + v-l

Proof: If A is the row-incidence matrix of the GY-design, then

A - m Jk v is the incidence matrix of a BIB design with parameters
’

(r',b',k',r',x') where

(V) (k)

Therefore we must have

(1) vr( = kb

k) (v)

(2) (1107-1) = r (b - 1)

(k) (V)

11
Equation (1) together with rv = kb gives
br = rb

(k) (V)

therefore proving part a) of I.

By previous Theorem 1.3.5 we know that
= - + .
(3) a1 r(k) rb xlv
Substituting in (2) we obtain
(v-l)(rb - xlv) = r(k)(v - b(v))

Using the first result r v = kb we obtain part b) of (I).

(k) (V)
From (2) and (3) we obtain

r ‘[b(v) -l]
v-l +rb-r(k).

 

(4) M" =

Notin that b = b - mv and r = mK + r and substitutin
g (V) (k) g

in (4) we obtain after simplifying

(b - m - l)

v - l

1‘
‘0‘) +mr.

R1 =
Obsering that b - m = m(v-l) + b(v) we obtain the desired result

)+ r(lower) ' 1)

k1 = m(r + r v _ 1

00

Part (II) is similarly proven.

Corollary 1.3.1: In any GY-design rb = xlv, or equivalently
rk = xzv, if and only if b,(k), is a multiple of v; otherwise
rb > xlv, (rk > xzv).

Proof: It is an immediate consequence of part b) and Theorem 1.2.4.

12

Corollary 1.3.2: The matrix AAT,(BBT), is singular if and only if
b,(k), is a multiple of v.

Proof: By Theorem 1.2.2 we know that

T
AA = (rb - xlv)lv + lev .

Since the eigenvalues of XI v are 0 and xlv with multiplicities
v-l and l reapectively, the eigenvalues of AAT are rb - xlv
and rb - xlv + xlv, with multiplicities v-l and 1, therefore

its product, which coincides with det(AAT), is rb(rb - xlv)v-l,
which by previous corollary is zero if and only if b is a multiple
of v.

Corollary 1.3.3: A necessary condition for the existence of a

(v,b,k,r,x1,x2) GY-design is that

(bar) ' 1) and imam)

v - l v - 1

rue ' 1)
both be integers.
2522;: It is an immediate consequence of part c) of the theorem.
Corollary 1.3.4: In any GY-design k.2 v.

2322;: It is Fisher inequality for the BIB design with incidence
matrix A - va.

Assumption: Since the transpose of a GY-design is also a GY-design
we will assume from now on that b 2 k; we will also assume b > v,

since b = v reduces the GY-design to an ordinary Youden design.

1.4 Analysis of GY-designs

(v,b,k5r,x1,x2) - GY-designs serve as designs for factorial

experiments with three factors (row, column and variety) at k,b,v

13

levels respectively. The row factor at the i-th level will be
spoken of as the i-th row, and similarly for the other factors.
Every entry of the GY-design represents a treatment, so we have
only N = kb treatments instead of the kbv which will appear
in a complete design.

Let yijL be the observation on the L-th variety in the
i-th row and j-th column; of course L is uniquely determined by
i,j, that is L = L(i,j) where the function L is given by the

design. The model is

= + + +
u- ozi Bj'i'YL eijt

yiJL
where u is the overall mean, a1, Bj’ YE are main effects and
eijL is the random error, that is we assume that no interactions
of two or more factors are present. We further assume that the
random errors are normally distributed around zero with covariance

2
matrix a I.

The model can also be described in matrix notation:
Y = X3 + e

where Y is the N-rowed vector of observations, 8 is the p-rowed
vector of parameters to be estimated (overall mean plus k +'b +-v
main effects), e is the N-rowed vector of errors and X is the
N X p matrix of the design; the normality assumption can be
expressed as Y ~ N(Xa,oI) that is, Y has a multivariate normal
distribution with mean X3 and covariance matrix 021.

We will associate the positive integer a(i,j) = (i-l)b + j

with the (i,j) cell, or plot, of the GY-design. Clearly for

14

every positive integer n sfikb there is exactly one pair (i,j),
or plot, such that a B a(i,j); accordingly, the plot in the i-th
row and the j-th column will be called the a-th plot, and the
corresponding observation the a-th observation, with a = a(i,j).
The matrix X is a matrix of zeros and ones whose rows
correspond to the plots and whose columns correspond to the para-
meters to be estimated. Clearly the column corresponding to p
is a column of 1's only, which we will write as last. Since each
of the k levels of the row factor appears exactly once with each
of the b levels of the column factor, each of the k columns
corresponding to the parameters “1’ i = 1,...,k contains exactly
b ones, each of the b columns corresponding to the parameters
51, j = l,2,...,b contains exactly k ones and the product of the
columns corresponding to ai and Bj is always 1 for any
i = 1,...,k, any j = 1,...,b. Finally the column corresponding
to the parameter yh, h = 1,2,...,v, has a one in the a(i,j) row
if and only if L(i,j) = h and contains exactly r ones. The

matrix X therefore looks like:

’1 o...o 1 o...o o...1...o 1I
10...o o1...o o..1...o 1
10...o oo...1 1
010000 100000 1
01...o o1...o 1
x8 ..... .....
01...o oo...1 1
oo...1 1o...1 1
oo...1 01...0 1
Loo...11o...1 1

 

 

Let

A1 is a b

15

us introduce the matrices A1, Bi, i = 1,...,k where

X k matrix with 1's in the i-th column and zeros else-

where, and B1 is a b X v matrix with a one in the cells

(j,L(i,J)).

of Ones, j
of a matrix

X can be ex

The

so that if

are given by

It is a stra

where A, B

matrices of

j = 1,2,...,b and zeros elsewhere. J will be a matrix
a column vector of ones; we will indicate the dimension
with subindices when necessary. Using these matrices

pressed as

 

 

normal equations are
XIY = xTx B

T . . .
X X is non-Singular the least square estimates E

E = (xTX)'1 XTY .

ightforward calculation to arrive at

Pblk Jk,b A:,v bit“
JbK k1b B:,V k"jb
Avk Bv,b rIv rjv

n: w.

 

 

are, of course, the row-incidence and column-incidence

the GY-design.

16

The normal equations can also be obtained directly from

the model. With the usual notation and side conditions

we obtain

3-3
II
x.
0"
t)

r-i

II

x‘
t»
+

W
‘0)
“'1

where, of course, a are the general entries in the row-

b
L1’ L1
incidence and column-incidence matrices of the GY-design.

In order to eliminate the row and column effects let us

compute

kb T - b 2 b ,T , - k z a T =

..L 1 L] .J. i 'Li i..
= kb “ - b b b “ - k a . a “ _ b “ =
”’4, 331.1,?th $4,132;in r”

kbr It - kbr a - b §L(rk - 12v) - k yL(rb - 11V) =

. 2 .

YLVEk X1 + b 12 - r ] - kbr p .
2

Dividing by r v,

2
k Al +'b 12 - r

Y = y
r2 L ... ..L

 

-12
Ljy-J. r i aLiyi”

- %-z b
1
which gives the variety effects ?L; the row effects &i and column

effects éj can now be easily obtained; from the first normal equa-

tion we obviously obtain fl = y .

CHAPTER II

CONSTRUCTION OF GENERALIZED YOUDEN DESIGNS

2.1 szdesigns with b(v) = 0 9r_ k(v) = 0

Theorem 2.1.1: There exist GY-designs with b = mv, k = nv for

 

any positive integers m, n and v.

Proof: Let {Li j‘i = 1,...,n; j = 1,...,m} be a collection of
9

mn Latin Squares of order v, not necessarily different. Then

the nv X mv matrix

11 12 ... le.I

 

 

LLnl Ln2 ... an

is a GY-design, since clearly every variety occurs m times in

each row and n times in each column, and every pair of distinct
. 2 . 2

varieties occur together in the same row m k times and n b

times in the same column.

Theorem 2.1.2: If there exists a symmetric BIB design with para-
meters (v,k',x), k' s v, then there exists GY-designs with para-
meters v = v, b = mv, k = nv +'k' for arbitrary positive integers
m, n.

nggg: The other parameters of the GY-design are easily established

to be

17

18
r=mk.11_-m2k.12=mT1+n(k+k')].

Let {Bi‘i = 1,...,m} be a collection of symmetric BIB designs,
not necessarily different, with common parameters (v,k',x); each
B1 can be converted to a Youden Square Yi by reordering the
varieties within each block (Smith and Hartley, 1958). Let

{Liin = 1,...,n; j - 1,...,m} be a collection of Latin Squares

of order v, not necessarily different. We claim that the matrix

F‘ 1
Y1 .. Ym
L11 ... le
D = 2
Lnl 00. Ln’m
L. .J

 

 

is a GY—design.

a) Every variety appears v times in each Latin Square and k'
times in each Youden Square, for a total of mnv + mk' = mk = r
times.

b) Every variety appears once in each row of each Youden Square
and of each Latin Square, therefore any pair of distinct
varieties occurs together in the same row of D, mzk = 11 times.

c) Let x,y be two distinct varieties; each Youden Square has 1
columns containing both x and y, (k' - 1) columns containing
x but no y, another (k' - 1) columns containing y but no
x, and the remainder v - X - 2(k' - 1) columns will contain
neither x nor y. Therefore the two varieties x,y will
appear together in the same column in D, [x(n+l)2 + 2(k'-x)n(n+l)

+ [v - I - 2(k'-x)]n2]m = m[x + n(k.+ k'f] = 12 times, which

concludes the proof.

19

Note that the existence of a symmetric BIB design is needed
to carry out the construction but is by no means necessary for the

existence of the GY-design, as the following theorem shows.

Theorem 2.1.3: Let s = pn be a power of a prime. Then there

exists GY-designs with parameters

v=s +l,b=s(sz+l),k=s+l.

Proof: The other parameters are easily computed
2 2
r=s(s+l),x1=s(s+l),x2=(s+l)(23 +23+l)

Now let Q be a non-degenerate elliptic quadric in PG(3,s);

it contains 82 + 1 points and each plane of the geometry inter-
sects the quadric Q in either one single point (tangent plane)

or in exactly 8 +'l points forming a non-degenerate quadric

Since Q contains 32 + 1 points, there are s2 +'l tangent

planes and s3 +'32 + s+l - (82 + l) = s(s2 +'l) non-tangent planes.
Taking the points of Q as varieties and the non-tangent planes

as blocks we obtain a BIB design with parameters

v = $2 + 1, b = 3(32 + l), k = s + l, X = s + 1 .

This design has the property that every triple of varieties occurs

in exactly one block, which is a translation of the fact that any

three points of the quadric determine a unique non-tangent plane.
Agrawal (1966) has proved that in any BIB design with

b = mv, the varieties can be rearranged within each block (column)

so that every variety appears in a row m times; the rearrangement

is achieved using systems of distinct representatives, which in

20

turn can be constructed with Hall's algorithm (Hall, 1956). After
the rearrangement of varieties, the BIB design becomes the desired
GY-design.

Note that no symmetric BIB design exists with v = 32 + l,

k = s +'l.

2.2 Geometric construction _§_§X;designs

In this section we will consistently make use of the follow-
ing conventions and notation.

s will designate a power of a prime number, s = p“; GF(s)
will stand for the Galois field with 8 elements; EG(2,s) will
designate the Euclidean plane based on GF(s).

Let a0 = 0, a1 = l, a2,...,as-1 be the 3 elements of
GF(s) in some order; let L1 be the line with equation x = 01,

i = O,l,...,s-l and similarly let Lj i be the line with equa-

tion a x'+ y = a1, i,j = O,l,...,s-l; the 3 parallel lines

J
Li, 1 = O,l,...,s-1 form a pencil X, and for each aj E GF(s)

the 5 parallel lines i = O,l,...,s-l, form also a pencil

Lj’i’

Y1; the order in GF(s) induces an order of the lines within each

pencil as follows: for any ai’ aj, an E GF(S),

Li < Lu it and only if ai < au
Lj,i < Lj,u if and only if 0i < an .
The lines L1 and Lj’i will be referred to as the i-th lines
of pencils X and Y1 respectively.

Any point P of EG(2,s) is uniquely determined as the

intersection of a line of the pencil X and a line of the pencil

21

Y We can therefore order the points of EG(2,s) as follows:

0.
Let P, P' be two distinct points of EG(2,s) given by

P=L1nLOJ’ P'gLi'nLOj'

then P < P' if and only if Li < Li. or i = i' and L0,j < L0,j"

We will assign the numbers 0,1,...,sZ-l to the 32 points
of EG(2,s) in that order. In all the algebraic manipulations
applied subsequently these serial numbers of the points will be
treated as actual numbers.

Lines will be viewed as s-tuples of their points enumerated
in increasing order, and pencils as square matrices of points whose
i-th row is the i-th line of the pencil, i = O,l,...,s-l.

We will use the n X n permutation matrices Tn and en

defined as follows:

By premultiplying a m X n matrix A by Tm we achieve a cyclic
permutation of its rows; by postmultiplying A by gn we achieve
a cyclic permutation of its columns. The subindices will be dropped
whenever the dimensions of the matrices involved are clear.

We will also introduce the transformation a defined on the

points of EG(2,s) as follows:

0(x,y) = (yet) V (x,y) E EG(2.S) -

Y will denote the s2 X 3 matrix

 

 

r' H
Y0
Y1;
Y = I
s-l
Y C
L 8'1 .I

and G will be the s2 + s X 5 matrix

“1:1 -

Theorem 2.2.1: There exist GY-designs with parameters v = $2,
b=k=s(s+l).

Proof: The other parameters are

'1
II

(s + l)2 , m = n = l , 11 = 12 = $2 + 33 + 3

2
OI=S ,aO-S-S-l,a1=1.

We will take the varieties of the design to be the points
of EG(2,s).

We claim that each column of the matrix Y is a permuta-
tion of the set of the 82 points.

Suppose that the point a appears twice in the j-th

column of Y for some j; then we must have

{a}=ta.flt =4, (It

, 1 j+q B , k j+8

for some a,e,i,k, a f a, which is impossible since the lines

and L are different and parallel.

LJ'I’OI 1+8

T
Similarly each row of oY is also a permutation of the

points of EG(2,s).

23

We now claim that the matrix
X oY

Y L

where L is any Latin Square of order 32, is the desired GY-design.
First note that oXT = X, therefore the first 3 rows of
D are the lines of EG(2,s) written vertically, and we have
natural one-to-one correspondence between the lines of EG(2,s)
and the rows and the columns of D.
Note that a point occurs twice in a row or column of D
if and only if it belongs to the corresponding line; consequently
since no two lines have more than one point in common any two rows
or columns will have at most one point occurring twice in common.
Therefore a1 8 Bl = l and we conclude that D is a GY-design.

Example 2.2.1: For 3 = 4 we have

v = 16 , b = k = 20 , r = 25 , 11 = 12 = 31
o 1 2 3 o 4 8 12
6 7 1 5 13
x= 91011 YO= 2 61014
12 13 14 15 3 7 11 15
o 5 1o 15 o 6 11 13
1 4 11 14 1 7 1o 12
Y1 = 2 7 8 13 Y2 = 2 4 15
3 6 12 3 5 14
o 7 14
1 6 15
Y3 = 2 5 11 12
3 4 1o 13

 

0 l 2 3

4 5 6 7

8

12

11

10

14
15
12

13

9
13

10

ll

13

12

15

14

10 11

14 15

10 14
11 15
15 O
14 1
l3 2

12 3

5 ll

4 10

2 6 10

3 7 11

10 ll 12
11 12 13
12 13 14
13 14 15
14 15 0

15 O 1

12

13

14

15

10

ll

12

l3

14

15

24

10

15

10

ll

12

l3

14

15

14

11

10

11

12

13

14

15

13

10

ll

12

l3

14

15

10

ll

12

l3

14

15

10

11

12

13

14

15

10

13

10

ll

12

13

14

15

15

10

ll

12

l3

14

15

11

12

11

12

13

14

15

13

12

l3

14

15

10

ll

15

13

14

15

10

11

12

l4

14

15

10

ll

12

13

10

15

10

11

12

l3

l4

 

25

Remark: It seems worthwhile to explain the main idea behind the
construction of the above GY-designs. The points, the lines and
the points within the lines were ordered in such a way that the
corresponding columns Of each of the matrices representing the
parallel pencils Yj’ j = O,1,...,s-l, consist of all elements
of the same row of the matrix X. Moreover since for x = 0 the
equation y = a1 is the same as ajx + y = ai the columns of
each of these matrices consisting of the elements of the row of
the X matrix for which x = 0 are also identical with respect
to the order of their elements within the columns. Consequently,
since no two lines of distinct parallel pencils can have more
than one point in common, the remaining 3 - 1 sets consisting
of 3 columns whose elements belong to the same row of the X
matrix x = ai’ ai # 0, form distinct permutations of these elements
of a specific structure. Namely each element will belong to one
and only one set of 3 columns and will occupy within the set
all the distinct 5 positions of a column. Hence the 3 distinct
powers of the g Operation, which permutes cyclically the columns
of each of the Yj parallel pencils, will place each element in
each of the distinct columns of the matrix Y.

Analogous reasoning applies to the dYT matrix with y
and 7 replacing the roles of x and g respectively.

For the next construction we need the following lemma.
Lemma 2.2.1: There exist Latin Squares of order 32 which can
be split into 8 groups of 3 columns in such a way that every

row in each group is a line of EG(2,s).

Proof: We claim that

26

r’ 3" 1
Y0 TYO T 1YO
S-
Y1; TYlg T 1Y1;
L = I Z
8-1 8-1 s— s-l
LYS‘lg TYs-lg ... T 1YS_1C 3

 

 

is the desired Latin Square.
We have already shown that each column of Y is a per-
mutation of the 82 points, therefore so is every column of L.
We must show now that each row of L is also a permuta-
tion of the 82 points; but since Ti is not the identity if
0 < i < s-l each row of L is made out of 3 different lines
belonging to the same parallel pencil and therefore no point can
occur twice in the same row.
Exggple 2.2.3: We have already constructed EG(2,4). The Latin

Square can now be exhibited as follows:

0 4 8 12 l 5 9 13 2 6 10 14 3 7 11
1 5 9 l3 2 6 10 14 3 7 11 15 O 4
2 6 10 14 3 7 ll 15 0 4 8 12 l 5 9
3 7 ll 15 0 4 8 12 l 5 l3 2 6 10
5 10 15 O 4 ll 14 l 7 8 13 2 6 9 12
4 ll 14 l 7 8 13 2 6 9 12 3 5 10 15
L = 7 8 13 2 6 9 12 3 5 10 15 O 4 11 14
6 9 12 3 5 10 15 O 4 ll 14 l 7 8 13
11 13 0 6 10 12 l 7 9 15 2 4 8 l4 3
10 12 1 7 9 15 2 4 8 l4 3 5 ll 13 0
9 15 2 4 8 l4 3 5 11 13 0 6 10 12 l
8 14 3 5 ll 13 0 6 10 12 l 7 9 15 2
14 O 7 9 15 l 6 8 12 2 5 11 13 3 4
15 1 6 12 2 5 ll 13 3 4 10 14 O 7
12 2 5 11 13 3 4 10 14 0 7 15 l 6
l3 3 4 10 14 0 7 9 15 l 6 12 2 5

15
12
13
14

NHOW

bwom

10

\O

11

27

An attractive feature of this family of Latin Squares is
that they are split into s2 subsquares each of which contains
each of the varieties once. We conjecture that they are orthog-
onally mateless, but were so far unsuccessful in proving it.
Orthogonally mateless Latin Squares of order k are known to
exist for arbitrarily large and even k, but their existence is
unknown for arbitrarily large k when k is odd. Our conjecture,
if true, will give a construction of an orthogonally mateless
Latin Square for all k of the form k = p2“, p a prime number.
Theorem 2.2.2: There exist GY-designs with parameters v = 32,

b = 8(82 - l), k = s(s+l).

Proof: The other parameters are

r=(s+l)2(s-l) m=s-l n=l
-2 _2
r(b) - s - l. r(k) — s - l

7.1 = (s-l)(82 - 1)(s + 2) + (32 - S - 1)

1,2 = (52 - 1) (s + 2) + (3-1)

_ = _2
01-8 010 1 (11—8 -s-1

6 = 52 - s 80 s3 - 232 + l 51 = s - l .

Let L be the Latin Square of order 32 constructed as
in the previous lemma. For every point a, let pL(a) be the
transpose of the column vector of L whose first component is a
with that first component missing, this notation is consistent
since each row of L is a permutation of the points of EG(2,s).
Thus pL(a) is a (82-1)-tuple of distinct points and it does not

contain the point a; is a mapping defined through the Latin

pL

Square L; in matrix notation

pL<a1 = cL(a>T

2
s -l J

 

 

where cL(a) is the column of L whose first element is a.
For any m X n matrix A = (aij)’ pL(A) will be naturally

understood as the m X n(sz-l) matrix pL(A) = (pL(aij))°

Now let G = [:j] and consider the s(s+l) X s(sZ-l)
matrix D = pL(G).

We will prove first that the rows of D satisfy the
requirements for a GY-design.

Any row of D contains every point of the geometry 3
times, except for the 8 points in the corresponding row of G,
which will occur s-l times. Furthermore, since the rows of G
are the lines of EG(2,s) the two elements of every pair of distinct

points occur 5-1 times in the same row of D exactly once.

Therefore a0 = l and the row conditions are satisfied.

Let x, , y be the (i,j) entries in the matrices
13.7 1:3
2
X and Y respectively; let Cj’ j = 0,1,...,s-l, be the s X s -1
matrix whose i-th row is pL(xij)’ i = O,1,...,s-l, and similarly

let Lj’ j = 0,1,...,s-l, be the 52 X 52-1 matrix whose i-th

row is pL(y1j), i = O,1,...,sZ-l. Note that there are no repeated
points in any row or column of Lj’ j = 0,...,s-l, but it is not
a Latin Square since each row has only sZ-l points.

The matrix D can be written

29

 

0 l s-l
L0 L1 ° Ls-l
Observe that since X = YO,
r 1 1 T
T YO
TjY g 0
l 2
1,3 -l
Gj = I j = O,l,...,s-l
I
- 2
TJY 1C8 1 s -l
L. S' ..1

 

that is, the matrix C is the transpose of the j-th block of

1

3 columns of L with the first row missing, and that missing

0' Therefore

the columns of G are the lines of EG(2,s) written vertically

1

except for the line LO j and the 3 lines Li, i = 0,1,...,s-l,
’

first row is LO j’ the j-th line of the pencil Y
3

of the pencil X. Hence in each Gj there are s + 1 missing
lines.

The idea Of the construction is to use one of the matrices
Gj consisting of 82 - l = (s+l)(s-l) s-tuple columns to complete
each of the remaining s-l Gj's to a full geometry. We shall
show that this can be achieved by permuting the elements within
each row of the chosen Gj and keeping the rows constant which
will preserve the already established GY-design prOperty for the
rows.

The lines to be recovered by the chosen Gj are the 3

lines Of the pencil X each replicated s-l times plus the lines

of the pencil YO except LO j’ a total of

s(s-l) + 8-1 = 32 - 1 lines .

30

Let the lines of the pencil X be written vertically.

Since XT = Y if we apply the cyclic permutation 'r1 to the

0’
*
i-th line of the pencil X, each row of the resulting matrix X

will contain one point from each line of Y0; indeed

* s-l
x [L0, TL1,'°°,T LS'IJ

where Li, 1 = 0,1,...,s-l, is the i-th line x = ai of X

written vertically. Consequently each row of the s X s(s-l)

matrix

9: * s-2*
[x,TX ,...,T X]

will contain 8-1 points from each line of Y0.

We shall add to each row of the above matrix s-l points

chosen in such a way that all the lines except L0 j will be
9

completed. Notice that this must be done in a unique way since
each of the lines had exactly one point missing. We Obtain

*
this way the s X 82 - 1 matrix Gj which is characterized by the

fact that only the line L0 j of Y0 is not complete.
9

*
It is clear from the way G was constructed that the i-th

J

point of L will appear in the j+i-th (j+i taken mod 3) row

0,J

*
of G as well as in the s-2 preceding rows

J
j+i-l (mod s),...,j+i-(s-2)(mod s), but not in the following row
j+l *
G
J
0.J’
i = O,l,...,s-l, which is also the case with GJ. Thus the i-th
1+1 *
G and of G contain the same points, but in a

J J

different order.

j+i+1 (mod 3), i = 0,1,...,s-l. Therefore the matrix T is

such that its i-th row does not contain the i-th point of L

rows of T

. j+1 * .
Substituting ¢ G for Gj in D we obtain

which we claim is a GY-design.

We need only to verify the conditions regarding the columns.

Since every column of Li’ 1 = 0,1,...,s-l is a row of a
Latin Square, and since each column of Gi’ i = 0,1,...,s-l, and
G: is a line of EG(2,s) we see that a point occurs twice in a
column as many times as it appears in a line; since each point
belongs to 8+1 lines in the geometry and we have s-l replicated
geometries, we conclude that any given point occurs twice in
(8+1) (8-1) = $2 - l = r(b) columns.

Two distinct points will appear each twice in the same
column if they belong to the same line; since a pair of distinct

points determine a unique line and there are s-l replicated

*
geometries, Bl = s—l and we can conclude that Dj is a GY-design.

Example 2.2.3: For 3 4 we have

a = 16 b = 60 k = 20 r = 75 *1 = 281 12 = 93 .
From Example 2.3.2 we directly write

0 1 2 6 5 4 7 8 ll 10 9 13 14 15 12
4 5 6 9 10 11 8 l4 13 12 15 3 0 l 2
G3= 8 9 10 12 15 l4 l3 3 O l 2 4 7 6 5
12 13 14 3 O l 2 5 6 7 4 10 9 8 11

We have already obtained

32

o 1 2 3 o 4 8 12
4 5 6 7 1 5 9 13
x Y =
8 9 1o 11 o 2 6 1o 14
12 13 14 15 3 7 11 15
We directly obtain
0 7 10 13
x* _ 1 4 11 14
’ 2 5 15
3 6 12
o 7 10 13 1 4 11 14 2 5 a 15
* 1 4 11 14 2 5 8 15 3 6 9 12
Ga = 2 5 15 3 6 9 12 o 7 1o 13
3 6 12 o 7 1o 13 1 4 11 14

it

Since T4 is the identity, the rows of G3

12 9 6
O 13 10
4 1 14
8 5 2

correspond

to the rows of G3, so there is no need to reorder these rows.

*

The GY-design D3 would be

Theorem 2.2.3: There exist GY-designs with parameters

b=k=s(sz-l).

Proof: The other parameters are

2
r = (s -l)2 m = n = 8-1

= (82-1)(s-l) b(v) = 3(8‘1)

1:(1») ' ”(1:1

11 = 12 = as - 333 + 33 - l

3 2

a=B=s(s-1) (11:61-18 -28+1

0’0

V

8o

33

Let us permute cyclically the lines within the same parallel

*
pencil in TJ+IGJ; this can be accomplished by matrix multiplication
as follows:
68 I 1'
cs
' * ° **
TJ+IG '. = G,
1 CS J
L gS-la

 

 

where there are s-l matrices £3 and all the off diagonal
matrices are zero.

We claim that the s(sZ-l) X s(sZ-l) square matrix

' **“
G0 G1 . . s-l
L0 L1 . LS_1
**
G1 (32 , . GO
D** ’ L
- L1 L2 ... 0
**
Gs-Z Gs-l °° Gs-3
LFS'Z Ls-l "° Ls-3

 

 

is a GY-design.

Using the same argument as in the previous theorem we
will prove that the row conditions for GY-designs are satisfied.

**

Any given column of D is made out of s-l rows of
the Latin Square L, corresponding to the matrices Li’ plus s-l
different parallel lines, cooresponding to either the matrices

**

Gi or to the matrices G1 as the case may be. Therefore a

point occurs in each column either s+l or 5 times; it will

occur 8 times if and only if it belongs to one of the s-l

34

parallel lines. Since these parallel lines contain s(s-l) points,

the number of points repeated in the column s = n+1 times is

s(s-l) = 32 - s = k(v)' Furthermore, the missing lines from each
** **

column of D are the columns of the missing Gj’ (G ), matrix

J

in each block of 32-1 columns; these matrices are

**
Go,ooo,G

Gs-l’ s-2

and they constitute, as we have seen in the previous theorem, the
full geometry EG(2,s) replicated 5-1 times. Therefore each
member of a pair of points will appear s-l times in the same column
if and only if both points belong to the line missing from that
column, and 60 = 8-1. This concludes the proof that D** is a
GY-design.

Example 2.2.4: For 3 = 3 we have

v = 9, b = k = 24, r = 64, 11 = 12 = 170, a = B = 6, a0 = 80 2,
01 = 81 = 10
0 l 2 O 3 6 O 5 7 O 4 8
X=3 YO=147 Y1= 138 Y2=156
6 8 2 5 8 2 4 6 2 3 7
O 3 6 1 4 7 2 S 8
1 4 7 2 5 8 O 3 6
2 S 8 O 3 6 1 4 7
5 7 0 3 8 l 4 6 2
L = 3 8 l 4 6 2 5 7 0
4 6 2 5 7 O 3 8 1
8 0 4 6 1 5 7 2 3
6 l S 7 2 3 8 O 4
7 2 3 8 0 4 6 1 5

TC

0

*‘k

”1

TC

0

80461537
72380461

61572304

35

G

1

20345678
53867120

86120534

23704865
=15623708

04815632

37248056
=56l37280

48056123

**

36

34

37

We finish this section exhibiting another GY-design D*
with parameters v 3 9, b = k = 24 which is non-isomorphic to
**
D with the same parameters.
Definition 2.1: Two GY-designs with the same parameters are said
to be isomorphic if one can be obtained from the other by renaming
the varieties, reordering the rows or reordering the columns.

The GY-design D which follows, was constructed using

*9

the unique geometry EG(2,3) and trial and error.

1 l 2 2 3 3 4 4 4 5 5 7 6 6 6 7 7 9 8 8 8 9 9 5
4 4 5 5 6 6 8 8 1 2 2 2 3 3 3 7 7 7 1 8 l 9 9 9
7 7 8 8 9 9 l l l 6 2 2 3 3 3 4 4 4 5 5 5 6 6 2
l 1 5 5 9 9 2 2 2 3 3 3 4 4 4 6 6 6 7 7 7 8 8 8
2 2 6 6 7 7 l 1 l 8 3 3 9 9 9 5 5 5 8 3 8 4 4 4
3 3 4 4 8 8 2 2 2 l 1 6 5 5 5 6 6 l 7 7 9 9 9 7
l l 4 4 7 7 2 2 8 3 3 3 5 5 5 9 6 6 9 9 6 2 8 8
2 2 5 5 8 8 3 3 3 l l 1 4 4 4 9 9 9 6 6 7 7 7 6
3 3 6 6 9 9 8 8 8 2 2 2 4 4 l l l 4 7 7 7 5 5 5
8 8 1 1 6 6 9 9 9 7 7 7 5 5 4 3 4 3 3 5 4 2 2 2
9 9 2 Z 4 4 8 8 8 5 5 5 6 6 6 7 7 7 3 3 3 l l 1
3 3 7 7 5 5 6 6 6 9 9 9 2 2 2 8 8 8 l l l 4 4 4
D* =
4 4 3 3 2 2 5 5 5 7 7 8 9 9 7 1 l 6 6 l 6 8 8 9
6 6 7 7 5 5 9 9 9 4 4 4 8 8 8 3 3 3 2 2 2 l l l
8 8 9 9 1 1 7 7 7 6 6 6 2 2 2 5 5 3 4 4 3 5 3 4
2 2 6 6 l 1 3 3 3 5 5 5 7 7 7 8 8 8 9 4 9 4 4 9
8 8 3 3 7 7 4 4 4 9 9 9 2 2 2 5 5 5 1 l l 6 6 6
5 5 9 9 4 4 7 7 7 6 6 6 l l l 8 8 8 3 3 3 2 2 2
5 5 8 8 2 2 7 7 7 4 4 4 9 9 9 l l l 6 6 6 3 3 3
6 6 9 9 3 3 5 5 5 7 7 7 8 8 8 4 4 4 2 2 2 l l 1
7 7 1 l 4 4 6 6 3 8 8 8 3 3 6 2 2 2 9 9 9 5 5 5
9 9 7 7 2 2 5 5 5 8 8 8 l 1 3 3 3 l 4 4 4 6 6 6
5 5 3 3 l 1 6 6 6 4 4 9 8 8 8 9 9 9 2 2 2 7 7 7
6 6 4 4 8 8 9 9 9 l l l 7 7 7 2 2 2 5 5 5 3 3 3

38

*9:
That D and D* are not isomorphic is evident since
**
D has several columns identical, while D has not two identical

columns.

2.3 A_class gf'non DeoEtimum Qi-designs

As stated in Chapter I, J. Kiefer proved in his 1958 paper
that GY-designs are D-optimum if either b(v) = 0 or k - 0,
We will show now that if the divisibility condition is not
satisfied the GY-design may not be D-Optimum.
Theorem 2.3.1: There exists GY-designs with v = 4, b = k = 6t
for any odd integer t.

Proof: The other parameters are

 

2
= 9t b - k = 2 - = 3t
1” (v) (v) 1r(b) r(k)
= = 3t-l _ _ 27t3 - t
m n 2 "1 " >2 2
a = B = 2t a0 = 80 ' t 01 = 81 ‘ t .

Let the set of varieties be V {A,1,2,3} and let g be a

permutation on Vb defined as follows:

g(a1,...,ab) = (ab,a1,...,ab_1), V(al,...,ab) E Vb.

Let T be a transformation on V which leaves exactly one
variety fixed; by renaming the varieties if necessary we may

assume without loss of generality that

T(A)=A,T(1)=2.T(2)=3»T(3)=1°

39

Finally let p E‘Vb be

m m+1 m+1 m
p = (A ... A, 1 ... l, 2 ... 2, 3 ... 3)

and let D be a k X b matrix whose first row is p and such
that every row and column is the transformed of the preceding one
by g o T.

Since T leaves A fixed, A will occur m times in
each row and column of D; since T3 is the identity every variety
other than A will appear m+1 times in two out of every three
consecutive rows or columns.

Let d i = l,2,...,k, j = 1,2,...,b be the (i,j)

ij’
entry of the matrix D. We claim that if we make di,3t+i = A,
*

i = 1,2,...,3t, the resulting matrix D is a GY-design.

Variety A appears ‘m+l times in each of the first
3t = r(k) rows; any other variety x # A appears m+1 times
in one out of every three consecutive rows for the first 3t
rows, and in two out of every three consecutive rows for the last
3t rows that is in a total of 2!;-+ §£2 = 3t = r rows.

’ 3 3 (k)
Moreover, the pair of distinct varieties A,x (x #.A) appear
m+1 times each in the same row t = a1 times.

A pair of distinct varieties other than A can occur
m+1 times each in the same row only in the last 3t rows and in
exactly one out of every three consecutive rows, that is in
t = (171 rows.

The same arguments applied to the columns would allow us

*
to conclude that D is a GY-design.

Example 2.3.1:

For

40

t = 3, we have

9 r 81 3 )t 1 XZ
= k - 2
(v) (v) ’ 0’
1 1 1 1 2 2

41

1 A A A A 2 2 2 2 2 A 3 3 3 3 l 1 1
2 2 A A A A 3 3 3 3 3 A l l l l 2 2
3 3 3 A A A A 1 l 1 1 1 A 2 2 2 2 3
1 1 l l A A A A 2 2 2 2 2 A 3 3 3 3
l 2 2 2 2 A A A A 3 3 3 3 3 3 A l l

*
We will show now that the GY-design D is not D-optimum,

by comparing it with the non-symmetrical design D.
The hypothesis to be tested is that variety has no effect

on yield, that is

‘YA='Y1=‘Y2=‘Y3.

In the two-way heterogeneity setting where we have v

varieties and a k X b array of plots, the covariance matrix is

42

given by (see for instance, Kiefer, 1958)

1(1) 1(2) r r
..-. .. _l.l_ _ .ii. ...1__1
C11 51111 b k + kb

where 611 is the Kronecker delta, ri is the number of replica-

tions of the i-th variety and

; n<1) n(1)
=1 11 11

(2) n<2)
1 it jL

IIMU‘
:1

(q)

with n equal to the number of occurrences of the i-th variety
in the L-th row 01 = l) or the L-th column (q = 2).
It is a straightforward but long computation to obtain

in the case of D

 

 

 

 

c* = 27t2 - 2 c* = 2 - 27t2
ii 4 ij 12
for 1 16 j, 1,1 =A,l,2,3.
For the design D one would Obtain
c = 27t2 - 6t - l c = _ 27:2 — 6t - 1
AA 4 Ai 12
2 2
c =2431; +18t-l7 c ____81t ~18t+7
ii 36 ij 36

i 7‘ J, i.J = 1,2,3

*
and for the corresponding determinants A and A,

* [27t2- ]3
A=——3—'—

A = L271:2 + 3t - 212127t2 - 6t - 11
3 " o
3

43

3 2
* 108t - - 12 +
The difference A - A = 45t3 t 4 is
3
* .
positive for any positive t, therefore D is not D-optimum.

Note however that for the eigenvalues we still have

 

2 2
- - - *
21£3———Z-> 27t 3 6t 1 , that is the smallest eigenvalue of D

is larger than the smallest eigenvalue of D, as it should be.

Example 2.3.2: For t = l

A11223 A11A23
1112233 1A22A3
1211331 12A33A

D=223All D*=223A11
2331A2 2331112
33112». 33112A

*
A - A = -—'> 0 .

Final Remark: Other sets of parameters satisfying the necessary
conditions for GY-designs were obtained but they did not lead to
suggestive combinatorial configurations. Further research is

now in progress to construct other classes of GY-designs using

different combinatorial structures.

CHAPTER III

SUM COMPOSITION OF LATIN SQUARES

3.1 Introduction and Definitions

The different methods of composition are among the most
powerful techniques of construction of combinatorial systems.
Those methods permit the construction of a new combinatorial
system out of known ones.

However the methods known so far are of the product type,
in the sense that the parameters of the new system are some sort
of product of the parameters of the initial systems; for instance
the existence of orthogonal arrays (xiv:,qi,vi,t), i = l,2,...,r,
implies the existence of the orthogonal array (th,q,vi,t), where
y = y1.y2...yr, v = v1-v2-oovr and q = min(q1,q2,...,qr).

In this chapter we will be dealing with a new sum type
method of composition of Latin Squares due to Hedayat and Seiden
(1969).

Definition 3.1.1: Two Latin Squares of order n are orthogonal

 

if upon superimposition each of the 112 pairs of distinct varieties
occur exactly once.

A system of two orthogonal Latin Squares or order n will
be referred to as a O(n,2) set. If A and B are orthogonal
Latin Squares we will write A 4.8.

Definition 3.1.2: t Latin Squares of order n are mutually

orthogonal if any two of them are orthogonal.
44

45

A system of t mutually orthogonal Latin Squares of order
n will be referred to as a 0(n,t) set.
Definition 3.1.3: A Latin Square L of order n is orthogonally
mateless if for any other Latin Square L1 of order n the pair
(L,L1) is not a O(n,2) set.
Definition 3.1.4: A transversal of a Latin Square of order n
is a collection of n cells whose entries exhaust the set of
varieties and such that no two cells belong to the same row or
to the same column.

Two transversals are parallel if they have no cell in
common.
Definition 3.1.5: A common transversal for a 0(n,t) set is a
collection of n cells which is a transversal for each of the

t Latin Squares in the set.

Example 3.1.1:

 

 

1 2
L a:
1 2 1
r -w
(1) 2 3 4,7 (1) 2 3 3
g 1 4 (3) _3__ 4 1 (2)
L2 "" 3 (4) 1 2 L3 = 4 (3) _2_ 1
L“ 3 (2) 1 2 1 <4) 3 J
r71 2 3 41 F1 2 3 47
4 3 2 1 3 4 1
L4 = 2 1 4 3 L5 = 4 1 2
L3 4 1 2 J I.“ 1 2 3 J

 

 

 

 

 

L1 is the only Latin Square of order 2; it has no transversals

at all.

46

L2,L3,L4 form a 0(4,3) set; L is orthogonally mateless,

5

the underlined and paranthesized cells in L form two common

2 ’13

parallel transversals of the 0(4,2) set formed by L ,L ; the

l 2

0(4,3) set formed by L has no common transversals.

1’12 ’13

3.2 The Method of Sum Composition

 

This method was first introduced by Hedayat and Seiden
(1969).

Let L1,L2 be two Latin Squares of orders T11 and 112

on disjoint sets of varieties {a1,a2,...,a } and

n
l
{b1,b2,...,bn }, n1 2 n2, and let L1 have at least n2 parallel
2

transversals.

Select arbitrarily n parallel transversals from L

2 l

and name them l,2,...,n2; in a n1 + 112 square fill the n1 X 111

upper left corner with L1 and the n2 X 112 lower right corner

with L . Fill the cells (i,n + k), k = l,2,...,n

2 , with that

l 2

element of transversal k which appears in row i, i = l,2,...,n1;
similarly fill the cells (n1 + k,j), k = l,2,...,n2, with that

element of transversal k which appears in column j, j = l,2,...,n1.

Finally substitute b for the n

k elements of transversal k,

l

k = l,2,...,n2.
The resulting n1 + 112 square matrix L is easily seen

to be a Latin Square.

The procedure just described of filling the first 111

entries of column (row) n1 + k is called horizontal (vertical)

projection of transversal k on column (row) 111 + k.

47

Remark: It is by no means required that the ordering of transversals
be the same for both horizontal and vertical projections. Therefore,

if N is the total number of parallel transversals of L we can

1
construct by this method

N 2
(n2) 61,!)

different Latin Squares of order n + n .

 

l 2
Example 3 .2 .1 :

0 l 2 3 4 5 6
2 3 4 5 6 0 l A B C D
4 5 6 0 l 2 3 B C D A

L1 = 6 0 l 2 3 4 5 L2 = C D A B
l 2 3 4 5 6 0 D A B C
3 4 5 6 0 1 2
5 6 0 l 2 3 4

In L1 the cells (i,j) such that i + j E k(mod 7)
form a transversal for each value of k, k = 0,1,...,6. Let us
use those corresponding to k = 0,2,4,6, in that order, for
horizontal projection, in reverse order, (6,4,2,0), for vertical
projection and in alternate order (0,4,2,6) for substitution.

The result is the Latin Square L of order 11.

J>
CD

A l C 3 B 5 D 0 2 4 6
2 C 4 B 6 D A 1 3 5 0
C 5 B 0 D A 3 2 4 6 l
6 B 1 D A 4 C 3 5 O 2
B 2 D A 5 C O 4 6 l 3
L = 3 D A 6 C l B 5 0 2 4
D A 0 C 2 B 4 6 l 3 5
5 4 3 2 l O 6 A B C D
l 0 6 5 4 3 2 B C D A
4 3 2 l 0 6 5 C D A B
0 6 5 4 3 2 l D A B C
3.3 Sum Composition of O(n,2) Sets

 

 

Under certain conditions it is possible to use the method
of sum composition to obtain O(n,2) sets from known O(n1,2)

and O(n2,2) sets, n = 111 + n2.

Let {A1,A2} be a O(n1,2) set on the set of varieties

A = {a1,a2,...,an } with at least 2n2
l

and {B1,B2} a O(n2,2) set on the set of varieties

common parallel transversals,

B ={b1,b2,ooo,bn2}, A n B = $9
Select 2n2 common parallel transversals from the first

set and use half of them to compose A and B to obtain a

l 1
Latin Square L1 of order 111 +n2 = n; use the remainder n2
transversals to compose A2 and 32 to obtain a Latin Square

L2 of order n.

It is obvious fnam the construction that upon superimposi-

tion of L1 on L2 the elements of A X B and B X A will
appear along the 2n2 transversals in the 1:11 X 111 upper left
corner; the elements of B X B will appear in the n2 X n2

lower right corner, since B1 and B2 are orthogonal. However

49

some of the elements of A X A will be missing, but by prOperly

choosing the 2n2 transversals and the order of projection we

may achieve that the pairs (ai,ak) lost by substituting elements

of B in transversals of A1 and A2 be recovered on projection.

Although we do not have a unified rule to achieve this we
do have procedures which are applicable in several cases.

Example 3.3.1:

Let r11 = pa be a power of a prime number p, and number

the rows and columns of a n X n square matrix 0,1,2,...,n -l;

1 1 l
for a fixed x E GF(nl), x # 0, fill cell (i,j) of the matrix

with ix + j E GF(nl); the resulting square is a Latin Square

A(x). Furthermore the n1 - 1 Latin Squares A(x), x E GF(nl),

x ¥ 0, constitute a 0(n1,n1-l) set; the cells (i,j) such that

i + j = k, k 6 GF(nl) constitute a set of 111 common parallel

transversals of the 0(n,n1-l) set.

Now, let GF(7) be represented as the residue classes

modulo 7, and let A =.A(3), A2 =4A(4) and similarly, for GF(3)

1

let B1 = B(1), B2 = 8(2). To compose A1 and B1 use the

transversals given by k = 0,5,4 in that order for both projec-

tions and substitution and obtain L1; to compose A2 and B2

use the transversals given by k = 1,2,6 and obtain L2;
(L1,L2) is a 0(10,2).

50

0 1 2 3 4 5 6
4 5 6 0 l 2 3

0 l 2 3 4 5 6

3 4 5 6 0 l 2
6 0 l 2 3 4 5

A1 = 2 3 4 5 6 0 1

l 2 3 4 5 6 0

A2 = 5 6 0 1 2 3 4

2 3 4 5 6 0 l

5 6 0 l 2 3 4

2 3 4 5

6 0 l

l 2 3 4 5 6 0

2

3 4 5 6 0 1

4 5 6 0 l 2 3

A
C

.A B
CA

BC

A 1 2 3 C B 6 0 5 4

3 4 5 C B A l 2 0 6

6OCBBAS421

ZCBSA01643

(330112341
L1=B2A456C310

5

6

4 A 6 0 l C B 5 3 2

0 5 3 1

6 4 2 A B C

l 6 4 2 0 5 3 B C A

6 4 2 0 C A B

3 l

5

6

2

0 A B 3 4 5 C l

A B 6 0 1 C 3 4 5 2
B 2 3 4 C 6 A 0 l

5

5 6 0 C 2 A B 3 4 l

2 3 C 5 A B

l 6 0 4

6 C 1 A B 4 5 2 3 0
C 4 A B 0 l 2 5 6 3

L2 =

4 l 5 2 6 3 0 A B C
l 5 2 6 3 0 4 C A B

3 0 4 l 5 2 6 B C A

Hedayat and Seiden (1969) have proved the following results.

51

Theorem 3.3.1: Let 111 = pa 2 7, where p is any odd prime

number, a a positive integer, 111 i 13. Then there exists an

O(n,2) set which can be constructed by composition of two
n -1

 

= —L_ =
0(n1,2) and 0(n2,2) sets for 112 2 and n n1 + n2.
meoreL3.3.2: Let r11 = 20’ 2 8 for any positive integer (1.
Then there exists an O(n,2) set which can be constructed by
n
composition of two 0(n1,2) and 0(n2,2) sets for 112 = 21’ and

n = n11+ n2.
The same authors have also proved in 1970
Theorem 3.3.3: If a prime number p has one of the following
forms:
I 3m +'1
II 8m-+ 1

III 8m + 3

IV 24m +'ll
V 60m +-23
VI 60m +’47

then using the method of Sum composition it is possible to con-
struct a pair of orthogonal Latin Squares of order pa + 3. The
method of construction depends on the form of p, but does not
depend on its specific value.

Theorem 3.3.4: If p is a prime of the form 8m-+ l or 8m'+ 3,
m # 0, then one can compose an 0(4,2) with an O(pa,2) based on

Galois field, to obtain an o(p°' + 4,2).

52

3.4 Construction of O(n,2) Sets by the Method of Sum Composition

In what follows we assume the following: n1 = pa, a power

of a prime p; the 0(n1,2) set is based in GF(pa) and formed,

with the notation introduced in Example 3.3.1, by A = A(x),

1
A2 = A(y), x,y E GF(nl), x f y, {x,y} fl {0,1} = Q5. We will use
common parallel transversals given by cells (i,j) such that

i +~j = k, k E GF(nl) and named by k. We further call

S = {31,sz,...,sn2} and T = {t1,t2,...,tn2} the disjoint sets
of 112 transversals each used to obtain L and L .

1 2
We have seen that the only difficulty of the method of
sum composition is to make it sure that every element of A X A
on L

appears on superimposition of L the missing pairs are

1 2‘

the 2n2n1 pairs of the form
(m+1.w+1),i+jesu1

which correSpond to the entries in the 2n2 transversals used
in the composition.
If transversal s of A(x) is projected horizontally

on the same column as transversal t of A(y), on superimposition

we will obtain along that column the 111 pairs
(ax+b,ay+c) ,a+b=s,a+c=t

If those pairs are to be some of the lost ones we must have:

ix + j ax + b a + b s E S a + c = t E T

iy +rj ay + c i + j k E S U T

53

or i(x-l) +-k = a(x-l) + s

i(y-l) +'k = a(y-l) + t .

Eliminating i we obtain

k(y-X) 8(y-1) - t(x-1)

or k(y-x) s(y-x) + (s-t)(x-l) .
x-l .
Making ;:;'= D we finally get

k=(1+p,)s-p.t

that is, by projecting horizontally transversal s of A(x) on
the same column as transversal t of A(y) we obtain on super-

impoSition the n1 pairs
(ix +'j, iy +>j) i + j = (l + ”)3 - At

Similarly, if transversals s and t of A(x), A(y)
are projected veritcally on the same row, we will obtain along

that row the n1 pairs
(ax+b,cy+b) a+b=s c+b=t.

If those pairs are to be some of the lost ones we must have

ix + j = ax + b a + b s E S c + b = t E T

iy+j=cx+b i+j=kESUT
or i(x-l) +’k = a(x-l) + s
i(y-l) +*k = C(y-l) + t .

Eliminating i we obtain

54
k(y-X) = (x-1)(y-1)(a-c) + s(y-l) - t(x-1)
Since a-c = s-t, we get
k(y-X) = 8(y-X) + (s-t)(x-1)y
and finally
k = (1 + yu)s - yut

that is, by projecting vertically transversal s of A(x) on
the same row as transversal t of A(y) we obtain on super-

imposition the 111 pairs
(ix +‘J. 1? + J) i + J = (1 + yu)s - yut
From now on we will use the following functions on S X T

Kh(8,t) = (1 "I' ”)8 - pt

Kv(s,t) = (l + yA)s - ypt .

By properly choosing x,y and the pattern of pairing
transversals from S and T we may be able to recover all the
lost pairs and thus obtain a 0(n,2) set with n = p01 + n2.

Hedayat and Seiden assume in all their work, xy = 1.

Theorem 3.4.1: If p is a prime of the form p = 4m +-l, m > 1, then

 

it is possible to compose O(pa,2) based on GF(pa) with
0(4,2) to obtain a O(pa + 4,2).

Proof: Consider the pattern

1+1 - Kh(si’ti) i 1,2,3 3 Kh(s4’t4)

ti-1 = Kv(si’ti) 1

2,3,4 1:4 = Kv(s1,t1)

55

that is

82 = (l + “>81 - ptl t4 = (1 + yu)s1 - ypt1
s3 = (1 + we, - u-tz c1 = (1 + ms, - Yutz
$4 = (1 + 11-)83 - M3 t2 = (1 + yu)s3 - 711113
S1 = (l + “)84 - pt4 t3 = (l + YH)34 - yut4 .

Solving this linear system in terms of s1 and t1, we

obtain as a solution

32 = (l + ”)51 - utl
1 l
83 = (1 + p.)[1 + p, - ;(1 + yu)]sl - [u(l + p.) - $11.0. + YIJ') + 1]]t1
2
1
s4 = [A(l + yp) +11] ix; 81 - ¥&;'t

2=[(1+yp)(11+p,) L381 -[p,(l+yp,)+1]l-t1

t3 = [(1 + 71071..“ [II-(1 + W) + 11- 341(1 + 5310181 -
2
r [(1 + Yum» {41: - yzuzltl
1:4 = (1 + 3'qu1 - yutl -

The compatibility conditions are

2
fin— [u(1+yn) + 1] = (1+p.) [1m - $(1+yu)] - M17711) [Ii-(1+1). + yuz) ' WI

2
1+“ = -(1*u)Lu(1+u) - -L1+u + 7112]] + w 3f—U17Vu) Y]
W = (1+Vu)(1+v-)L1+u - jams] - yu<1+yu>1fi13<1mm2> - w]
2
- 11115322.). .. -(l+yu)[u(1+u) - "(11'1143’11-271 + y2 $111.41. .7] -

These compatibility conditions reduce to

 

 

56

3 2 2 2 3 3
(l'i'p) -(1+u)yp+(l+u)yu ‘YTJ. =0.

Dividing by y3p3 and making lEfi-= A we obtain as compatibility

condition
13 - 12 +'x-l = 0 or (A-l)(),2 + l) = 0 .

2
I = 1 would give 33 = 81’ therefore we must have 1 +*l = 0,
that is -1 has to be a quadratic residue in GF(pa) which is
possible only if p is of the form p = 4m +-l.

Calling i2 = -1, the compatibility condition becomes

y(l : i(l-x)) = 1 .

 

which is satisfied by the pair x = 2, y = 1 . Using 8 = 0,

t1 = l we obtain as solution of the system

s =’3 ; i t = -3 $.41
2 5 2 5
=4+2i t =-1~T21
S3 5 3
= -l i.3i t _ 1 1.21
S4 5 4’ 5

We must investigate now under what condition those solutions are

all different. One can easily see that

81 = 32 if 10 E O(mod p), that is p = 2,5
31 3 83 if 20 E O(mod p), that is p = 2,5
31 = 34 if 10 a O(mod p), that is p = 2,5
81 = t2 if 25 E O(mod p), that is p = 5

s1 = :3 if 5 O(mod p), that is p = 5

III

s = t4 if 5 O(mod p), that is p = 5

57

= 83 if 10 E 0(mod p), that is p = 2,5
84 if 20 a 0(mod p), that is p = 2.5
82 3 t1 if 5 E 0(mod p), that is p = 5
if 45 E 0(mod p), that is p = 3,5
32 = t3 if 25 a 0(mod p), that is p = 5
if 5 E 0(mod p), that is p = 5

s3 = 54 if 50 E 0(mod p), that is p = 2,5

83 = t1 if 5 0(mod p), that is p = 5
33 = t if 85 E 0(mod p), that is p = 5,17
83 = t3 if 5 E 0(mod p), that is p = 5
s3 = t4 if 25 E 0(mod p), that is p = 5
s4 = t1 if 45 s 0(mod p), that is p = 3,5
84 = t2 if 5 E 0(mod p), that is p = 5
s4 = t3 if 25 E 0(mod p), that is p = 5
t4 if 5 E 0(mod p), that is p = 5

t1 = t2 if 80 E 0(mod p), that is p = 2,5

H‘
H

II

('1'

3 if 40 a 0(mod p), that is p = 2,5

t1 = t4 if 20 a 0(mod p), that is p = 2,5

t2 = t3 if 40 a 0(mod p), that is p = 2,5
t2 = t4 if 20 E 0(mod p), that is p = 2,5
t3 = t4 if 20 E 0(mod p), that is p = 2,5 .

Therefore the solutions are all different when p = 4m+l, m > 1,
provided p i 17.

If p = 17, the pair x = 5, y = 9 satisfies the
compatibility equation; using again 3 = 0, t = l we obtain

1 l

the solutions

58

32 = 16 t2 = 12
83: 3 t3: 2
s4 = 4 t4 = 3

which are all different in GF(17).
The limitation m > 1 is due, of course, to the fact
that the method requires at least 8 parallel transversals in
order to compose a 0(4,2) set.
Note that xy = l is incompatible with y(l i i(l-x)) = l;
indeed, the only common solution is x = y = 1.
Theorem 3.4.2: If p E l,2,4(mod 7), p 2 11 it is possible to
compose O(pa,2) based on GF(pa) with 0(4,2) to obtain a
0(p“ + 4,2).

Proof: Consider the pattern

81 = Kh(32’t2) t1 = Kv(52’t2)
s2 = KhIS3't3) t2 = Kv(s3't3)
s3 = Kh(sa,t4) t3 = Kv(sl,t4)
s4 = Kh(sl,t1) t4 = Kv(sa.t1)

Solving this linear system in terms of s and t2, we

obtain as solutions:

S]. = (1 + ”)82 - ptz

s3 = [(1'111)L(1+u)2-u(1+w)]-HL(HTML(1+p)2-u(1+yu)] - yu(1+'yu)]]sz
2 2 2 2
- L<1+u)[u(1+u)-yu 1 - uL(1+Vu)Lu(1+u)-yu ] - y u lltz
84 = [(1+u)2 - u<1+7u)132 - Lu<1+u) - yu21t2

59

F?
..a
II

(“VI-1752 - yutz

H
II

2
3 L(1+7u)(1+u)-YHL(1+YH)L(1+H) -u(1+Vu)] ' yu(1+yu)]]82
2 2 2
- L<1+Vu)u - yuL(1+7u)(u(1+u) - yu ) - y u ]]t2
t4 = [annulmz - some] - yeah/ms;
2 2 2
- [(1+yu)[u(1+u) - w '_I - y 111112 -
The compatibility conditions are
1 = (“u-)L(1'I'I1)L(1‘*11-)2 -u- am) 1-61 (1471») 1 an») 2 -a<1+yu>]-ys<1+wm
- HL (1476) (HT-l) -1m[ (1m) 1 (1+6) 2 ‘11-(1'1711) ]-yu(1+yu.)]]
2 2 2 2
0 = -(1+u)L(1+u)Lu(1"u)-yu l-uL(1+yu)Lu(1+u)-yu ]-y u- I]
2 2 2
+ uLu<1+yu)-yu[(1+yu)(u(1+u)-yu )-y u I]
o = <1+ye>1<1+m1<1+m2m<1+w>T-swm)[<1+n>2-n(1m>1-ys<1+vu)11
- yuL(1+yu)(1+u)-yuL(1+Vu)L(1+u)2-u(1+yu)l-yu(1+yu)ll
2 2 2 2
1 = -(1+yu)L(1+u)Lu(1+u)-yu ]-uL(1+Vu)Lu(1+u)-yu I-y u 11
2 2 2
+ YuLu<1fiu)-yui (lflu)(u(1+u)-yu ) - y u- 1]

which reduce to

2 2 2
1 - u(y-1) - u (y-l) (u y + uy-l) = 0 -
Making x-l = u, y -l = v we get

v4(u-l)(u2 + 1) +v3u(3u2 - 3u +-4) - v2u2(u2 - 3u + 6) -

- v u3(u-4) - u4 = O .

For u

= l

60

the equation becomes

QVB - 4v2 +'3v - 1 = 0

which can be factorized

However

(VTJE)(2V2-v+l)=0.

u:

look for the roots of 2v2

quadratic residue, and this is so if p

To solve that equation it is necessary that

Calling 12

3.7,

u:

1, v = % gives

t2 - t4, so we have to

- vi+ l = 0.

1 gives

X

-7 be a

1,2,4(mod 7).

=2,y=

5 i.i

4

= 0 we obtain as solution of the system

 

 

=1li

4
=3-71

2
=7-731

8
is easily seen
= 32 if 121
= 83 if 32
= 34 if 32
= t1 if 8
= t2 if 8
= t3 if 56
= t4 if 112

that

0(mod
0(mod
0(mod
0(mod
0(mod
0(mod

0(mod

p).
p).
p).
p).
p).
p).

p).

that

that

that

that

that

that

that

 

 

1:1
2
2
9-751
8
is p
is p
is p
is p
is p
is p
is p

11

2,7

2,7

32 = 83 if
32 = 84 if
82 = t1 if
32 = t4 if
83 = 34 if
83 = t1 if
83 = t2 if
53 = t3 if
33 = t4 if
34 = t1 if
34 = t2 if
84 = t3 if
34 = t4 if
t1 = t2 if
t1 = t3 if
t1 = t4 if
122 = (:3 if
t2 = t4 if
t3 = t4 if

Therefore the solutions are all different

176

32

16

16
16
112
144
32
8
16
32
2
256

224

61

0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod
0(mod

0(mod

p).
p).
p).
p).
p).
p).
p).
p).
p).
p).
p).
p).
p).
p).
p).
p).
p).
p).

p).

P 5 1,2,4(mod 7). provided p E 11.

For
31 = 8
t1 = 5

which are all different in GF(ll).

that

that

that

that

that

that

that

that

that

that

that

that

that

that

that

that

that

that

that

p = 11 we obtain, using y =

is

is

is

is

is

is

is

is

is

is

is

is

is

is

is

is

is

is

is

 

+
4

2,7

2,3

2,7 .

when

62

n
Theorem 3.4.3: If n2#6 is even, then for any prime number p 2'—2

2
it is always possible to compare 0(pa,2) based on GF(pa) with
0(n2,2) to Obtain a O(pa + n2,2) set.

Proof: Consider the pattern

n
I

81 = Kh(82’t2) 1 ’ Kv(52’t2)

Solving this system in terms of s the compatibility

13 t1,

conditions are

1 = (1 + u)2 - u(1 + ya)

0 = -u(1 + u) + yuz

0 = (1 +u)(1 +111) - yu(1 +yu)
1 = -u(1 + yu) + yzuz

which reduce to

Yu=1+uw

+ .
1 s1 1 we Obtain

Taking t
32 = 31 - u t2 = 31 - ya = 32 - 1

that is, t2,32 are also consecutive numbers. By properly choosing

y, which uniquely determines x, since the equation of compatability

is of first degree in x, we may achieve that t2 = t1 + l; the
2
choice is A = -3 which provides = 3' and x = %u The sets

3 and T are therefore

63

S = {31, 31 + 3}
T = {81 + 1, 51 + 2} .
n2
By starting with s1 = 0 and repeating the above process '5-

times, we obtain the sets of transversals

- 4, 2n

(D
II

[0,3; 4,7;...; 2n2 2 - 1}

1-3
II

{1,2; 5,6;000; 2112 ‘3, 2112 '2} c

We could also have considered the pattern

81 = Kh(82’t2) t1 = Kv(s1’t2)
s2 = Kh(sl’tl) t2 = Kv(sz,t1) .
Taking sl,t1 as independent unknowns, the compatibility

condition reduces to

Yu(1 +‘u) = l .

Using again t1 = 31 + l we obtain
= — = - + = ..
32 31 u t2 s1 (1 H) 32 1

that is, t2,32 are also consecutive numbers; t2 = t1 + 1 would
imply as before u = -3, y = %3 x = - i“ and we will get

S = {51, 31 + 3}

T = {31 +-l, 51 + 2} .

n2

Again by starting with $1 = 0 and repeating the process 2—

times we Obtain

in
II

{0,3; 4,7;...; 2n2 - 4, 2n2 - l}

I—l
I

— {1,2; 5,6;...; 2n2 - 3, 2n2 - 2}

however this time we have to reverse the order of the set T
before projecting vertically.

Note that although all the computations have been
carried out in GF(p), that is mod p, the theorem can be
extended to pa since any GF(pa) has a subfield isomorphic

to GF(p); this is also the reason to impose the limitation

n
p 2 a; on p rather than on pa.

Note that if xy = l the compatibility conditions are
not satisfied.

Unlike in previous theorems, where for each value of x
we could obtain at least two values of y satisfying the com-
patibility conditions, this method cannot be extended to the con-
struction of O(n,3) sets because the value of y uniquely

determines x.

3.5 Composition of O(pa,2) and O(3,2) Sets

The smallest non-trivial n for which a 0(n,2) set
exists is n = 3; there are 24 possible patterns to compose a
O(n1,2) and a O(3,2) set. We assume, without loss of generality,
that the pairs (s,t) of transversals horizontally projected on

the same column are (Si,ti), i = 1,2,3. The sets S and T are

now S = {31,82,33}, T = {t1,t2,t3}.

65

Theorem 3.5.1: If a pattern for composition of a O(pd,2) and a
O(3,2) set is such that horizontal projection recovers transversals
from both sets S and T, then xy = 1.

23292: For any pattern, of the six equations which determine the
pattern, three will involve the function Rb and the other three
equations will involve the function Kv' Adding the six equations

we will always obtain, no matter what the pattern is,

13si + Eti = (1 +11 + Hymzsi - «thwarti

or (Esi - Eti)(l + p +’YH) = 0 .

If horizontal projection recovers transversals from both
S and T adding the three equations involving Kh we will
obtain in the l.h.s. the sum of either two 3's and one t, or
one s and two t's; in the r.h.s. we will obtain
251 - A(Zti - 281). Therefore if zti - 231 = 0 we will have
31 = tj for some i,j. We must then have 1 + A + yu = 0; but
1 +'p + yp = xy - 1, thus the result.

This theorem applies to 12 of the 24 possible patterns

to compose O(pa,2) and O(3,2) sets; they have been fully

investigated by Hedayat and Seiden (1970).

BIBLIOGRAPHY

BIBLIOGRAPHY

Agrawal, H. (1966). "Some generalizations of distinct representa-
tives with applications to statistical designs", Ann. Math.
Statist. 37, pp. 525-528.

Albert, A.A. and Sandler, R. (1968). An Introduction to Finite
Projective Plpnes. Holt, Rinehart and Winston, New York.

Birkhoff, G. and MacLane, S. (1959). A Survey of Modern.Algebra.
Macmillan Company, New York.

Bose, R.C. (1947). gMathematical theory Of the symmetrical factorial
design", Sankhya, Vol. 8 (Part 2), pp. 107-166.

Bose, R.C. (1957). "Combinatorial systems". Unpublished class
notes, University of North Carolina, Chapel Hill.

Bose, R.C. and Kishen, K. (1940). "On the problem of confounding

in the general symmetrical factorial design", Sankhya, Vol. 5,
pp. 21-36.

Bose, R.C. and Nair, K.R. (1939). "Partially balanced incomplete
block designs", Sankhya, Vol. 4, pp. 337-372.

Bose, R.C. and Nair, §.R. (1941). "On complete sets of Latin
squares", Sankhya, Vol. 5, pp. 361-382.

Bose, R.C. and Shrikhande, 8.8. (1960). "On the construction of
pairwise orthogonal Latin squares and falSity of a conjecture
of Euler", Trans. Aner. Math. Soc. 95, pp. 191-209.

Bruck, R.M. (1955). "Difference sets in a finite group", Trans.
Amer. Math. Soc. 78, pp. 464-481.

Bruck, R.M. (1963). "What is a lOOp?", Studies in Modern Algebra,
Math. Assn. of Amer., pp. 59-99.

Carmichael, R.D. (1956). Groups of Finite Order. Dover Publications
Inc., New York.

Chowla, S. and Ryser, H.J. (1950). "Combinatorial problems",
can. J. Math. 2’ pp. 93-99.

Cochran, W.G. and Cox, G.M. (1966). Experimental Designs. Wiley,
New'York.

66

67

Dembowski, P. (1968). Finite Geometries. Springer-Verlag, New York.

Ehrenfeld, S. (1953). "On the efficiency of experimental designs",
Ann. Math. Statist. 26, pp. 247-255.

Feller, W. (1965). An Introduction to Probability Theory and its
Applications, Vol. I. Wiley, New York.

Finkheiner, D.T. (1966). Introduction to Matrices and Linear
Transformations. Freeman and Co., San Francisco.

Finney, D.J. (1945). "The fractional replication of factorial
arrangements", Annals of Eugenics 12, pp. 291-301.

Fisher, RJA. (1925). Statistical Methods for Research Workers,
Oliver and Boyd, Edinburg.

Fisher, R.A. (1942). "The theory of confounding in factorial

experiments in relation to the theory of groups", Annals
of Eugenics 11, 341-353.

Fisher, RnA. (1960). The Design of Experiments. Hafner, New York.

Hall, M. (1943). "Projective planes", Trans. Aner. Math. Soc.
54, pp. 29-77.

Hall, M. (1945). “An existence theorem for Latin squares", Bull.
Amer. Math. Soc. 51, pp. 387-388.

Hall, M. (1948). "Distinct representatives of subsets", Bull.
Amer. Math. Soc. 54, pp. 922-926.

Hall, M. (1956). “An algorithm for distinct representatives",
Amer. Math. Monthly 63, pp. 716-717.

Hall, M. (1959). Theory of Groups. Macmillan, New York.

Hall, M. (1967). Combinatorial Theory, Blaisdell Publishing Co.,
Massachusetts.

Hedayat, A. and Seiden, E. (1969). "On a method of sum composition
of orthogonal Latin squares", RM-238, Department of Statistics
and Probability, Michigan State University.

Hedayat, A. and Seiden, E. (1970). "On a method of sum composition
of orthogonal Latin squares III, RM—259, Department of
Statistics and Probability, Michigan State University.

John, P.W. M. (1971). Statistical Design and Analysis of Experi-
ments. Macmillan, New York.

68

Kiefer, J. (1958). "On the nonrandomized Optimality and randomized
nonoptimality of symmetrical designs", Ann. Math. Statist. 29,
pp. 675-699.

Kiefer, J. (1959). "Optimum experimental designs", J. Roy. Statist.
Soc., Series B, 21, pp. 272-319.

Kempthorne, 0. (1952). The Design and Analysis of Experiments.
Wiley, New York.

Levi, F.W. (1942). Finite Geometrical Systems. University of
Calcutta.

Liu, C.L. (1968). Introduction to Combinatorial Mathematics.
McGraw-Hill, New York.

Marcus, M. and Minc, H. (1964). A Survey of Matrix Theory and
Matrix Inequalities. Allyn and Bacon Inc., Boston.

 

Peng, R.C. (1967). The Design and Analysis of Scientific Experi-
nents. Addison-Wesley, Massachusetts.

 

Plackett, R.L. (1946). "Some generalizations in the multifactorial
design", Biometrika 33, pp. 328-332.

Plackett, R.L. and Burman, J.P. (1946). "The design of optimum
multifactorial experiments", Biometrika 33, pp. 305-325.

Quist, B. (1952). "Some remarks concerning curves of the second
degree in a finite plane",.Ann. Acad. Sci. Fennicae, Series

A, I: Math-Phys. (134).

Rao, C.R. (1968). Linear Statistical Inference and its Applications.
Wiley, New York.

Ryser, H.J. (1963). Combinatorial Mathematics. Wiley, New York.
Scheffe, H. (1967). The Analysis of Variance. Wiley, New York.

Seidel, J.J. (1969). "Discrete mathematics". Unpublished class
notes, Michigan State University.

Seiden, E. (1950). '%.theorem in finite projective geometry and
an application to statistics", Proc. Amer. Math. Soc., Vol. 1,
pp. 282-286.

Seiden, E. (1954). "On the problem of construction of orthogonal
arrays", Ann. Math. Statist. 25, pp. 151-156.

Seiden, E. (1955). "On the maximum number of constraints of an
orthogonal array", Ann. Math. Statist. 26, 132-135.

69

Seiden, E. (1955). "Further remarks on the maximum number of
constraints of an orthogonal array", Ann. Math. Statist. 26,
pp. 759-763.

Seiden, E. and Zemach, R. (1966). "On orthogonal arrays", Ann.
Math. Statist. 37, pp. 1355-1370.

Smith, C.A.B. and Hartley, H.0. (1948). "The construction of
Youden squares", J. Roy. Statist. Soc., Series B, 10, pp.
262-263.

Stanton, R.C. and Sprott, D.A. (1958). “A family of difference
sets", Canad. J. Math. 10, pp. 73-77.

Tang, P.C. (1938). "The power function of the analysis of variance
tests with tables and illustrations of their use", Stat.
Research Memoirs 2, pp. 126-149.

Wald, A. (1943). "On the efficient design of statistical investiga-
tions", Ann. Math. Statist. 14, pp. 134-140.

Yates, F. (1937). "The design and analysis of factorial experi-
ments", Imperial Bureau of Soil Science, Harpenden, England.

Youden, W.J. (1940). "Experimental designs to increase accuracy
of greenhouse studies", Contr. Boyce Thompson Inst. 11, pp.
219-2280

A“
"I