ON ORTHOGONAL ARRAYS OF STRENGTH EGUR: t: '

AND THEIR APPUCATIONS

1965

 

 

THESlS

LIBRARY

Michigan State
University

 

This is to certifg that the
thesis entitled

ON ORTHOGONAL ARRAYS OF STRENGTH FOUR
AND THEIR APPLICATIONS

presented bg
Rita Zemach

has been accepted towards fulfillment
of the requirements for

% Jaye»

 

Major professor

0-169

,, Roomusfomv

 

 

 

a?

- O

ABSTRACT

ON ORTHOGONAL ARRAYS OF STRENGTH FOUR
AND THEIR APPLICATIONS

by Rita Zemach

An orthogonal array (N,k,s,t) of 3 levels, k constraints,
strength t, and index Q, is a k X N matrix with entries from a set
of 5 elements, 5 3 2, such that each t X N sub-matrix contains
all possible t x 1 column vectors with the same frequency Q. The
array serves as a design for a factorial experiment, with k factors,
each occurring at 5 levels, and N treatments. If the array is of
strength t = 2v, all interactions involving v or fewer factors can
be estimated, assuming there is no interaction of more than v factors.
If t = 2v + 1, all interactions involving v or fewer factors can
be estimated even if interactions of v + 1 factors are present, but
estimates of interactions of v + 1 factors may be confounded with
one another. Thus arrays of strength four have the smallest strength
which allows estimation of main effects and all first-order interactions,
assuming that higher order interactions are negligible.

The main problem of interest for orthogonal arrays is to determine

the maximum possible number of constraints for given N, s and t.

9
Chapter I is devoted to a general discussion of orthogonal arrays,
and the method of analysis. An iterative bound on the maximum number

of constraints for an array (Qst,k,s,t) is given, which depends on the

n ‘ . t—
maX1mum number of constraints for an array (Qs l,k,s,t—l).

Rita Zemach
The main theorem of Chapter II gives a method of constructing an

t+1 t
,k+l,2,t+l) from an array A" = (Q2 ,k,2,t), when

array A = (02
t = 2v. If k is the maximum number of constraints possible for A',
then R + l is the maximum possible number of constraints for A.

In addition, the structure of arrays (Q2t,t+l,2,t) is analyzed,
and for Q: q2n , a method of extending any array (Q2t,t+1,2,t) to
t + n + 1 constraints is described.

Chapter III describes a method of constructing arrays by matrix
multiplication, due to Bose, for the case s = pu, Q = pv, p a prime.
The algebraic properties of arrays of this class are discussed, and
bounds on the maximum possible number of constraints are reviewed. A
bound is given for arrays of strength four which can be constructed
by matrix multiplication, when s = 3, Q = 3U.

In Chapter IV, the maximum possible number of constraints is
determined, when s = 2, t = h, for arrays with N = 32, £8, 6A and
80. In each case, arrays with the maximum number of constraints are
constructed. A detailed examination of the structure of most of the
arrays is included.

The last Chapter is devoted to a brief discussion of the relation

of orthogonal arrays to information theory.

ON ORTHOGONAL ARRAYS OE STRENGTH FOUR

AND THEIR APPLICATIONS

By

Rita Zemach

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Statistics

1965

ACKNOWLEDGMENTS

 

I wish to express my gratitude to Dr. Esther Seiden for sug-
gesting this area of research, and for her helpful guidance and
valuable advice in the preparation of this thesis.

I appreciated very much the support of my research by the National
Science Foundation through fellowships from September 1962 to September
1963, and during the summer of 196A.

Finally, I wish to thank my husband and children for their patience

and encouragement during my entire period of graduate study.

ii

TABLE OF CONTENTS

CHAPTER
I INTRODUCTION .
1.1 Factorial Design . . . . . . . . . . .
1.2 Orthogonal Arrays . . . . . . . . . . .
1.3 Some Conditions Necessary for the
Existence of Arrays . . . . . . . . . .
1.h Analysis of Arrays . . . . . . . . . . . .
II THEORENS ON CONSTRUCTION OF ARRAYS . . . . . . . . . .
2.1 Construction of Arrays of Strength t+l from
Arrays of Strength t when t=2v, s=2 . . .
2.2 Structure of Arrays of Strength t with
t+l Constraints . . . . . . .
III GROUP ARRAYS . . . . . . . . . . . . . . . . . . .
3.1 Relation of Orthogonal Arrays to Finite
Projective Geometry
3.2 Bounds on the Number of Constraints of Arrays
of Strength Four of Type C x B . .
3. 3 Structure of Arrays of Type C x r . .
3 b Confounding in Arrays of the Form C x Br
IV ARRAYS or 32, 118, 61; AND 80 COLUMNS, s : 2, t = Li
A.l Arrays of 32 Columns, 3 = 2, t = b
b.2 Arrays of AB Columns, 5 = 2, t = A
A.3 Arrays of 6A Columns, 3 = 2, t h .
A.b Arrays of 80 Columns, 3 = 2, t b

RELATION OF FACTORIAL DESIGN TO INFORMATION THEORY .

BIBLIOGRAPHY .

iii

PAGE

13

13
16

2O

CHAPTER I

INTRODUCTION

1.1 Factorial Design

 

Frequently in statistical investigations it is known that the
characteristic being studied is affected by several different factors,
F1, ..... ’Fk' Each factor may assume ssexrer‘al different levels,

e.g. Fi assumes si levels, i = l, ..... k. Estimation of each of the
main effects is desired, as well as information about interactions

among the various factors.

I shall call a complete factorial design one which includes each

 

of the possible 31 . 52 ° .... . sk treatments exactly once. A
treatment in which F1 occurs at level a,, i = l,....,k will be desig—
nated by (a1, a2,....,ak).

In a symmetrical factorial design all factors assume the same

 

number of levels, i.e. s1 = 52 r ..... = s = s. In this case a

,
complete factorial design consists of the set of all sk possible
k-tuples of 5 elements. It will be referred to as a complete sk
design.

The true yield of a treatment in a factorial design is in general
regarded as the sum of an over—all mean u, the effects of the k fac—
tors, and the effects of interactions of all orders among these
factors.

The special case s r 2 occurs when each of the k factors

assumes 2 levels, which may be the presence or absence of the factor,

or its existence at high or low intensity, or in two different forms.

If the number of factors is very large, the number of treatments
necessary for a complete sk design reaches a prohibitive size. This
problem arises, for example, in exploratory experiments, where the
researcher cannot, for the time being, ignore the effect of any factor
which may influence the characteristic under investigation. At the
same time, although the complete sk design provides estimates of
interactions of all orders, in most practical situations the higher
order interactions may be assumed to be negligible.

These considerations have given rise to the use of fractional
replication of complete factorial designs. In a l/sn replication
of a complete sk factorial design, the 5k treatments are partitioned
into blocks of sk_n treatments, satisfying certain properties. This
type of design is discussed in section 3.1. One block may be represented
by a k X sk_n matrix representing k factors and sk_n treatments.

The term block of a design will hereafter imply a block of a parti—

 

tioning as described.

The partitioning of a complete sk design is said to be of strength
t if no interaction of t or fewer factors is confounded with the
block effect. The prOperties of a single block as a design will be

described under the more general topic of orthogonal arrays.

1.2 Orthogonal Arrays

 

An orthogonal array (N,k,s,t) of 5 levels, R constraints,

strength t and index Q , is a k x N matrix A with entries

)

from a set S of 3 elements, s Z 2 such that each t X N sub-

)

matrix of A contains all possible t x 1 column vectors of S with

