J. R. Statist. Soc.

B (1982),
44, No.2, pp. 221-225

Conjectures for Optimal Block Designs

By J. A. JOHN and E. R. WILLIAMS

University of Southampton, CSIRO. Australia
Southampton, UK
[Received April 1981]

SUMMARY
In the study and construction of optimal block designs over the past 20 years a number of
conjectures have been repeatedly stated and used. The purpose of this note is to bring
together some of these conjectures. Although known to those actively engaged in
research in design, it is hoped that this note will stimulate other statisticians and
mathematicians to give their attention to these unsolved problems.
Keywords: OPTIMAL DESIGNS; DUAL DESIGNS; COMPLEMENTARY DESIGNS; CANONICAL EFFICIENCY
FACTORS; REGULAR GRAPH DESIGNS; BINARY DESIGNS; NON-BINARY DESIGNS

l. INTRODUCTION
A NUMBER of conjectures have been used over the past few years in the construction of A-, D-
and E-optimal block designs. These conjectures are brought together in this paper. It is shown
that the known results for (M, S)-optimality form a basis for the conjectures. The paper is
primarily concerned with equal replicate block designs, although in the final section some
comments are made about designs with unequal replication but equal-sized blocks. In Section
2 the various optimality criteria are defined in terms of the canonical efficiency factors of a
design. Conjectures for binary and non-binary designs are then discussed in Sections 3 and 4
respectively.

2. PRELIMINARIES
A block design of size (v, k, r) has v treatments set out in b blocks each of size k with each
treatment replicated r times, where b = orlk. The incidence matrix of a design is a v x b matrix
N = (nij) where nij represents the number of times that the ith treatment appears in the jth
block. If nij = 0 or I for all i and j the design is called a binary design; otherwise it is non-
binary. Only connected designs are considered here, a design being connected if all contrasts in
the treatment parameters are estimable.
The canonical efficiency factors (c.e.f.) e l,e 2 , ... ,e v - 1 are the non-zero eigenvalues of
A = I -(I/rk) NN', (I)
see James and Wilkinson (1971). The harmonic mean of the c.e.f. is equal to the usual overall
efficiency factor based on the average variance of pairwise treatment differences. No treatment
contrast can be estimated with an efficiency factor smaller than the minimum of the c.e.f
There are three optimality criteria usually considered when comparing different designs,
namely A-, D- and E-optimality. In terms of the c.e.f., they are
A -optimality: max (L e; I) - I,
i

D-optimality: max (f] e j ) , (2)

i

E-optimality: max (min e;).