3
the same frequency Q. Clearly N = Qst. The set S may be taken
as the set of integers (0,1, ..... ,s—l).
If A is of strength t , then any k“ x N sub—array, t‘f k9 f k

)
is also of strength t . Hence, if no array (Qst, k', s, t) exists,
then neither does any array (Qst, k, s, t) for k > k'.

If A is of strength t , it is also of strength tY for
every t7 f t.

An orthogonal array serves as a design for a factorial experiment,
with k factors at s levels, and N treatments.

Arrays of the form (52, k, s, 2) may be derived from k-2
mutually orthogonal Latin squares of side 5 , the rows of one square

providing one row of the array. The remaining two rows are derived

from the following orthogonal (but not Latin) square and its transpose:

 

O O ....... O

I l ........ l

2 2 ....... 2
(5—1) (3—1) ....... (s—l)

 

Orthogonal arrays were introduced by C. R. Rao, [17], who first
discussed these factorial designs in terms of ”hypercubes” of strength
t .

If the design of a factorial experiment is an orthogonal array
of strength t , then no estimate of a main effect is confounded with
any interaction of (t—l) or fewer factors, and in general, no inter-
action involving m factors, m < t, is confounded with an interaction

involving (t-m) or fewer factors.

 

A

By using an array of strength 2t, all interactions involving
t or fewer factors can be estimated, assuming there are no inter—
action of more than t factors. With an array of strength 2t+l,
interactions of t factors can be estimated, even if interactions of
t+l factors are present. However, interactions of t+l factors may
be confounded with one another.

Thus arrays of strength A, which will be the subject of par-

,
ticular study in this thesis, allow estimation of all main effects
and all first-order interactions, assuming that interactions of
second or higher order are negligible. (An interaction is "of nth
order" if it involves n+1 factors.)

If no interaction of more than (t—l) factors is present, a suf—
ficient condition to measure all main effects only is that an array
be of strength t.

It should be noted that while a block of a factorial design of
strength t (see Sec. 1.1) is an orthogonal array of strength t,
the converse is not true. The array need not satisfy all the condi-
tions imposed on the block, and may still be of strength t.

In particular, a complete sk factorial design is an array of
strength k.

The main problem of concern with respect to an array A=(N,k,s,t)

is the maximum value of k for a given t, N, and s or the maximum

9
number of factors which can be accomodated in a design of strength t
and index Q.

The maximum number of constraints for orthogonal arrays of

strength 2 and 3, when s=2, has been determined for many cases.

S
For the case t=2, it was shown by Plackett and Burman [16] that for
an array (Qsz,k,s,2)

2
< Qs — l
k ‘ s - l

which reduces to k 5 AQ — 1 for the case s=2. Construction of
arrays which achieve this bound for all Q up to Q=SO, except for
the cases 0:29, A7, has been determined by Paley [15], Williamson [23],
and Baumert and Hall [3]. A method of construction is given whenever
n

O = 2 . (See [5, 11, 15]). For the case t=3, Rao [17] shows that

for an array (Q83,k,5,3)

Qs2 - 1

<
k _ s - 1

+ 1

which reduces to k 5 AQ when s=2. Again it was shown by Bose [5]
that arrays can be constructed with k=hQ when Q=2n. Seiden [19]
gives a method of construction of arrays (Q23,hQ,2,3) whenever an array
(Q22,hQ-l,2,2) exists.

For the case t=h, the bound of Rao becomes

 

(s-3)+ i/(s-Bi2 + 8(Qs4-1)

k E 2(s-1)

 

which gives the following bounds for s=2:

 

N Q R
(l) 16 1 5
(2) 32 2 7
(3) 118 3 9
(A) on t 10
(5) 8o 5 12

6
It will be shown that for the cases listed, this bound can be
achieved only for case (1). Moreover, in the remaining cases, the
exact maximum for R will be established.
Bush [9] has shown that, in general, if Q=l,
k,f s + t — 1 3 even

k s + t - 2 3 odd.

I/\

If s fft, then the bound is attained, for s=pn, p a prime.
The following inequality can be established between the max—

imum number of constraints k' and k of orthogonal arrays

t—l
s

t
(O ,k',s,t—l) and (Q5 ,k,s,t):

Let k' be the maximum number of constraints
possible for an array of index Q and strength t—l.
Then for an array of index Q and strength t, k f k' + 1.

Proof: Let A = (Qst,k,s,t) be an orthogonal array of strength t.

th

The i row of A, i=1,....,k, contains each element O,l,2,...,s—1

repeated Qst-l times. Without loss of generality, consider the

first row. Let A' be any sub—matrix of t—l rows from among the

last k—l rows. Each of the st—1 (t—l)-tuples must appear exactly

Qs times in A' and these must be arranged so that each one appears

9
exactly Q times following each of the elements O,1,...,s—l in the
first row. Therefore the last k—l rows may be partitioned into s

t_1,k_1,s,t—1). Hence if k' is the maximum number of

arrays (Qs
constraints possible for an array of strength t-l, the maximum for

an array of strength t is less than or equal to k'+l.

7

1.3 Some Conditions Necessary for the Existence of Arrays

 

For any orthogonal array A = Gfl,k,s,t) of index Q, let nij
denote the number of columns (other than the 1th) having j coin-
cidences with the 1th column, i=1 N; j=O,... R. It is shown by

’0...) ’

Bose and Bush [7] that for each i

, the k variables nij must

satisfy a set of t+l linear equations:

: (g) n,, = (i) (Qst‘h-i) 1 5 h < t

where (g) = O for j < h. These equations will be used in several
proofs and will be referred to as the "necessary equalities.”
Some additional properties will prove useful for the construc-

tion of orthogonal arrays.

PrOperty 1: For an array A = (Qst,k,s,t), let gik be the maximum

value of nik among all solutions to the necessary equations. Then

for any array it is necessary that

n.. < (i?) (9

1J _ J ik + l) J=O,l,...,H-l.

Proof: Suppose a particular column having j coincidences with the

.t . A .
1 h column is repeated more than nik+l times. Then an array would
exist whose solution yields nik > gik' There are at most (g) columns

having j coincidences with the 1th column.

8

Property 2: If no solution exists with nik > 0, then every array

(Ost,k,s,t) has Qst distinct columns. This follows from property 1.

Property 3: If for some k, nik

k',s,t) with k' > k must have n

= O for all solutions, then every

 

O.

array OQst,

ik
For the case t=h, the equations take the form:

 

k
E n.. = QS4 - l

1J
j=
k

° = 3-
E Jnij MOS 1)
le
R

J = k 2-
E 1pm,, (2) (OS 1)
i=2
k

j _ k

n.. — s — l

E (3) ,, (3)(Q >
i=3
R

J = k _
E (1,) n1, 9,) (Q n
J=A

l.h Analysis of Orthogonal Arrays
Consider k factors Fl, ..... ’Fk’ Let A = (N,k,2,h) be the
array. Let dijm_ _ be the true yield of the treatment with F,

at level i, F2 at level j, F3 at level m, etc., where each i

9

j, m, —, -, is either 0 or 1, and ijm——— takes on at most only those

N distinct values indicated by the N columns of the array A.

9
The main effects of factors F1, F2, F3, —-- will be denoted

by the lethzs a b c etc.

, , , and the interactions by pairs (ab),

)
(ac), (be), etc. It is assumed that no interactions of three or more
factors are present. The parameters to be estimated are the over-all

mean u, k main effects, and k(k—l)/2 first-order interactions.

Assume that:

m -;
II
I!
Q
Q
I ll
(32 1—4
a
II M
Q
[\3 ._..
E L"
a
l
l
- 1
Q
I
Q

l l. ..... (1 flxed) le--" .....
b. = a - a
J .J .....
(ab).. = a - a. — a + a
lJ lJ 1. J .....

(In practice it is customary, with only two levels, to define each
effect at twice the value given here, so that, for example, with
one factor the effect is

a = a, — do

rather than

a1 = a1 — l/2(al + co)
= 1/2(c1l — do) = 1/2(a)
a0 = do - l/2(c1O + d1)

1/2(do — a1) = — 1/2 (a)
as indicated above.)

Let Y = yijm--- denote the l X N vector of observations

for (ijm-——) contained in A.

1O

The assumptions of the model are:

(1) yijmn- = u +{ai + bj + cm + —-—} (k main effects)

+<(ab)ij + (ac)im + 4} ((2) interactions)

+ 8..
1Jm——-

i,j,m,-,—,-, contained in (0,1)
(ijm—-—) contained in A
(ii) {e.,m___> are normally distributed with mean zero and co-

2
variance matrix I 0'

Because of the assumptions about the effects we have

1

a0 = -al for each main effect a;

(ab)ll = - (ab)lO

(ab)ll = - (ab)Ol

(ab)10 = — (ab)00

(ab)Ol = - (ab)OO for each interaction.
Hence, (ab)ll = (ab)OO = — (ab)lo = — (ab)01.

Therefore the estimates may be derived as follows: Let A%
be the k x N matrix derived from A by substituting -1 for O.
Construct the following m x N matrix X, m = (2) + k + l,
where each row of X corresponds to one of the parameters of the
model:
The first row of X consists of all 1's, and corresponds to u,
The next k rows are the rows of A%, and correspond to the

main effects of the k factors,

11
The row corresponding to an interaction (ab) is obtained as
follows: let i(a) be the ith element in the row cor-
responding to a , and let i(b) be the ith element in the
th

row corresponding to b. Then 1(a). i(b) is the i

element in the row corresponding to (ab), i = l N.

,....,
Because the array A is of strength A, A* has the property that in
each four-rowed sub-matrix, each possible column h—tuple of le and
—l's appears the same number of times. Thus the matrix X has the
property that any two rows are mutually orthogonal, and each row
except the first contains Qst“l 1's and Qs — —l‘s. These rows
of X therefore are the coefficients of a set of mutually orthogonal
contrasts.

Let B be the l x m vector

(u, a1, b1: cl,—-—, (ab)ll, (ac)ll, (bc)11:“')~
Then assumption (i) may be stated
E (Y) = O X.
In minimizing (Y — BX)‘(Y - BX) the normal equations, in matrix
form, are
XX'B' = XY'.

The matrix XX' is a diagonal matrix with N's along the diagonal
and zeros elsewhere.

Solving the normal equations yields

'év = (XX')—l XY'.
These least-square estimates are

:E yijm——— : y .....

A7?

Zli—a

A
LL:

 

12

g.l E -1
i N yijm--- N yijm——-
i fixed —i fixed
= yi — fl,:> for k main effects,
’\ _ l l :E
{:(ab)ij ‘ N :E yijm-—— ‘ N yijm---
ioj fixed -(i~j) fixed
_ +A
‘ymu.'yrn. %M. u

for (g) interactions, where i,j,m,—,—, are contained in (—l, l).

The estimate of an interaction of three or four factors, should
it be present, may be found by adding to the X matrix those rows
of A* which correspond to the factors involved. However, in arrays
of strength A, if three-factor interactions are present, two-factor
and three—factor interactions may be confounded. Similarly, if a
four—factor interaction is present, it may be confounded with a main
effect.

Each estimate has variance CTZ/N} If the experiment is
replicated m times, each effect or interaction is estimated by the
mean of m individual estimates, and thus has variance O'Z/TmN).

In a factorial experiment with k factors, each at 8 levels,
and N treatments, each main effect carries (8 — 1) degrees of
freedom, and each first—order interaction (3 - 1)2 degrees of free—

dom. The number of degrees of freedom for error is thus

N - 1 — k(s - l) - (g) (s - 1)2.

 

CHAPTER II

THEORENS ON CONSTRUCTION OF ARRAYS

2.1 Construction of Arrays of Strength t+l from Arrays of Strength
t When t = 2v, 5 = 2

 

 

Lemma: Let A be an array (Qst,t+l,s,t) with s = 2, of strength

 

t and t+l constraints. Then any two columns differing in an even
number of coordinates will appear the same number of times, and any
two columns differing in an odd number of coordinates will appear

together a total of Q times.

Proof: Let (a1, a2, )Y be any column (t+l)—tuple,where each

0..)at+l

ai is O or 1. Let a; be O if ai is 1 , and 1 if ai is O.

Let X(al,. denote the number of times the column (a1,

'°’at+1) °°°’at+1)v

appears in A. Since A is of strength t and index Q , for any

two coordinates ai and aj,

x(al,..,a,,..,aj,.,at,l)+ x(al,..,a:,..,aj,..,at+l) = Q;

X(a,,..,a:,..,a,,..,at+l)+ X(al,..,a:,..,a§,..,at+l) = O.
Therefore

x(a,,..,a,, .,aj,..,at+l) = x(a,,..,a?,,.,aj,..,at+l).

Hence two columns differing in two coordinates must appear the same
number of times, and two columns differing in one coordinate must
appear together Q times. By successive applications of this rule,
two columns differing in an even number of coordinates muat appear
the same number of times, and two columns differing in an odd number

of coordinates must appear together Q times.

13

1A
The following theorem is proved by Seiden in [19]:

Let S be an ordered set of 5 elements e0, el,.., For
any integer t consider the 5 different t tuples Sof the
elements of S. They can be divided into st 1 sets, each con-
sisting of s t— tuples and closed under cyclic permutation of
the elements of S Denote these sets by S i = 1,2, ,st 1.
Suppose that it is possible to find a scheme of r rows with
elements belonging to S
all 312 ... a1n
t—l
(n=QS)
a a ... a
r1 r2 rn
such that in every t—rowed sub-matrix the number of elements
belonging to each Si is the same, say, equal to Q; then one
can tuse this scheme in order to construct an orthogonal array
(Qst ,r, s ,t). If in addition this scheme consists of an array

of strength t—l, then one can construct an orthogonal array
(Qst, r+l,s,t).

Theorem: Let A = (Ost,k,s,t) be an array of strength t , where
t = 2v and s = 2. Then A may be used to construct an array of
strength t+l with n+1 constraints, and index 0. If k is
the maximum number of constraints possible for the array A, then
k+l is the maximum number of constraints possible for the new

array.

Proof: Let A? be any sub-matrix of A consisting of t+l rows.

 

Let (al,.,.,a ) be any (t+l)-tuple of the elements (0,1), and let

t+l
. . " " 1
X(al,...,at+l) be the number of times (a1,..,at+l) appears in A .
By the previous lemma, since t+l is odd,
I, ‘X’ 1“ .-
x\al,...,at+l) + X<a1""’at+1) ~ Q.

The array thus forms a scheme satisfying the conditions of the
theorem quoted. The second statement of the theorem follows from

the inequality proved in Section 1.2

15

This theorem shows that in considering the maximum number of
constraints possible for orthogonal arrays, for fixed values of 0,
it is sufficient to consider strengths t = 2v. The maximum number
of constraints for strength t = 2v+l will be exactly one more.

The previous theorem has the following application. It frequently
happens that after an experiment has been performed, it may seem de-
sirable to include one or more additional factors. Then either (1)
an entierly new experiment may be performed and the original informa—
tion disregarded, or (2) additional treatment combinations may be
designed so that information on the additional factors is obtained,
while information from the original treatments is preserved. For (2),
it must be assumed, of course, that there is no "block effect" of the
time lag between parts of the experiment.

Suppose one additional factor is to be included, where each factor
is at two levels, and suppose the original design was an orthogonal
array (Qst,k,s,t), s = 2, t = 2v. The obvious way to achieve (2) is
to consider the original experiment as half of an array (Qst+1,k+l,s,t)
and to add the remaining half-array in which the new factor will ap—
pear constant at the 1 level [1].

The problem may arise that while in the original experiment there
were no v+l—factor interactions, the introduction of a new factor
makes this assumption questionable.

The previous theorem shows that the additional treatment combina—
tions may be designed so that the augmented experiment is of strength

2v + l.

 

16

2.2 Structure of Arrays of Strength t with t+l Constraints

 

Let A = (2t,t+l,2,t) be an array of index 1, t: 2. By a
theorem of Bush [9], t+l is the maximum possible number of constraints.
By the lemma of section 2.1, each column differing from the first
column in an even number of places must appear once, and there are
no columns differing from the first column in an odd number of places.
The total number of columns differing in an even number of places is

2t-l

, and there are no other columns. This also proves the unique—
ness of the array A up to the permutation of the elements 0 and 1.

This proves: there is exactly one array of strength t , with
t+l constraints, and index 1, s=2, up to a permutation of the ele—
ments (0,1).

Hereafter this array will be denoted by D , and it will be
assumed that the first column consists entirely of 0's. Then if t
is even (odd), each (t+l)—tuple with an odd (even) number of 0's is
repeated exactly once in the array, where zero is considered even.

Let D' be the array of index one derived from D by per—
muting the elements (0,1) in any row. Since each column has the num-
ber of 0's increased or decreased by one, D' has the following
structure: there is no column of all 0's; if t is even (odd),
each column of D' has an even (odd) number of 0's. Since each
column is distinct, D' must contain each possible column with an
even (odd) number of 0's, because the total number of columns is
2t.

When t is even, interchanging 0 and 1 in one row is

equivalent to interchanging 0 and 1 in the entire array.

17

Example: For the case t=h , the two forms of the array

A = (24,5,2,h) are:

D:

O O O O O O O l l l l O l l l l
O O O O 1 1 1 O O O l l O l l l
O O l 1 O O l O O 1 O l 1 O l l
O l O l O 1 O O 1 O O 1 1 l O 1
O l 1 O 1 O O l O O O 1 1 1 1 O
D!

O O O O O O O l 1 l l O l l 1 1
O O O O l 1 1 O O O l l O 1 l 1
O O 1 1 O O l O O l O l l O l l
O l O 1 O 1 O O l O O l 1 l O l
1 O O 1 O l l O l 1 l O O O O 1

Theorem: Let A = (Q2t,t+l,2,t) be an array of strength t and
t+l constraints. A can be decomposed into 0 repetitions of the

array (2t,t+l,2,t), each repetition of the form D or D‘.

Proof: It follows from the lemma in section 2.1 that each (t+l)—tup1e
differing from the first column in an even number of coordinates must
appear the same number of times, say x, l f x E Q , forming x
arrays of type D° Each of the (t+l)-tuples differing by an odd
number of coordinates will have to appear 0 — x times, forming
Q — x arrays of type D'.

Assume that Q = q2n, q odd (q 3 1). Then any array
A = (Q2t,t+l,2,t) may be extended to one with t+n+l constraints
in the following way. We have shown that the array consists of
q2n component arrays, each of which is type D or D'. We take
an n—tuple of the elements (0,1) and add it to all the columns of a
particular component array. This is done for all the component arrays

n

in such a way that each of the possible 2 n—tuples has been added

to all the columns of q such component arrays.

 

18
We show below that this gives (Q2t,t+n+l,2,t).

For t rows all belonging to the original array A each t-tuple

)

appears 0 times.

If n Z.t it is clear that for a set of t rows, all of which

3

are among the added rows, each t-tuple must appear with the same
frequency 0.

Consider a set of t rows, of which t-m belong to A and
m belong to the added rows. For a t-tuple from these rows, let y

denote the first t—m elements, which are in A and let 2 denote

)