A-optimality aims to maximize the harmonic mean efficiency factor whilst E-optimality is
concerned with minimizing the maximum variance of a treatment contrast. D-optimality
© 1982 Royal Statistical Society 0035-9246/82/44221 $2.00
222 JOHN AND WILLIAMS - Conjectures for Optimal Block Designs [No.2,
involves maximizing the geometric mean efficiency factor which is equivalent to minimizing the
generalized variance of the estimates of the treatment parameters, see Kiefer (\958).
Another useful criterion is that of (M, S)-optimality (Shah, 1960; Eccleston and Hedayat,
1974). It is a two-stage procedure defined as follows
(M, S)-optimality: max (L e j) then min (L ef). (3)
i i

That is, the subclass of designs which maximizes L e, is formed; this is the M-optimality part.
An (M, S)-optimal design is selected from this subclass so that L e? is minimized; that is S-
optimality is concerned with minimizing the spread or variance of the c.e.f.
The dual design is important when b > v. It is obtained by interchanging treatment and
block labels, that is the dual of a design with incidence matrix N has incidence matrix N'. Since
NN' and N'N have the same non-zero eigenvalues, it follows from (2) and (3) that if a design is
optimal under any of the four criteria, then the dual is also an optimal design for its size.

3. DESIGNS WITH k ~ v
For k ~ v, binary designs need only be considered since, as Cox has pointed out in the
discussion in Tocher (1952), non-binary designs are inefficient. Clearly, non-binary designs are
not (M,S)-optimal, as Le j or trace of the A matrix in (I) is maximized for binary designs. For
binary designs, the off-diagonal elements of the concurrence matrix NN' in (1) give the numbers
of blocks in which pairs of treatments appear together. These elements will be referred to as the
;.-values of the design. Here (M, S)-optimality corresponds to minimizing the sum of squares of
all the ;.-values. A design whose ;.-values are all equal (a balanced incomplete block, BIB,
design) or take one of two values ;'1 or ;'1 + 1 is called a regular-graph (RG) design. Clearly a
RG-design (when it exists) is (M, S)-optimal. For most parameter combinations a RG-design
can be found. When a RG-design does not exist the (M, S)-optimal design will have some ;.-
values differing by 2 (or perhaps more).
An (M, S)-optimal design with the harmonic mean efficiency factor at least as large as that of
any other (M, S)-optimal design of the same size is defined as being A I-optimal; D 1- and E 1-
optimality are defined in a similar fashion.
Conjecture I. An AI (or D I or Ed-optimal design with v ~ b is also A (or D or E)-optimal.
When v> b, the conjecture can be applied to the dual design. The conjecture is certainly
true if the design is a BIB design, since then all the c.e.f. are equal.
This conjecture has been used by John (\966) and John et al. (1972) to construct tables of
cyclic incomplete block designs. It has also been used by Patterson and Williams (1976) to
construct iX-designs, a class of resolvable incomplete block designs; also by Williams et al.
(\977) to construct efficient two-replicate resolvable designs. An examination of the tables of
partially balanced incomplete block designs with two associate classes (PBIBj2) given by
Clatworthy (1973) shows that, where different designs of the same size are given, a RG-design is
better than any other design (using A-optimality).
Mitchell (1973) used a computer algorithm to construct D-optimal designs for v + b ~ 31
and vr~44. For every parameter set, the best design (or its dual with v>b) was a RG-design.
Following from this work, John and Mitchell (\977) carried out a systematic computer search
for A-, D- and E-optimal RG designs for all parameter sets in which v ~ 12, r ~ 10 and v ~ b; for
v> b the duals of the optimal designs for 1'< b were presented. They conjectured that these
designs were optimal over the entire class of designs of size (v, k, r). More recently, Jones and
Eccleston (1980) described a computer algorithm to search for A-optimal designs. To test their
program they attempted to generate the 209 optimal designs of John and Mitchell (1977). In
192 cases the best designs produced by the algorithm were the same as those given by John and
Mitchell; for the other cases they were slightly worse.
1982] JOHN AND WILLIAMS - Conjectures for Optimal Block Designs 223
Work on E-optimal designs has also supported the conjecture although Cheng (1978) gives
a design for v = 4 and k = 2 which is not (M, S)-optimal but whose smallest c.e.f. is the same as
for the design listed in John and Mitchell (1977). Takeuchi (1961) showed that a group divisible
PBIB/2 design with tt 2 = }'I + 1 is E-optimal. Other results on PBIB/2 designs have been given
by Cheng (1978, 1980)and Jacroux (1980). Cheng (1980) has also considered the 209 parameter
sets studied by John and Mitchell (1977). For 176 sets he shows that the designs are E-optimal;
the remaining 33 sets for which the E-optimal designs are stillunknown are listed in the paper.
Jacroux (1980) also considers the E-optimality of RG-designs.
Support for the conjecture is also given by Conniffe and Stone (1974,1975) and Shah et al.
(1976).
Conjecture 2. If an (M, S)-optimal design is A-optimal (D-optimal) then it is also D-optimal
(A-optimal).
John and Mitchell (1977) observed that the best design on the A-optimality criterion was
also best on D-optimality. The E-optimal design on the other hand was sometimes found to be
different.
Complementary designs
If a design D of size (v, k, r) has incidence matrix N, then the complementary design
D* = K -D of size (v, k*, r*) has incidence matrix J - N, where k* = v-k, r* = b-r and J is a
v x b matrix of ones; K is the complete block design with v = k. For k* = 1, D* is degenerate
and hence is not considered. If e I' e 2 , ..., e; _ 1 are the c.eJ. of D then it can be shown that the
c.e.f. of D* are given by er where
er = l-IX(1-ei) (i= 1,2, ...,v-l) (4)
with IX = rk/(r* k*). It follows from (2), (3) and (4) that if D is (M, S) (or E)-optimal then D* is
also (M,S) (or E)-optimal; see also Jacroux (1978).