the m elements in the added rows. We note that the (t—m)-tuple

y occurs exactly 2m times in each component array of A and each

)

m-tuple 2 occurs below q2n_m component arrays. Thus the t—tuple

(y,z) occurs 2m X q2n—m times in the extended array.

n
9

It follows from a theorem of Bush [9] that if Q = q2
an array of type (Q2t,t+n+l,2,t+n) can be constructed. However,
our method describes a way of extending any (Q2t,t+l,2,t) to
(Q2t,t+n+l,2,t).

Let A = (024,5,2,h) where Q is odd. If A is the array

consisting of Q repetitions of the array D then A cannot be

)

extended.

Proof: Suppose A is extended to an array A' of six constraints.
The columns of A satisfy the equations nis = (Q—l), ni4 = 0,

: l = _ = ' l
niOCL Then A must have ni5 + ni6 (Q l), ni0 0. But 1n A ,

solving the necessary equations in terms of the dependent variables,

we must have:

l9
niO = (Q24 —1) - 6(023 -1) + 15(022 —1) — 20(02 -1)

+ 15(Q - l) - n15 - SH.

16
: 3Q _ 5 T nis _ Sni6

Thus niO = 0 implies nis + Sni6 = 30 — 5.
The system of equations

n,+n. =Q-l

-5 16
1 c- = _

p15 .,6 3Q 5

has the solution 1116 = 0/2 - l . There is no integer solution if

Q is odd.

CHAPTER III
GROUP ARRAYS

3.1 Relation of Orthogonal Arrays to Finite Projective Geometry

Consider a factorial design for k factors, each occurring at
5 levels, where s = p“, p a prime. The 3 levels may be repre-
sented by the elements of the Galois Field GF(pn). Then each
treatment vector (al,....,a ) may be taken as a point of a finite
projective geometry of dimension (k—l). This geometry will be
denoted by PG(k—1,pn).

In this setting, R. C. Bose, in his definitive paper of 19h?
[5], made a study of the problem of confounding in the blocks of a
factorial design (see Sec. 1.1).

A complete symmetrical factorial design SR is said to be of
m)

the class (SR, 5 if it is partitioned into sm blocks (m f k)

k-m
s

of treatments each. The block size is sr

, where r = k—m.
Bose shows that if mt(r,s) denotes the maximum number of
factors that it is possible to accommodate in a symmetrical factorial

experiment in which each factor is at s = pn levels, and each

block of size sr , so that no estimate of an interaction involving

t or fewer factors is confounded with blocks, then mt(r,s) equals

the maximum number of rows it is possible to take in a matrix of r

columns of elements of GF(pn) so that no t rows are dependent.
Equivalently, mt(r,s) is given by the maximum number of points

it is possible to choose in PG(r-l,s) so that no t are conjoint

(t points are said to be conjoint if they lie in the same t—2 dimen-

sional subspace).
20

21

It was pointed out in Section 1.2 that a block of a complete
factorial design of strength t is an orthogonal array of strength t.
Thus, for those arrays which are blocks of a complete factorial de—
sign, Bose has made the problem of determining the maximum number of
constraints a geometric problem.

The following theorem of Bose and Bush [7] gives explicitly a

method of constructing orthogonal arrays of strength t .

Theorem: Let C be a matrix of k rows and r columns, such that
every t X r sub—matrix is of rank t , with entries from a Galois
Field GF(pn). Then an orthogonal array (sr,k,s,t) may be con-
structed, where s = p“.
Prggf: Let Br be the r X sr matrix whose columns are the sr
different r-tuples of elements of GF(pn). (Br is the complete sr
array). The k x sr matrix A = C x Br is the required array.

If A' is a t x sr sub-matrix of A , and C' is the corres—
ponding sub—matrix of C of rank t ,
each column (al,...,at)i of A' is obtained from sr—t different

columns of B . The array A obtained is of index sth.

3.2 Bounds on the Number of Constraints of Arrays of Strength Four

 

 

of Type C x Br

Following the notation of the previous section, let Br be the
r X sr matrix whose columns are the sr different r-tuples of ele—
ments of GF(s) , where s = pn. Let C be a k x r matrix with

entries from GF(s) , such that every t x r sub-matrix is of rank

t. It follows from the theorems of Bose (Sec. 3.1) that the maximum

22

number of constraints possible in an array (sr,k,s,t) of the form

C x B is equal to the maximum number of points in PG(r—l,s) such
r

that no t are conjoint. This number is denoted by mt(r,s).

When t = 2 all distinct points of PG(r-l,s) can be chosen,

)

so that m2(r,s) = (3r — 1)/(s - 1). As we have indicated (Sec. 1.2)

3
this is the maximum number of constraints possible in any array of
strength 2 and sr columns.

When t = 3, s = 2 m3(r,2) = 2r—1

_, This has been shown by
Bose [5] to be the maximum number of points in PG(r—l,2) such that
no three are colinear. Bose and Bush [7] have also shown this to be
the maximum number of constraints possible in any array of strength 3,

r
and 2 columns, when s = 2.

Bose also proves the following [5]:

n

m3(3,s) = s + 2 when s = 2 3

m3(3,s) = s + 1 when s = pn,p an odd prime;

m3(h,s) = s2 + 1 when s = pn,p. an odd prime.
Seiden [2h] proves m3(h,3) = s2 + l for the case s = 22. Qvist [25]
proves m3(h,s) = s2 + l, s = 2n, n > 1. In particular, 32 + l is

the maximum number of constraints possible in any array when s = 3,
t = 3, N = 34, i.e., (hi, 10, 3, 3) [20].

A bound for m4(r,2), r 3 8, and the values of m4(r,2) for

r h,5,6,7, and 8 are presented in [2b]. We may assume in each case
that the coordinates of the first r points chosen form the rows of
the r x r identity matrix Ir'

(1) In PG(3.2). m4(h.2) = S.

The only point which can be added to I, is (l,l,l,l).

(2) In PG(A,2), m4(5,2) = 6.

 

23

Again, only one point may be added to I5. This point must
have either five coordinates equal to l, or four 1's and one 0.
(3) In PG(5.2). m4(6,2) = 8.

If the point (l,1,l,l,1,l) is added to I6, no more points may
be added. There are essentially two different sets of two points
which may be added:

1 l 1 l 1 0 l l l l 0 0
l l l 0 0 l 1 l 0 0 l l
(h) In PG(6,2), m4(7,2) = 11.

Nine possible sets of four points are exhibited in [21] which
may be added to I7, such that no four are dependent. In each case,
the set of 11 points contains a subset of 8 points lying in the same
5 dimensional subspace.

(S) In PG(r'192); I“ Z 8 m4(r,2) _<_ 3(2r-6 —l) + 8

D

This bound follows from the fact that a S-dimensional subspace

in PG(r—l,2) passes through (2r—6

—1) 6—dimensional subspaces.
To the 8 points in the S-dimensional subspace, 3 points may be
added in each 6—dimensional subspace.
(o) In PG(7,2), m4(8,2) - 17.

The bound in (E) is 17 when r = 8 . Seventeen points have been
found in PG(7,2) such that no four are dependent.

Using a similar method, we can show that the maximum number of
points, no four in a plane, in PG(r—l,3) is at most 3(3r‘4 —1) + 5,

for r 3 6.

Lemma 1: The maximum number of points, no A in a plane, in PG(3,3)

is S.

 

2A
3329f: Any point added to I4 must be a linear combination, with
non-zero coefficients, of the four basis points. Two such points
can differ in at most two coordinates, or be alike in one coordinate;
hence one point may be written as a linear combination of the other
point and two basis points. Then exactly one point may be added.

Therefore, m4(h,3) = 5.

Lemma 2: The maximum number of points, no A in a plane, in PG(h,3)

 

is 11.
Prggf: There are 5 different sets of four basis points among the
points of I5. By the previous lemma, at most one point may be added
for each such set of four basis points. At most one point can be
added with five non—zero coordinates. Two such points can differ in
at most two places, and can be alike in at most two places, which is
impossible. Thus at most 6 points can be added to the basis points.
The following set of 11 points of PG(A,3), with no four in a

plane, is the maximum number which may be found. Therefore,

m4(5,3) = 11.
l 1 I l I I O O O O
I 2 l 2 O O l O O O
1 2 2 O l O O l O O
l l O 2 2 O O O I O
l O 2 I 2 O O O O l
O l 2 2 i

This set of points is unique, up to an interchange of rows or
columns, or multiplication of a column by a non-zero element. Let
us assume that the point with five non—zero coordinates has a 1 in
each place. Assume also that the other points added to I5 , with

four non-zero coordinates, each have a 1 as the leading non-zero

25
coordinate. There must then be two 2's and one 1 among the other
non-zero coordinates. In each PG(3,3), therefore, there is a choice
of three points: (1 2 1 2), (l 2 2 1), or (1 l 2 2). In addition,
any pair of these points chosen must differ in one or two of the places
where both are non—zero. There are then five additional ways of
selecting one point from each PG(3,3). The six sets shown may be

obtained from one another by interchanging columns.

1 2 l 2 O l 2 2 l O 1 2 2 1 O l 1 2 2 O 1 l 2 2 O
1 1 2 O 2 l 2 l O 2 1 1 2 O 2 1 2 2 O l 1 2 l O 2
1 2 O l 2 1 l O 2 2 l 2 O 2 1 l 2 O l 2 l 2 O 2 l
1 O 2 2 1 l O 2 2 1 1 O l 2 2 1 O l 2 2 1 O 2 l 2
O 1 1 2 2 O l 2 l 2 O 1 2 2 1 O 1 2 1 2 O 1 1 2 2

Theorem: The maximum number of points, no four in a plane, in

PG(r-l,3), is at most 3<3r-4 -l) + S, r 2 6.

Proof: Clearly any set of 11 points in a PG(A,3) contains five
points lying in the same PG(3,3). A three-dimensional Space in
PG(r-1,3) is contained in exactly (1/2)(3r-4 —l) four—dimensional
Spaces. Five points may be selected in the three-dimensional space,
and at most six additional points may be selected in each four—

dimensional space. Therefore

miirms 6[(1/2><3r‘4 -1)1 + s.

 

3.3 Structure of Arrays of Type C X Br
The theorem of Bose and Bush in Sec. 3.1 describes a method of
constructing arrays by matrix multiplication. Let us consider the
T-X sr matrix Br used in the construction of the array A =
C3F,k,s,t). The S levels are regarded as members of the Galois
F3€31d. GF(s)

, and the columns of Br are the sr r—tuples of ele-

mernhsof GFb).

26
We may consider the columns of Br as the elements of an r-
dimensional vector space. In particular, the columns form an Abelian
group under coordinate-wise addition(modulo 3). Let A = C x Br
be the array constructed by the method of Bose and Bush. It follows
that, if repeated elements are identified, the columns of A form a

subgroup of B the group of k—tuples of elements of GF(s). In

R)
addition, if A is an array (Sr,k,8,t), k > r, then so is each coset

of A in Bk.

To show that A is a group, consider any two columns hi’hj of

A. By the construction of A (see Sec. 3.1), h1 = Cbi and hj = ij

for two columns bi’ bj of Br' Hence,

h. + h. = Cb. + Cb.
1 J 1 J

= C(bi + bj)
= Cb
m
for some column b in B . Similarly, -h. = —Cb. = C(—b.).
m r l 1 1

Therefore the columns of A form a group.

We will now Show that every coset of A in Bk is also an

array of strength t. Let A' be any t x sr sub-matrix of A.

r—t r r—t

Since A is of index S , the 5 columns of A' contain s

repetitions of each t-tuple of elements of GF(s). A' thus consists

Of Sr-t repetitions of the group Bt'

Let (al,...,ak)' be a k-tuple of Bk which is not in A.

The addition of (al,.. a to each column of A leaves the

k)9

EHVDup Bt in the columns of A' invariant.

‘ )

 

27
It is also clear that if nij is the number of columns in A
having j coincidences with the ith column, then any array which is

a coset of A has the same parameters n i = 1 N

’00.) ,

I .0. n-
10’ ’ 1k’

providing that the transformed columns of the coset remain in the same
order as the original columns of A . For suppose the element ai
of GF(s) is added to each member of the ith row of A. Then only
those columns which had matching elements in the 1th row of A will
have matching elements in the ith row of the new array.

We have thus shown that each array A = (Sr,k,S,t), k_Z r, of

the form C x Br’ constructed from a k X r matrix C, is a subgroup

of Bk which has sk_r —l coset arrays. A and its cosets in turn

form a group of arrays of order Sk_r under the usual definition of

coset operations. If the sr columns of A are distinct, then the

sk—r elements of this group are the blocks of a class (sk,sk-r)

design of strength t.
We will now show that in any array of the form C x Br , the
number of times each column is repeated depends on the rank of the

matrix C.

If C is of rank v v E r, each column which appears

3

in A is repeated exactly Sr—v times.

Suppose the first v rows of C are linearly independent.
Without loss of generality assume the 1th row of C consists of the

Vector with l in the ith place and 0's elsewhere, i = 1 2 v.

3 3")

T1hen the first v rows of A are identical with the first v rows

, the group of sr column vectors. Hence

Of‘ the matrix formed by Br

 

28

each column v—tuple is repeated sf—V times. Each succeeding row of
A is a linear combination of the first v rows; therefore columns
will be identical if and only if they have matching elements in the
first v rows.
It follows from this proof that the array A = C X Br will
have Sr distinct columns if and only if C is of rank r. If A
is to be of strength t, then the rank of C must be at least t.
We have shown previously that if A is an array of the form
C x Br’ the columns of A form a group, if repeated columns are
identified. The theorem which follows characterizes a larger class
of arrays whose columns form groups, with identification of repeated

columns. Conditions will then be given under which arrays of this

class are of the form C x Br'

Theorem: Let A = (N,k,s,t) be an array with exactly Sr distinct
columns, srlf N. Then, with identification of repeated columns,
the columns of A form a group if and only if A is a matrix of

rank r.

2329f: Let A be of rank r. A set of r linearly independent
columns may be selected, and every other column of the array must be
a linear combination of the r linearly independent columns. Since
A contains sr distinct columns, it must contain all linear combina—
tions of the r independent columns. Then the columns of A form
the group generated by the r linearly independent columns.

Suppose A is a group, and let the rank of A be v. A set
Of v linearly independent columns may be chosen, and every other

COlumn must be a linear combination of the v linearly independent

29
columns. Furthermore, since A is a group, it must contain every
linear combination of the v independent columns, therefore the
r v