Conjecture 3. The complementary design of an A (or D)-optimal design is also A (or D)-
optimal.
The conjecture is true if D is a BIB design, since D* will also be a BIB design. The
complementary design of a RG-design is also a RG-design since its concurrence matrix is equal
to NN' +(b-2r)J. John and Mitchell (1977) observed that, in all cases they considered, if a
design D was optimal within the class of RG designs then the complementary design K - D was
also optimal within the same class.
John et al. (1972) and Williams et al. (1977) have made use of this conjecture in the
construction of cyclic and two-replicate resolvable designs respectively.

4. DESIGNS WITH k:» v

When k » v, designs are necessarily non-binary. Such designs can be useful in practice; they
have also been used by Williams et al. (1977) to construct optimal two-replicate resolvable
designs.
Let the general class of designs with incidence matrix of the form pJ + No be denoted by
pK + Do where p ~ 1 and Do is a binary design of size (v, k o, r o) with incidence matrix No.
Clearly an (M, S)-optimal non-binary design will belong to the class pK + Do. Further if Do is
(M, S)-optimal then so is D (Jacroux and Seely, 1977). This prompts the following conjectures:
Conjecture 4. The A-, D- and E-optimal non-binary designs belong to the class pK + Do.
Conjecture 5. If Do is an A (or D or E)-optimal design then D = pK +D o is A (or D or E)-
optimal.
These conjectures are true if Do is a BIB design. We note also that if e l , e2' ..., e v - I are the
224 JOHN AND WILLIAMS - Conjectures for Optimal Block Designs [No.2,
c.e.f. of Do then the c.e.f. of D are given by h where
L> 1-tx(l-eJ (i= 1,2, ...,v-l) (5)

with tx = r o ko/(rk) which is of the same form as (4). It follows from (5) that if conjecture 4 is true,
conjecture 5 is certainly true for the E-optimality criterion.
Further support for Conjecture 5 is provided by Williams et al. (1977) who showed that,
within the class of RG-designs and within a given range of parameter values, optimal non-
binary designs were obtained by adding complete replicates to the blocks of the binary designs
of John and Mitchell (1977).
5. DESIGNS WITH UNEQUAL REPLICATION
Some remarks on the wider class of designs with unequal replication but equal-sized blocks
can be made. Let Sv.b,k denote the collection of all designs with v treatments in b blocks of size
k ~ v; the equal replicated designs constitute a subset of Sv.b,k' If r is the replication vector and
r~ the diagonal matrix of replications, the information matrix of a design is given by
C = r6 - (I / k) N N '. The optimality criteria are then expressed in terms of the non-zero
eigenvalues of this C matrix.
Many of the results on E-optimality by, for example, Takeuchi, Cheng and Jacroux apply
in fact over SV.b,k' Cheng (1980) in considering the 209 parameter sets in John and Mitchell
(1977) showed that for 159 sets the designs are E-optimal over Sv,b.k whilst for the other 17 sets
only the E-optimality over the equal replicated designs could be claimed at present. Jones and
Eccleston (1980) found for the three parameter sets (v, b,k) = (10,10,2), (11,11,2), (12,12,2)
that their algorithm produced designs which were better than those of John and Mitchell for
A- and E-optimality, but which had unequal replication. On D-optimality the equal replicated
designs were better. Conjecture 1 does not, therefore, hold over the entire class Sv,b,k' although
it would be of interest to know whether there are cases other than those with v = b ~ 10 and
k = 2 where a design with unequal replication is better than an equal replicated design, Note
that the use of designs of size (v, v, 2) would only give one degree of freedom for error; the three
designs above are therefore of academic rather than of practical interest.

REFERENCES
CHENG, C. S. (1978). Optimality of certain asymmetrical experimental designs. Ann. Statist ; 6, 1239-1261.
- - (1980). On the E-optimality of some block designs. J. R. Statist. Soc. B,42, 199-204.
CLATWORTHY. W. H. (1973). Tables of Two-associate-class Partially Balanced Designs. Washington: National Bureau
of Standards. (Appl, Math. Ser. 63.)
CONNlfFE,D. and STONE, J. (1974). The efficiency factor of a class of incomplete block designs. Biometrika, 61, 633-636.
- - (1975). Some incomplete block designs of maximum efficiency. Biometrika, 62, 685-686.
ECCLESTON, J. A. and HWAYAT, A. (1974). On the theory of connected designs: characterization and optimality. Ann.
Statist., 2, 1238-1255.
JACROUX, M. A. (1978). On the properties of proper (M,S) optimal block designs. Ann. Statist.; 6, 1302-1309.
- - (1980). On the E-optimality of regular graph designs. J. R. Statist. Soc. B, 42, 205-209.
JACROUX, M. A. and SEELY, J. (1977). Some sufficient conditions for establishing (M.S)-optimality. Technical Report
No. 57, Department of Statistics, Oregon State University.
JAMES, A. T. and WILKINSON, G. N. (1971). Factorization of the residual operator and canonical decomposition of
nonorthogonal factors in the analysis of variance. Biometrika, 58, 279-294.
JOHN, J. A. (1966). Cyclic incomplete block designs. J. R. Statist. Soc. B, 28, 345-360.
JOHN, J. A. and MITCHELL, T. J. (1977). Optimal incomplete block designs. J. R. Statist. Soc., B 39, 39-43.
JOHN, J. A., WOLOCK, F. W. and DAVID: H. A. (1972). Cyclic Designs. Washington: National Bureau of Standards.
(Appl. Math. Ser. 62.)
JONES, B. and ECCLESTON, J. A. (1980). Exchange and interchange procedures to search for optimal designs. J. R.
Statist. Soc. B, 42, 238-243.
KIEFER, J. (1958). On the non-randomized optimality and randomized non-optimality of symmetric designs. Ann.
Math. Statist.; 29, 675-699.
MtTCHELL, T. 1. (1973). Computer construction of small "D-optimal" incomplete block designs. Proc. 39th Session lSI.
pp. 732-738.
1982] JOHN AND WILLIAMS - Conjectures for Optimal Block Designs 225
PATTERSON, H. D. and WILLIAMS, E. R. (1976). A new class of resolvable incomplete block designs. Biometrika, 63, 83-
92.
SHAH, K. R. (1960). Optimality criteria for incomplete block designs. Ann. Math. Statist; 31,791-794.
SHAH, K. R., RAGHAVARAO, D. and KHATRI, C. G. (1976). Optimality of two and three factor designs. Ann. Statist., 4,
419-422.
TAKEUCHI, K. (1961). On the optimality of certain types of PBIB designs. Rep. Statist. Appl. Res. Un. Japan Sci. Engrs.,
8, 140--145.
TOCHER, K. D. (1952). The design and analysis of block experiments (with discussion). J. R. Statist. Soc. B, 14,45-91.
WILLIAMS, E. R., PATTERSON, H. D. and JOHN, J. A. (1977). Efficient two-replicate resolvable designs. Biometrics, 33,
713-717.