number of distinct columns is SV. It follows that s = s , and

since 5 2,2, r = v.
If A is of rank r , then r rows, say the first r , are

linearly independent, and the elements of the last k-r rows are

linear combinations of the elements of the first r rows. Thus

if A has sr distinct columns, there are sr distinct columns

in the first r rows. It follows that the first r rows must con-

sist of the group Br , with possible repetition of columns. We

will now Show that if each column of A is repeated sV times, then

A is of the form C x Bm for some m 3,r.

m

Suppose A is of rank r , with N = S , m 3 r and each column

3
is repeated the same number of times, say sV , where v = m—r. It
has been shown that r rows of A , say the first r , consist of
the group Br . Since each column of A is repeated sv times, it
follows that in the first r rows of A , each column of Br is
repeated sV times. The first r rows of A then consist of r
rows of the matrix formed by the column group Bm' 'We now show that
the array A is of the form C X Bm’ where C is a k x m matrix.
Let the first r rows of the matrix C consist of the unit

vectors with l in the 1th place and 0 elsewhere, i = l,.. r.

' 3
The last k—r rows of the array are linear combinations of the first

r rows. Let ( ), j = r+l,...,k, be the coefficients of

aji""’ajr
these linear combinations. Then the last k—r rows of C may have

(a. ... . ) as the first r elements and 0's elsewhere.
J1) ) Jr 5

30
The first r rows of A may be written as the product of the
first r rows of C with the matrix Bm' Let (aj1"" a. 0 ..,0)
be one of the remaining k—r rows of C. The aji are the coef-
ficients of the appropriate linear combination of the first r rows

which yields the jth row of A, j = r+l,... k.

3
We will demonstrate in Chapter IV that there exist arrays
(2r,k,2,t), k > r, containing 2r distinct columns, which are neither

subgroups of B nor cosets of subgroups. Thus they cannot be de-

k

rived from construction of the form C x Br' A method of construction

is described which yields such arrays, and examples will be given.

 

3.h Confounding in Arrays of the Form C x Br

In any array A = (2r,k,2,t) of the form C X Br’ the pattern
of confounding may immediately be determined by the structure of the
matrix C used to generate the array.

We will assume the rank of C is r. We may take as the first
r rows of C the identity matrix Ir' The array constructed will
then be a complete 2r factorial design for the first r factors

Fl,...,Fr. Let the last k—r rows of C correspond to the factors

F ,...,F . Among these k—r rows the structure of the ith row
r+1 k ’

indicates the interaction with which the estimate of the ith effect

is confounded, for i = r+l,... R.

J

Let (cl,...,c ), c. = 0 or 1, be one of the k-r rows added to
r 1
Ir to form C. Then the estimate of the effect corresponding to
(C1"°°’Cr) is confounded with the estimate of the interaction of
those factors Fi for which ci = l, in (C1"'°’Cr)' Then, using

"identities” derived from the confounding with respect to factors

T+1"°°’Fk’ all other confounding in the array may be determined.

31

For example, if the (r+1)th row of C is of the form (l,l,l,l,
0,0,...,O), the estimate of the effect of Fr+1 is confounded with
the estimate of the interaction of F1,F2,F3,F4, denoted as l23h, if
such an interaction should be present. The "identity" in this case
is expressed as r+1 = i l23h, or I = i 123h(r+1). The method follows
that of Box and Hunter [8].

The parity of the confounding may be determined as follows: if
the row of C corresponding to Fi has an even number of 1's,
the confounding is negative; if the row has an odd number of 1's,
the confounding is positive. (See Sec. l.h.)

An example may be given for the case of the array A = (128,ll,2,h)
constructed with a matrix C taken from [21]. Let C be the follow-
ing matrix:

F 17 T
l l l l l l O

l l l l O O 1

l l O O l l 1

 

 

O 1 O l O 1 1_J

L.

The identities derived from the last four rows of C are

I = — 123h568
I = 123A79

I = 12567 10
I = — 2A6? 11.

These identities may now be combined, using the order two

prOperty xx I, so that, for example, (123b79)(l2567 10) = 3hS69 10.

This yields the additional identities

I

I

56789
3A78 10

'1378 ll

3&569 10
1369 ll

INS 1O 11

32

From these identities, we can determine

confounded.

For example, from
1
12

125

I

= 12567 10
2567 10
567 10

67 10,

etc.

1289 10
2L589 11
2368 10 11

23579 10 11
116789 10 11

which interactions are

it follows that

D

It is easily seen that since each identity contains at least

five factors, no main effect is confounded with any interaction of

three of fewer factors, and no interactions of two factors are confounded

with one another.

described in Sec. 1.2.

This is the property of arrays of strength A, as

CHAPTER IV

ARRAYS or 32, AB, 6t and 80 COLUMNS, s = 2, t = A

A.l Arrays of 32 Columns, 3 = 2, t = h

 

Theorem: The maximum number of constraints for an array (32, k, 2, A)

is six.

Proof: Consider the equations whose solution is necessary for the

 

existence of an array with 7 constraints (see Sec. 1.3). Solving

them in terms of the dependent variables yields

1110 = 3 - ni5 - 5ni6 - 15 ni7

ni3 = —35 + 10 nis + NO ni6 + 105 ni7
According to the first equation, ni6 = ni7 = 0 , and His-5 3. There
is then no non-negative solution for ni3 , and thus an array of 7

constraints cannot exist.

Using the following method, two different arrays (32, 6, 2, A)
may be constructed. We may assume that the first column must consist
entirely of 0's. Let the first five rows consist of two arrays
(16, 5, 2, h) of the form D or D', as described in Section 2.2.
The columns of D are made up of all five-tuples with an odd number
Of 0's, and the columns of D' are made up of all five—tuples with

an even number of 0's. A row of 0's may be added to one array D ,

and a row of 1's to the other array. The two arrays constructed are:

(1) (2)

33

3A

The number 1 below a D or D' indicates that a row of sixteen
i's is to be added to the five—rowed array.
Array (1) has solution

nlo = 0: r111 = 5; n12 = 5: n13 = 10: “14 = 10; n15 = 1: n16 = 0:
Array (2) has solution
) n12 = 15: n13 = on n14 = 15: n15 = 0: n16 = 0-

nlo = 1: nll = 0

These are the only solutions possible to the necessary equations for

an array (32, 6, 2, A).

A.2 Arrays of A8 Columns, 5 = 2, t = A

 

Theorem: The maximum number of constraints for an array (A8, k, 2, A)

is five.

Proof: The necessary equations of Section 1.3 may be solved in terms

 

of the dependent variables for the case k = 6. We then have
“10 2 h ‘ Snio ’ “15'

Any solution must have ni6 = 0 for all i . It follows that if an
array of six constraints exists, all columns are distinct.

Consider the complete array (26, 6, 2, A) consisting of all 26
distinct 6—tuples. In any four rows, each A—tuple appears exactly
four times. If A8 distinct columns can be chosen to form an array of
index 3, then in any four rows of the remaining 16 columns, each A—tuple
must appear exactly once. This would yield an array of 16 columns
with k = 6 , contradicting the fact that an array (16, k, 2, A) can
have at most five constraints [9].

It follows from the theorem of section 2.2 that every array

(A8, 5, 2, A) is composed of three arrays of the form D or D’.

35

A.3 Arrays of 6A Columns, s = 2,7t = A

 

We will prove in this section that the maximum number of constraints
for an array (6A, k, 2, A) is eight.

When k = 7 no solution to the necessary equations exists with

J

n. > 0. It follows that n

17 i7 = 0 for all k greater than 7, by

Property 3 of section 1.3. The following table gives all solutions

which must be considered for k = 6, 7, 8 and 9

Solutions for k = 6, 7, 8, 9; N = 6A.

T1. 1'1. n II n. 1'1. n. 1'1 n I]

 

fiiifififififlfifi
6-1: 0 10 10 2o 20 2 1

6-2: 1 5 2o 10 25 1 1

6-3: 2 o 30 o 30 o l

6-A: o 11 5 3o 10 7 o

6-5: 1 15 2o 15 6 o

6-6: 2 1 25 10 2o 5 0

7-1: 0 A 15 5 3o 6 3 o

7-2: 1 0 2o 5 25 10 2 o

7-3: 0 5 10 15 2o 11 2 o

7-A: o 6 5 25 10 16 1 o

7—5: 1 1 15 15 15 15 1 o

7-6: 0 7 o 35 o 21 o o

7-7: 1 2 lo 25 5 2o 0 o

8-1: 0 2 9 12 15 18 7 o 0

8-2: 0 1 1A 2 25 13 8 o o

8—3: 0 3 A 22 5 23 6 O 0

9-1: 0 o 9 6 l8 9 21 o o o
9-2: 0 1 A 16 8 1A 20 o ‘ o o

36

Theorem: Every array (6A, 8, 2, A) has solution 8-1.
nggfz We assume the first column of an array consists entirely of 0's.

Solution 8—2 has ni1 = l . Let i = 1. Suppose the single 0
in this column is coincident with a 0 in any of the columns with two
0's. This would result in two columns with seven coincidences, contra—
dicting the fact that if k = 8, ni7 = 0. Thus the single 0 in the
column with one 0 cannot be coincident with a 0 in any column with
two 0's. The array then has a sub—array of seven rows with n10 = l,
nll = 0. This sub-array would have solution 7-2 with respect to the
first column, with 1112 = 20 . 0f the columns with two 0's in the
sub-array, six would have to have 0's added in the extension. But
in solution 8-2, nis = 2. Because of this contradiction, no array
can exist with solution 8-2.

Suppose an array exists with solution 8-3. This solution has
1111 = 3, and the columns having one coincidence with the 1th column
must be distinct. Thus the array would contain a sub—array of seven
rows with nio = l, nil 3 2. The only such solution is 7-7 with
niO = l, nil = 2. But in 8-3, ni5 + ni6 + 1117 + n18 = 29. In any
seven—rowed sub-array, these columns have four or more coincidences
with the 1th column. However, in 7-7 , n. + n. + n. + n. = 25,

14 15 16 17

Hence an array with solution 7—7 cannot be extended to an array with
solution 8-3. Because of this contradiction, no array can exist with
solution 8—3.

This leaves 8—1 as the only solution for an array of eight

constraints.

37
Theorem: The maximum number of constraints for an array (6A, k, 2, A)

is eight.

Proof: We first prove that solution 9—2 cannot correSpond to an

 

array. Such an array would have one column having one coincidence
with the 1th column, since nil = 1. It would then contain a sub-
array of eight constraints with nio 2 1. No such array exists.

An array with solution 8—1 cannot be extended to antarray with
solution 9-1. Consider the solutions with respect to the first column
of all 0's. Solution 8—1 has nil = 2. These two columns with one
0 have six coincidences. Since solution 9—1 has ni1 = 0, each
of the two columns must have a O in the ninth row. The two columns

would then have seven coincidences, contradicting the fact that

n. = 0 for all i.
17

Theorem: Arrays (6A, k, 2, A) of seven constraints with solutions

7-1, 7-2, 7-A, 7-6, and 7—7 cannot be extended to eight constraints.

Proof: We consider the solutions with respect to the first column of 0's.
(1) Suppose an array has solution 7—1. Since ni6 = 3, we may

assume there are four columns as in (a).

A
D)
V
A
C“
v

OOOOOOO
HOOOOOO
OHOOOOO
OOI—‘OOOO

38
Suppose one of the last three rows of (a) is deleted. In each case
the remaining six rows have n16 = l and n15 = 2, and hence must form
an array of six constraints with solution 6-1.
The array of seven constraints with solution 7—1 must now have

since n. = 6.

six columns consisting of five 0's and two 1's , 15

However, deleting one of the last three rows must leave each of these
columns with only four 0's. Therefore, in the last three rows, these
six columns have only 0'3 , as in (b).

Suppose the array is extended to eight rows. Four of the columns
in (b) must coincide with the first column in the eighth row, since
solution 8-1 has ni6 = 7. We would then have the A-tuple (O O O 0)
appearing five times in the last four rows. Thus the extension is
impossible.

(ii) Suppose an array with solution 7—2 is extended to eight

rows. According to 7—2 , the extension must have nio + ni1 = 1
Since the unique solution for k = 8 has nio + 1111 = 2 , this is
impossible.

(iii) Consider an array with solution 7—A. The array must have
six columns with exactly one 0 . If an eighth row is added, these
as in (c).

columns will be followed by two 1's and four 0's ,

(c) (d)
011111 11111
101111 11111
110111 -----
111011 -----
111101 -----
111110 -----
111111 -----
110000 -----

39

The eight-rowed array must now have five more columns with exactly
two 0's . All of these columns must have 1's in the first two rows
as in (d); otherwise, there would be a column having seven coincidences
with at least one of the first two columns.

If any one of rows 3 through 8 is deleted, the remaining
seven-rowed array would have nlo = 0 , and hence n11 2 5. This
implies that if any one of rows 3 through 6 is deleted, then at
least two of the columns of (d) must have only one 0 in the remain—
ing rows, while if row 7 is deleted, at least three of the columns
of (d) must have only one 0 in the remaining rows. Therefore the
five columns of (d), with two 0's in each column, must have at least
(A)(2) + 3 = 11 0'3 . This is clearly a contradiction.

(iv) An array with solution 7—6 can be extended only to an
array of eight conStraints with ni5 + ni6 = 21. Solution 8—1 has
nis + ni6 = 25.

(v) Suppose an array with solution 7—7 is extended to eight
rows. Solution 7—7 has n. = l, n. = 2. Let i = l. The column

10 11

with no 0 and one of the columns with one 0 must both have a O

) J

in the eighth row. This would result in two columns of the eight—rowed

array having seven coincidences, while solution 8—1 has ni7 = 0.

Construction of Arrays with Seven and Eight Constraints

 

An array (6A, 8, 2, A) of the form C x B6 may be constructed
by the method of matrix multiplication, as described in section 3.1.
To form the rows of the matrix C, there are essentially two dif-

ferent sets of eight points which may be chosen in PG(5,2) such that

A0
no four are conjoint. We may assume in each case that the first six
rows of C form the 6 X 6 identity matrix Is. The matrices C

which result are:

— ‘1

I6
c1: 111100
110011
L __

r 16
C2: 111110
111001

 

 

In addition, the following set of seven points may be chosen,
which cannot be extended to eight points:
16

03: 111111

The array C3 X B6 of seven constraints, has solution 7—6 ,

5
and thus cannot be extended to eight constraints by any method.

If a seven-rowed matrix C is used which consists of 16 and
a row with four non-zero coordinates, for example the first seven

rows of C1 the array formed will have solution 7-3. If the seventh

9
row has five non—zero coordinates, as in the first seven rows of C2,
the array will have solution 7—5.

We may also construct arrays of seven constraints by the method
described in section 2.2. Since 0 = 22 , any array of five con-
straints can be extended by this method to seven constraints.

Any array (6A, 5, 2, A) is composed of four arrays of the form D
or D' . It may be extended by adding one of the pairs (0 0), (0 l),
(l 0), (l l) to the columns of one D or D’ the same pair being

9

added to all the columns of a single D or D'.

A1

We may assume that in each array constructed by this method, there
is a five—rowed array of the form D followed by (0 0), so that the
seven—rowed array has a column of all 0’s. Using all possible
arrangements of the remaining five-rowed component arrays, we may con—
struct six different arrays by this method. These six arrays are dis-
played below, where

D
i
j
indicates that the pair (i j) is to be added to all the columns of

the array D (or D').

 

 

(l) [D D D D l
0 0 l 1 Solution 7-3
L0 1 0 1 g

(2) 7D D D D7
0 0 l 1 Solution 7—2
0 l 0 l

(3) TD D D' D I
0 0 l 1 Solution 7—A
0 1 0 1
_ .1

(A) _D D’ D D'—
0 0 l 1 Solution 7-5
0 l 0 1 _

(5) 7D D' D' D I
O O l 1 Solution 7—6
0 l 0 1 .

 

(6) TD D' D' D"
0 0 l 1 Solution 7—7

 

 

This method thus yields seven—rowed arrays with each possible
solution except 7—1. An array with solution 7-1 may be constructed

in the following form.

A2

(7) The first 32 columns consist of

D D
0 l
l 0
while the last 32 columns are:
(i) (ii)

0 O O O l 1 l 1 O O O O l l 1 1 O O O O l 1 1 l O O O O l l l l
O O 1 1 O O 1 1 O O l l O O 1 1 O O 1 1 O O l 1 O O 1 l O O l 1
O 1 O l O l O l O 1 O l O l O l O l O l O 1 O 1 O l O l O 1 O l
O l 1 O 1 O O l O l l O 1 O O l 1 O O 1 O l l O l O O l O l l O
O O O O O O O O l 1 l 1 l 1 l l 1 1 1 l 1 l 1 1 O O O O O O O O
O O O O O O O O O O O O O O O O l l l l l 1 1 l l l 1 l l l l l

O O O O O O O O O O O O O O O O 1 l l 1 l l 1 1 l 1 l l 1 l l 1

One can easily verify that (7) is an orthogonal array of strength A.
We note first that rows 1 through 5 form a five—rowed array of
type D D D D'. We must now show that if we take either (a) two of
the first five rows, together with rows 6 and 7, or (b) three of
the first five rows together with either row 6 or row 7, each A—tuple
appears four times.

Consider (a). In any two rows of D , each possible pair of the
elements 0,1 appears four times. Thus in the first 32 columns of
array (7), each A—tuple ending in (O l) or (1 0) appears four times.

In the last 32 columns, the 16 columns of (i) end in (0 0), while
the 16 columns of (ii) end in (l 1). It is now sufficient to check
that in any two of the first five rows, each possible pair appears

four times in (i) and four times in (ii). It should be noted that rows

A3

1, 2, and 3 of (i) and (ii) are exactly alike, while the remaining
four rows are the same except for an interchange of 0 and 1.
Next consider (b). In the first 32 columns, rows 1 through

5 , together with either row 6 or row 7 clearly form an array

)
(32, 6, 2, A). It remains to be shown that the same property is true
for the last 32 columns. It is therefore sufficient to check that

in any three of the first five rows, each possible 3—tuple appears
twice in (i) and twice in (ii).

Two of the seven-rowed arrays shown above, arrays (A) and (5),
with solutions 7—5 and 7-6 , are actually arrays of strength five.
Using the method of the theorem of section 2.1, they can be constructed
from arrays of the form (32, 6, 2, A). We may choose one of the arrays
(32, 6, 2, A) displayed in section A.l, adjoin the same array with 0

and l interchanged, and add a seventh row of 0's and 1's as in-

9
dicated in section 2.1. By this method, array (1) of section A.l

will yield the array (A) shown above, and array (2) of section A.l will
yield (5). It follows also, from the same theorem of section 2.1,

that the maximum number of constraints for an array (6A, k, 2, 5) is
seven.

We will now examine the algebraic properties of the seven—rowed
arrays constructed, considering 0 and l as members of the Galois
Field GF(2).

First consider the five—rowed arrays D and D'. D consists of
all columns with an odd number of 0's and an even number of 173;

the columns of D9 are those with an even number of 015 and an odd

number of 1's. We thus have the following property: using coordinate

AA
addition (modulo 2), a column of D added to a column of D' yields

a column of D' while the sum of two columns both from either D or

3
D' , is a column of D. Using this property, it is easily seen that

the columns of arrays (l), (A) and (5) have closure, and thus form

)

subgroups of B7 the group of all possible seven-tuples of the ele-

D

ments 0 l.

3

Using the same property, it can also be shown that the columns of
arrays (2), (3), (6), and (7) do not have closure. In each of these
arrays, consider the two component arrays D or D' which are followed
by (0 l) and (l 0). The sum of two columns, one ending in (0 l) and
one ending in (l 0), will clearly be a column ending in (l 1). To have
closure, arrays (2) and (6) would have to have an array D followed
by (l 1), while array (3) would have to have D' followed by (l 1).
These requirements are not net. In array (7), we note that part (i)
contains columns of the D' type followed by (0 0). The sum of such
a column, and any column chosen from the first 32 columns of the
array, will not be a column of the array.

Since each of the arrays constructed contains the identity column,
arrays (2), (3), (6) and (7) are neither groups, nor cosets of groups,
and thus cannot be derived from the method of construction discussed
in Chapter III, using matrix multiplication. These four arrays have
solutions 7-2, 7-A, 7-7, and 7-1 respectively, hence none of them can
be extended to eight rows.

In section 3.3 it was proved that an array with sr distinct
columns forms a group if and only if the array is a matrix of rank r.

It can easily be shown that the four arrays discussed in the previous

A5
r = 6.

paragraph form matrices of rank seven, while for N = 6A,

Arrays (2), (3) and (6) contain the five columns:

1 O O O O
O l O O O
O O l O O
O O O l O
O O O O 1
O O O O O
O O O O O

In addition, (2) contains (0 O O 0 0 1 0) and (0 O 0 O O O l); (3)
contains (0 0 0 0 O l l) and (0 0 0 0 O 0 l); and (6) contains
(0 0 0 0 l l 0) and (0 0 0 0 l O 1). In (7) we may choose the

following set of independent columns:

1 O O O O O O
O l O O O O O
O O 1 O O O O
O O O l O O O
O O O O l O O
O O O O O l O
1 l 1 1 1 O 1

The group generated by a set of seven indepndent columns contains
27 distinct columns, while the arrays have only 26 columns, indicat-

ing once again that these arrays cannot form groups.

A.A Arrays of 80 Columns, 3 = 2 t = A

_I
In this section it will be proved that the maximum number of
constraints for an array (80, k, 2, A) is six.
The solutions to the necessary equations for an array with N = 80,

for k = 5 and k = 6 are given in the table on the next page.

9

It will first be shown that only two of the arrays with five

constraints can be extended to arrays with six constraints.

 

Solutions for N = 80, k = 5, k = 6
5—1: 0 25 O 50 O A
5-2: 1 20 10 A0 5 3
5-3: 2 15 20 30 10 2
5-A; 3 10 30 20‘ 15 1
5-5: A 5 A0 10 20 0
6-1: 0 12 15 20 30 0 2
6-23 0 13 10 30 20 5 1
6-3: 1 8 20 20 25 A l
6—A: 2 3 30 10 30 3 1
6-5: 0 1A 5 A0 10 10 0
6-6: 1 9 15 30 15 9 0
6-7: 2 A 25 2O 2O 8 O

Lemma 1: The arrays with solutions 5—1, 5—2, and 5-5 cannot be

extended to six-rowed arrays.

2322f: There is a unique array with solution 5—1, i = l,...,5. Since
solutions 5-2 and 5—5 represent the same array up to a permutation
of the elements (0,1), it is sufficient to consider either 5—1 and
5-2, or 5-1 and 5—5.

Any array of six rows obtained by extending 5—1 would have to
have nio = 0, nis + ni6 = A. No such solution exists.

Consider an array admitting solution 5—5 with respect to a
first column of all 0V3. If an array with solution 5-5 could be

extended to an array of six rows, the six—rowed array would have to

have nl6 = 0. Solving the necessary equations in terms of the dependent

A7
variables then yields
nll = —36 + 5 his, which implies n15 3 8
(i) n15 = 8 implies nlo = 2, nll = A
(ii) n15 = 9 implies nlo = l, n11 = 9
(iii) n15 = 10 implies n10 = O, nll = 1A.

But any extension of an array with solution 5—5 must have
1110 + 1111 f 9. Then (i) is the only possibility, with complete solution
nlo : 2; n11 = A: n12 = 25: “is = 20, n14 = 20: n15 = 8; n16 = 0-

An array of type 5—5 has four columns of all 1's one column

J
of each type with one 0 , and four columns of each type with four 0's.
The first 5 rows of the following matrix are part of such an array,

and the sixth row is the extension, if an extension is possible.

1 l 1 l O l l 1 1 O O O O

H

1 1x1 1 O l l l O O O O

1...

l l 1 l l O l l O O O O

p...

l l 1 l l 1 O l O O O O

H

l 1 1 1 l 1 1 O l l l 1

 

l l 0 0 0 0 0 1 l l l l 0
The elements added to the first nine columns are determined by
the solution 1110 = 2, nll = A, for the extension. Then if the fifth
row is deleted, a five-rowed array remains with n10 = 3, which can
only be of type 5-A. In 5—A, each column with four 0's is repeated
three times, and n15 = 1. Therefore the last four columns above must

have three 1's and one 0 added.

A8

Now suppose the fourth row is deleted. Again the same array with
solution 5—A is obtained, and should have each column with three 0's
repeated twice. Since (0 0 0 l 1) appears three times in this sub-
array, this leads to a contradiction. Hence the extension is not an
array. Since array 5-5 cannot be extended, neither can array 5-2.

Note that solutions 5-3 and 5—A represent the same array with
0 and l interchanged. We have shown that arrays with these solu—

tions are the only ones which can be sub—arrays of a six-rowed array.
Lemma 2: Solutions 6—A and 6-5 do not correspond to arrays.

Proof: Consider an array having solution 6-A with respect to a first
column of 0's. Since ni6 = l and ni5 = 3, there must be another

column of all 0's and three columns with five 0's and one 1.

)
It follows from lemma 1 that the columns with five 0's must be
distinct, since no five—rowed sub-array may have more than three

columns which are all 0's. Thus the array would have the following

columns:

000000
000000
OOOOOH
OOOOHO
OOOHOO

To complete the requirement that the four—tuple (0 0 O 0) appear
five times in each four-rowed sub-array, the columns (0 0 O 0 l l) and
(O O 0 l 0 1) must each appear three times. However, the four—tuple

(O O O l ) would then appear six times in rows 1, 2, 3, 6.

A9

Suppose an array has solution 6—5. With nis = 10 , it must

have a sub—array with solution 5—A. Consequently, it would be neces—

sary that ni0 + nil be less than or equal to 13, but 6—5 has

nil = 1A.

Construction of Arrays (80, 6, 2, A)

 

The construction of an array with solution 6—1 will now be
described, and it will be shown that the construction of an array having
solution 6-1 with respect to a first column of 0's is unique.
Further, it will be shown that this array admits each of the remaining
solutions with respect to some column.

An array having solution 6—1 with respect to the first column
of 0's may be constructed as follows.

a) There are three columns with six 073 (1116 = 2).

b) The four-tuples of 0‘s must be completed by the columns with
four 0's; hence each possible column with four 0's appears twice
(mm = 30).

c) Each four—tuple consisting of three 0's and one 1 appears
in two distinct columns with four 095 , and each of these distinct
columns appears twice. For example, (0 0 0 l) in rows 1, 2, 3, A
appears in (O O O l l O) and (O O O l O 1). To complete the four—

each type of column with

tuples consisting of three 0's and one 1 ,

three 0‘s must appear once (n13 = 20).
d) Each four—tuple consisting of two 0's and two 1's appears
in one type of column with four 0's (repeated twice) and in two

distinct columns with three 0's , so it must appear once more. For

50
example, (0 0 l l) in rows 1, 2, 3, A appears in (0 0 l 1 0 0),
(O O l l l O), and (O O l 1 O 1). Hence, each type of column with
two 0's and four 1's must appear once to complete the four-tuples
with two 0's and two 1's (n12 = 15).

e) Each of the four—tuples with three 1's and one 0 appears
in one of the columns with three 0's , and two of the columns with
two 0's. For example, (0 l l l) in rows 1, 2, 3, A appears in
(0 l l l 0 0), (0 l l l 0 l), and (0 l l l l 0). Then each type of
column with one 0 must appear twice to complete the four-tuples with
three 1's and one 0 (n11 = 12).

f) The four-tuple consisting of four 1's appears in two distinct
columns with one 0 , each repeated twice, and in one column with two
0's . Thus the array is complete (nlo = 0).

It can now be shown that the array just constructed also has
solutions 6-2, 6-3, 6-6, and 6-7 with respect to different columns.
Let a column with one 0 , say (0 1 l 1 l 1), be the ith column.
This column is repeated twice; hence ni6 = 1. Since no column with
five 0's and one 1 appears, nio = 0, and the solution must be 6-2.

Suppose a column with four 0's and two 1's , say (0 0 0 0 l l),
is the 1th column, so that ni6 = 1. Since (1 1 1 l 0 0) appears

once, nio = l and the solution is 6-3.

th

Let a column with three 0's , say (0 0 0 l l 1), be the 1

column. Since each column with three 0's appears once, the solution

has n. = 0, n. = 1. This solution must be 6-6.
16 10

If (1 l 1 l 0 0) is the ith column, the array has 1116 = 0,
nio = 2, since columns with two 0's appear once, and columns with

four 0's appear twice. The solution is therefore 6-7.

51
We will now prove that an array (80, k, 2, A) with k = 7 does
not exist. It will first be shown that an array of Six constraints
having solution 6-1 with respect to some column cannot be extended
to seven constraints. We then show that every six—rowed array has

solution 6—1 with respect to some column.

Theorem: The maximum number of constraints for an array (80, k, 2, A)

is six.

Lemma 3: An array admitting solution 6—1 with reSpect to.some

column cannot be extended to seven rows.

Proof: A seven—rowed extension of an array with solution 6—1 must

 

have n. +

16 ni7 = 2. There are only two solutions to the necessary

equations which might correspond to such an extension.

nio “ii “i2 “is “i4 “is “is “iv
7-1: 0 A 23 0 A0 10 1
7-2: 0 8 A 35 10 20 2 0

First consider 7—1. An array with solution 7—1 could be constructed
only by extending an array with solution 6—1. But an array with solu—
tion 7-1 must have a six-rowed sub-array with ni0 > 0. This is a
contradiction; hence no array can exist with solution 7—1.

An array with solution 7—2 has n.1,O = 0, ni1 = 8. Therefore

it could not be an extension of an array with solution 6—7, since 6-7

has nio + nil = 6. Moreover, Since ni1 = 8 , the array with solution

7-2 would have to have at least two of the columns having one coinci-

dence with the ith column alike. Crossing out the row including

52
these coincidences would leave six rows with nio > 1. Hence the
array could not be an extension of any of the remaining six-rowed
arrays.
Since neither of the possible extensions of an array with solu-

tion 6-1 exists, the array cannot be extended.

Lemma A: An array (80, 6, 2, A) must have solution 6—1 for some

value of i.

 

Proof: Solution 6-1 is the only solution with n£6 = 2. We will
show that any array (80, 6, 2, A) must have some column repeated three
times. The array must then have solution 6-1 with respect to this
column.

An array with solution 6-2 must have one of the columns having
one coincidence with the 1th column repeated three times.

Solutions 6—3, 6-6, and 6—7 will be considered with i = 1,
assuming the first column to be all 0's.

Solution 6-3 has nis = A. It follows from lemma 1 that the

columns with five 0's must be distinct. Therefore an array with

this solution must have six columns as follows:

0 O 1 O O O
O O O 1 O O
O O O O l O
O O O O O 1
O O O O O O

O O O O O O

53

Then the column (0 0 0 0 l 1) must appear three times.

An array with solution 6—7

tion 6—3,

with O

and l

is the same as an array with solu-

interchanged.

An array with solution 6—6 must have columns as follows:

O 1 1 O O O O O

O O O l 1 O O O

O O O O O l 1 O

O O O O O O O 1

O O O O O O O O

O O O O O O O O

Consider the first 10 columns

leaves a five-rowed array with

with five 0's ,

coordinates must
0's

three must

(1 l O O 0) must

O O

O O

O O

O O

shown.

1115 = 2.

l l 1

l l l

1 1 l

O O O

O O O

O O O

Deleting the first row

Since there are three columns

and Since columns differing in an even number of

appear the same number of times, each column with

appear three time

appear three times in the last five rows.

it must be preceded each time by a

S.

1

In particular, the column

Further,

in the first row, since the

four-tuple (0 0 0 0) already appears in rows 1, A, 5 and 6 five times.

Proof of Theorem:

 

Lemmas 3 and A together prove the theorem.

CHAPTER V

RELATION OF FACTORIAL DESIGN TO INFORMATION THEORY

This chapter will briefly describe the relation between the con—
struction of orthogonal arrays by the method of matrix multiplication
(described in section 3.1) and the construction of t—error correcting
codes.

A signalling alphabet A(k,v,s) is a set of v distinct k-place

 

sequences of members of a set of 3 elements. A(k,v,s) is a subset

of Bk , the set of all sk possible sequences of k elements. An

encoder E(k,v) is a 1-1 correspondence between a set of v distinct
messages and the v sequences of A(k,v,s). A message is transmitted
by presenting the k elements of the corresponding sequence in suc—

cession. The output is some member of Bk'

A decoder D(k,v) is a 1—1 correspondence between the members

al,.. a of A(k,v,s) and v disjoint subsets of B which

a .

3

form a partition SO, Sl"'”"Sv—1 of Bk' If an element bi in Si

is received as output, it is read as ai. E(k,v) and D(k,v) together

form a kjplace s-ary code.
Let s = p“, p a prime. Then the elements of Bk may be re-
garded as the group of vectors with coordinates from GF(s).

For each sequence b in Bk let w(b) be the number of non-

zero coordinates in b. The Hamming distance [13] between two sequences

 

b1, b2 is defined to be
d(bl, b2) = w(hl - b2).

Hamming distance clearly satisfies all the properties of a metric.

5A

55
Suppose ai is an element of A(k,v,s) transmitted, and bi is

the element of Bk received. Then

is called the noise vector. The number of errors in transmission is

 

then

w(ei) = d(ai, bi)'

 

The code is said to be t—error—correcting if bi is contained

the set corresponding to ai whenever w(ei) f t, for

3 3

,...,v-l. This implies that the received sequence is correctly

interpreted when there have been t or fewer errors of transmission.

Group Codes

 

I‘
9

I“

Let v = s and let A(k,v,s) be a subgroup of order s of

Bk' Assume a0 = (0 0 0...0). A decoder may be constructed as follows:

let the group B be partitioned into the 8m cosets of A(k,v,s),

k

where m = k - r. In the jth coset, choose an element bj with the
t

property that w(bj) f w(b) for all b in the j h coset, and call

bj the coset leader. In particular, bO = a0. Now let Sj be the

set

The v-l sets Sj form the required partition of Bk'

The code obtained is called a (k,r) s—ary group code. This class

 

of codes was first considered by Slepian [22] for the binary case, and
by Bose [6] for the s—ary case. The scheme described may be displayed

as follows:

56

 

Alphabet: a0 a1 — — - - — aV l
/ _
bl (bi + 511) - - - — — (bl + av-l)
Coset b2 (b2 + a1) _ _ _ _ _ 032 + aV—l)
leaders <
\b.-. (b.-. + .1)- — — — — (13,,le
1 1 i
<5.) <5.) — - — — — (SW)

The transmitted message is correctly received if and only if the
error vector is a coset leader. Thus the code is t—error-correcting
if and only if for each b in Bk , w(b) f t implies b is a coset
leader.

Bose proves that a (k,r) s-ary group code is t—error-correcting
if and only if w(a) 3 2t + l for every a in A(k,v,s) , except a0.
This was first proved by Hamming for the binary case. Finding a t—error-
correcting (k,r) s-ary group code is thus equivalent to finding a
subgroup Br of B of order Sr

, such that each element of Br

k 3
has weight at least 2t + l. Naturally it is of interest to maximize

I‘.

Relation of Group Codes and Orthogonal Arrays

 

Let C be a k X r matrix of rank r with entries from GF(s),

3

r‘f k. Suppose C has property P that any d x r submatrix of C

d

is of rank d d: r. It was shown in section 3.1 that C generates

3

an array A = (Sr,k,8,d).

57

Without loss of generality, let C be the matrix

I
r

M
where Ir is the r X r identity matrix, and M is the (k—r) x r
matrix of rows added to Ir which satisfy the property Pd stated

above.

Consider a sequence b = (Xl,....,X ) in B which is orthogonal

k
to the columns of C. The sequence b defines a linear dependence

among the rows of C,

Since every set of d or fewer rows of C are linearly independent,

bC = 0 implies that b is a sequence of weight d + l or greater.
Therefore the group of sequences orthogonal to C is an alphabet of
minimum weight d + l. The matrix C thus serves to define two mutually

orthogonal subspaces of B one constituting an array of strength d,

k 3
and the other a group alphabet of minimum weight d + l.
The alphabet may be derived from C as follows:

Let

C* is a k X (k-r) matrix of rank (k—r), and

[(C*)' C] = [M —Ik_r] r

58
The columns of CR generate a subgroup .A of sequences of minimum
weight d + l.

The existence of a matrix C with property P is shown by

d
Bose [5,6] to be sufficient for the existence of an array (Sr,k,5,d)

and necessary and sufficient for the existence of a t—error—correcting

group code with alphabet A , where d = 2t.

IO.

11.

l2.

13.

1A.

BIBLIOGRAPHY

Addelman, Sidney, "Augmenting Factorial Plans to Accomodate Addi-
tional Two—level Factors", Biometrics, Sept. 1962, pp. 308-322.

Baumert, L. D., S. W. Golomb, and M. Hall, "Discovery of an
Hadamard Matrix of Order 92", Bulletin of the American Mathematical
Society (68), 1962, pp. 237-238.

Baumert, L. D., and M. Hall, "A New Construction for Hadamard
Matrices", Bulletin of the American Mathematical Society (71),
1965, pp. 169-170.

Birkhoff, G., and S. MacLane, ”A Survey of Modern Algebra", Mac-
millan Co., 1959.

Bose, R. C., "Mathematical Theory of the Symmetrical Factorial
Design", Sankhya, Vol. 8, Part 2, 19A7.

Bose, R. C., "On Some Connections Between the Design of Experiments
and Information Theory", Bulletin of the International Statistical
Institute, Vol. 38, Part A, 1961.

Bose, R. C., and K. A. Bush, "Orthogonal Arrays of Strength Two
and Three”, Annals of Mathematical Statistics, Vol. 23, No. A
Dec. 1952.

3

Box, G. E. P., and J. S. Hunter, "The 2k-p Fractional Factorial
Designs", Technometrics, Vol. 3, No. 3, August 1961.

Bush, K. A., "Orthogonal Arrays of Index Unity", Annals of Mathe—
matical Statistics, Vol. 23, No. A, Dec. 1952.

Carmichael, Robert, "Groups of Finite Order"

, Dover Publications,
Inc., 1956. C0pywright 1937.

Fisher, R. A., "The Theory of Confounding in Factorial Experiments
in Relation to the Theory of Groups." Ann. Eugen. Lond., (ll)
19A2. pp. 3Al—353.

Hall, Marshall, Jr., "The Theory of Groups", Macmillan Co., 1959.

Hamming, R. W., "Error Detecting and Error Correcting Codes", Bell
System Technical Journal (29), 1950, pp. lA7—l60.

Kempthorne, Oscar, "The Design and Analysis of EXperiments", John
Wiley and Sons, N.Y., 1952.

59

l5.

l6.

l7.

l8.

19.

20.

21.

22.

[\3
Lo
0

2A.

60

Paley, R. E. A. C., ”On Orthogonal Matrices", Journal of Mathe-
matics and Physics (12), 1933, pp. 311-320.

Plackett, R. L., and J. P. Burman, "The Design of Optimum Multi-
factorial Experiments", Biometrika, Vol. 33, l9A6.

Rao, C. R., ”Factorial Experiments Derivable from Combinatorial
Arrangement of Arrays", Journal of the Royal Statistical Society,
Supplement, Vol. 9, No. l, 19A7.

Scheffe, Henry, "The Analysis of Variance", John Wiley and Sons,
N.Y., 1959.

Seiden, Esther, "On the Problem of Construction of Orthogonal
Arrays", Annals of Mathematical Statistics, Vol. 25, No. 1, March
195A.

Seiden, Esther, "Further Remarks on the Maximum Number of Con-
straints of an Orthogonal Array", Annals of Mathematical Statistics
Vol. 26, No. A, December 1955.

3

Seiden, Esther, "On the Maximum Number of Points No Four on One
Plane in a Projective Space PG(r-l,2)", Technical Report RM-
ll7, ES—7, Department of Statistics, Michigan State University,
196110

Slepian, D., "A Class of Binary Signalling Alphabets", Bell
System Technical Journal (35), 1956, pp. 203-23A.

Williamson, J., "Hadamard's Determinant Theorem and the Sum of
Four Squares”, Duke Mathematical Journal (11), 19AA, pp. 65—81.

Seiden, Esther, "A Theorem in Finite Projective Geometry and an
Application to Statistics", Proc. Amer. Math. Soc. Vol. 1
(1950), pp. 282-286.

3

Qvist, B., "Some Remarks Concerning Curves of the Second Degree
in a Finite Plane", Ann. Acad. Sci. Fennicae. Series A, I:
Math.-Phys. (13A). 1952.

 

 

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

1111111111

169