Double Arrays, Triple Arrays and Balanced Grids

John P. McSorley

Department of Computing, Information Science and Mathematics, London Guildhall University, 100 Minories, London EC3N 1JY, England

         mcsorley60@hotmail.com

N. C. K. Phillips

Department of Computer Science, Southern Illinois University,

Carbondale IL, USA 62901-4511 nckp@siu.edu

W. D. Wallis

Department of Mathematics, Southern Illinois University, Carbondale IL, USA 62901-4408 wdwallis@math.siu.edu

J. L. Yucas

Department of Mathematics, Southern Illinois University, Carbondale IL, USA 62901-4408 jyucas@math.siu.edu

Abstract

Triple arrays are a class of designs introduced by Agrawal in 1966 for two-way elimination of heterogeneity in experiments. In this paper we investigate their existence and their connection to other classes of designs, including balanced incomplete block designs and balanced grids.

1 Combinatorial designs in general

We shall follow the standard notations for combinatorial designs, as for example are laid down by Preece in the survey [11]. For convenience we restate the definitions that will be most important in this paper.

A balanced incomplete block design with parameters v, b, r, k, λ, denoted a (v, b, r, k, λ)-BIBD, is a way of selecting b subsets of size k, or blocks, from some v-set V = {t_{1}, t_{2}, …, t_{v}} of treatments, in such a way that every treatment appears in exactly r blocks (the design is equireplicate) and any two treatments appear together in exactly λ blocks (the design is balanced). The set V is called the support of the design. Since the blocks are defined as sets, these designs are necessarily binary (that is, there are no repeated members in blocks). The parameters of balanced incomplete block designs satisfy the two conditions

bk = vr,  (1)
λ(v − 1) = r(k − 1),  (2)

(see, for example, [19]). Without loss of generality, we usually write V = {1, 2, …, v}. The complement of a (v, b, r, k, λ)-BIBD is the (v, b, b − r, v − k, b − 2r + λ)-BIBD formed by replacing each block B by its complement in V, V \B.

A balanced incomplete block design is called symmetric if v = b (or, equivalently, r = k); in such a design, any two blocks intersect in λ elements. A symmetric balanced incomplete block design with parameters (v, k, λ) is often called a (v, k, λ)-SBIBD. Among symmetric balanced incomplete block designs are the finite projective planes, the symmetric designs with λ = 1, which exist if (and, it has been conjectured, only if) k − 1 is a prime power. Given a (v, k, λ)-SBIBD, its residual design modulo a given block B is constructed by deleting B from the list of blocks and deleting every member of B from the remaining blocks. The derived design modulo B is formed by deleting B and, in the remaining blocks, retaining only the members of B. The residual and derived designs are a (v − k, v − 1, k, k − λ, λ)-BIBD and a (k, v − 1, k − 1, λ, λ − 1)-BIBD respectively. Stanton [17] pointed out that the complement of the derived design of a symmetric balanced incomplete block design B equals the residual of the complement of B.

The usual definition of a balanced incomplete block design requires that k < v (“the blocks are incomplete”), but we shall find it convenient to allow the trivial case where k = v.

A binary row-column design is a rectangular array whose entries are members of some set of treatments, with no repetitions in any row or column. If such a design has r rows, c columns, and v treatments which form a v-set V, then it is an r × c binary row-column design based on V. We normally use the same notational conventions for V as above.

A binary row-column design is called equireplicate if every member of V appears the same number of times in the array. This common number is then called the replication number of the design.

Among binary row-column designs, perhaps the best-known is the Latin square, the designs with r = c = v, which are easily seen to exist for all values of v. Another important class are Youden squares. A Youden square is a k × v array based on a (v, k, λ)-SBIBD. Each column contains the elements of one block, ordered so that each element appears exactly once in each row. It was shown in [16] that such an ordering is always possible; that is, every symmetric balanced incomplete block design gives rise to a Youden square. (In fact, it is common for many non-isomorphic Youden squares to arise from the same SBIBD.)

When discussing binary row-column designs, we shall often need to refer to the set of all elements of a row, ignoring the arrangement of the elements into columns. It will be convenient to extend the usage in design theory and refer to this set as the support of the row; and similarly for columns.

2 Double arrays

We wish to investigate a class of binary row-column designs that were defined by Agrawal [], although a small example was discussed earlier by Potthoff [9] and another was published by Preece [10] independently of Agrawal’s paper. We shall introduce these designs below under the name of triple arrays. It will be convenient to begin by introducing a more general class, double arrays.

Suppose A is an equireplicate r × c binary row-column design based on V, with replication number k, having the following properties:

(P1) any two distinct rows have the same number, λ_{rr}, of common elements;

(P2) any two distinct columns have the same number, λ_{cc}, of common elements.

Then A is a double array with parameters v, k, λ_{rr}, λ_{cc}, or

DA(v, k, λ_{rr}, λ_{cc} : r × c).

Associated with any double array are two balanced incomplete block designs. To construct them, suppose the rows of a DA(v, k, λ_{rr}, λ_{cc} : r × c) are labeled R_{1}, R_{2}, …, R_{r} and the columns are labeled C_{1}, C_{2}, …, C_{c}. Then the row design or BIBD_{R} has v blocks B_{1}, B_{2}, …, B_{v}, corresponding to the v elements of V: if element x appears in rows R_{a}, R_{b}, …, R_{z} then B_{x} = {a, b, …, z}. Similarly the column design or BIBD_{C} is defined using the incidence of elements in columns.

Lemma 2.1 Suppose A is a DA(v, k, λ_{rr}, λ_{cc} : r × c). Then

(i) the row design of A is a balanced incomplete block design with param-

eters

(r, v, c, k, λ_{rr}).

(ii) the column design of A is a balanced incomplete block design with pa-

rameters (c, v, r, k, λ_{cc}).

Theorem 2.2 Any DA(v, k, λ_{rr}, λ_{cc} : r × c) satisfies

vk = rc,  (3)
λ_{rr}(r − 1) = c(k − 1),  (4)
λ_{cc}(c − 1) = r(k − 1),  (5)
λ_{rr}r(r − 1) = λ_{cc}c(c − 1).  (6)

Proof. Equation (3) follows from applying (1) to either of the designs associated with A. Equations (4) and (5) are just (2), for the BIBD_{R} and BIBD_{C} respectively. Equation (6) is obtained by combining (4) and (5). □

Example. Here is a DA(10, 3, 3, 2 : 5 × 6):

\begin{aligned}& C_{1} & C_{2} & C_{3} & C_{4} & C_{5} & C_{6} \\ R_{1} & 1 & 2 & 3 & 4 & 5 & 6 \\ R_{2} & 4 & 7 & 1 & 3 & 8 & 9 \\ R_{3} & 2 & 5 & 10 & 8 & 9 & 3 \\ R_{4} & 10 & 8 & 7 & 6 & 1 & 2 \\ R_{5} & 9 & 4 & 5 & 10 & 6 & 7 \end{aligned} .  (7)

The BIBD_{R} has parameters (5, 10, 6, 3, 3), with blocks

124, 134, 123, 125, 135, 145, 245, 234, 235, 345,

while the BIBD_{C} has parameters (6, 10, 5, 3, 2) and blocks

135, 126, 346, 124, 235, 456, 236, 245, 156, 134.

Clearly any double array must satisfy 1 ≤ k ≤ r and 1 ≤ k ≤ c. The extreme cases of double arrays need to be discussed. Both extreme cases will be called trivial.

If k = 1, so that no entry of the array is repeated, then λ_{rr} = λ_{cc} = 0, and the array is a DA(rc, 1, 0, 0 : r × c). This design exists for every r and c.

If k = r, (3) yields c = v, so every row is a permutation of the set V. So the array is a Latin rectangle. The BIBR_{R} is trivial, and the BIBD_{C} is a (v, r, λ_{cc})-SBIBD. As we said previously, such a design is called a Youden square and it is well-known that such a design exists if and only if there is a (v, r, λ_{cc})-SBIBD. (Many Youden squares may correspond to the same SBIBD.) The case k = c yields the transpose of a Youden square.

3 Triple arrays

Suppose A is a double array with parameters (v, k, λ_{rr}, λ_{cc} : r × c). Suppose further that A satisfies the following condition:

(P3) any row and any column have the same number, λ_{rc}, of common elements.

Then A is called a triple array with parameters v, k, λ_{rr}, λ_{cc}, λ_{rc}, or

T A(v, k, λ_{rr}, λ_{cc}, λ_{rc} : r × c).

Not every double array is a triple array. The smallest example is

1 2 3 4 3 1 5 6 6 4 2 5 ,

which is a DA(6, 2, 2, 1 : 3×4) but is not a triple array. In fact, an exhaustive search shows that there is no 3×4 triple array. In Section 7 we shall describe a DA(24, 6, 10, 3 : 9×16) which is not a triple array, and cannot be transformed into a triple array by any sequence of permutations within its columns.

Theorem 3.1 In any T A(v, k, λ_{rr}, λ_{cc}, λ_{rc} : r × c),

λ_{rc} = k.  (8)

Proof. Write I_{ij} for the intersection of row i with column j. If x is any particular entry in A, the binary property means that x belongs to k of the rows and k of the columns, so it is in k^{2} of the sets I_{ij}. As there are v different entries, the total number of entries in the I_{ij} is k^{2}v. But each I_{ij} is a λ_{rc}-set and there are rc of them. So k^{2}v = rcλ_{rc}. But vk = rc from (3), and the result follows. □

It is easy to see that any trivial double array is also a triple array (in both cases λ_{rc} = k), and these will be called trivial triple arrays. More interestingly, the example (7) is a triple array, a T A(10, 3, 3, 2, 3 : 5 × 6).

Theorem 3.2 Any triple array with k ≠ r and k ≠ c satisfies

v ≥ r + c − 1.  (9)

Proof. Suppose A is a T A(v, k, λ_{rr}, λ_{cc}, k : r × c) where k ≠ r. Let R and C denote the incidence matrices of the corresponding BIBD_{R} and BIBD_{C} respectively. The r × v matrix R satisfies RR^{T} = (c − λ_{rr})I + λ_{rr}J_{rr} and the c × v matrix C satisfies CC^{T} = (r − λ_{cc})I + λ_{cc}J_{cc}, where J_{pq} denotes the p × q matrix with every entry 1. From the definition of λ_{rc} it follows that RC^{T} = λ_{rc}J_{rc} = kJ_{rc} and CR^{T} = λ_{rc}J_{cr} = kJ_{cr}.

The (r + c) × v matrix A is defined by

A = \left[{R \atop C}\right] .

Then AA^{T} is (r + c) × (r + c), and satisfies

AA^{T} = \left[{R \atop C}\right] [R^{T} C^{T} ]
= \left[{RR^{T} RC^{T} \atop CR^{T} CC^{T}}\right]
= [ \begin{matrix}(c − λ_{rr})I + λ_{rr}J_{rr} & kJ_{rc} \\ kJ_{cr} & (r − λ_{cc})I + λ_{cc}J_{cc} \end{matrix} ] .  (10)

We show that AA^{T} has rank r + c − 1. Then

r + c − 1 = rank(AA^{T}) ≤ rank(A) ≤ v.

To find the rank we use row and column reduction.

AA^{T} = [ \begin{matrix}c & λ_{rr} & … & λ_{rr} & k & k & … & k \\ λ_{rr} & c & … & λ_{rr} & k & k & … & k \\ ⋮ & & ... & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ λ_{rr} & λ_{rr} & … & c & k & k & … & k \\ k & k & … & k & r & λ_{cc} & … & λ_{cc} \\ k & k & … & k & λ_{cc} & r & … & λ_{cc} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & & ... & ⋮ \\ k & k & … & k & λ_{cc} & λ_{cc} & … & r \end{matrix} ]

Subtracting column 1 from columns 2, 3, …, r, and column r + 1 from the later columns, we obtain

[ \begin{matrix}c & λ_{rr} − c & λ_{rr} − c & … & λ_{rr} − c & k & 0 & 0 & … & 0 \\ λ_{rr} & c − λ_{rr} & 0 & … & 0 & k & 0 & 0 & … & 0 \\ λ_{rr} & 0 & c − λ_{rr} & … & 0 & k & 0 & 0 & … & 0 \\ ⋮ & & & ... & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ λ_{rr} & 0 & 0 & … & 0 & k & 0 & 0 & … & 0 \\ λ_{rr} & 0 & 0 & … & c − λ_{rr} & k & 0 & 0 & … & 0 \\ k & 0 & 0 & … & 0 & r & λ_{cc} − r & λ_{cc} − r & … & λ_{cc} − r \\ k & 0 & 0 & … & 0 & λ_{cc} & r − λ_{cc} & 0 & … & 0 \\ k & 0 & 0 & … & 0 & λ_{cc} & 0 & r − λ_{cc} & … & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & & & ... & ⋮ \\ k & 0 & 0 & … & 0 & λ_{cc} & 0 & 0 & … & 0 \\ k & 0 & 0 & … & 0 & λ_{cc} & 0 & 0 & … & r − λ_{cc} \end{matrix} ]

Now add rows 2, 3, …, r to row 1, and rows r +1, r +2, r +3, …, r +c to row r. The (1, 1) entry becomes c + (r − 1)λ_{rr}; by (4) this equals c + c(k − 1), which equals ck. Similarly, the (r + 1, r + 1) entry equals rk.

[ \begin{matrix}ck & 0 & 0 & … & 0 & rk & 0 & 0 & … & 0 \\ λ_{rr} & c − λ_{rr} & 0 & … & 0 & k & 0 & 0 & … & 0 \\ λ_{rr} & 0 & c − λ_{rr} & … & 0 & k & 0 & 0 & … & 0 \\ ⋮ & & & ... & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ λ_{rr} & 0 & 0 & … & 0 & k & 0 & 0 & … & 0 \\ λ_{rr} & 0 & 0 & … & c − λ_{rr} & k & 0 & 0 & … & 0 \\ ck & 0 & 0 & … & 0 & rk & 0 & 0 & … & 0 \\ k & 0 & 0 & … & 0 & λ_{cc} & r − λ_{cc} & 0 & … & 0 \\ k & 0 & 0 & … & 0 & λ_{cc} & 0 & r − λ_{cc} & … & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & & & ... & ⋮ \\ k & 0 & 0 & … & 0 & λ_{cc} & 0 & 0 & … & 0 \\ k & 0 & 0 & … & 0 & λ_{cc} & 0 & 0 & … & r − λ_{cc} \end{matrix} ]

If row r + 1 and column r + 1 are deleted from this matrix, the resulting (r + c − 1) × (r + c − 1) matrix has determinant ck(c − λ_{rr})^{r−1}(r − λ_{cc})^{c−1}. If c − λ_{rr} = 0 then (4) gives k = r, which is not allowed, and similarly r − λ_{cc} = 0 gives k = c. So the determinant is non-zero, and the matrix AA^{T} has rank at least r +c−1. But rows 1 and r +1 are identical, so AA^{T} cannot have rank r + c. So it has rank r + c − 1, as required. □

Question: can we ever get v < r + c − 1 in a double array?

4 Balanced grids

We now introduce another type of binary row-column design. Its relevance will be seen in Section 6.

Suppose G is any binary row-column design. We shall define μ_{xy} to be the number of times that elements x and y occur in the same row or column of G. In other words, if there are r_{1} rows that contain both x and y, and c_{1} columns that contain them both, then μ_{xy} = r_{1} + c_{1}. A binary row-column design will be called a balanced grid if there is a constant μ such that μ_{xy} = μ for every x and y.

Theorem 4.1 An r × c balanced grid based on v symbols satisfies

μ = \frac{rc(r + c − 2)}{v(v − 1)};  (11)

moreover, it will be equireplicate, with replication number

k = \frac{rc}{v}.  (12)

Proof. Suppose G is an r × c balanced grid based on the v-set V. Each of the \binom{v}{2} pairs of elements of V occur μ times amongst the r rows and c columns of G. Each row covers \binom{c}{2} pairs, and each column \binom{r}{2} pairs. Hence

\binom{v}{2}μ = r\binom{c}{2} + c\binom{r}{2},

and the first result follows.

Now select an arbitrary fixed element x of V; suppose x occurs k[x] times in G. Consider the pairs of the form {x, y} where y ∈ V \{x}. If x appears in the (i, j) cell, r−1 such pairs arise in column j and c−1 in row i, for a total of r+c−2 pairs. So there are (r+c−2)k[x] such pairs in total. But clearly there are v − 1 pairs of the form {x, y} for a given x, so k[x](r + c − 2) = μ(v − 1). Therefore k[x] is constant, k say, independent of x, and k = \frac{rc}{v} from (3). □

In view of the above result, we shall denote such a balanced grid by

BG(v, k, μ : r × c).

The trivial cases of balanced grids are similar to those we have seen before. In the case c = v, a balanced grid is a Youden square. It will have r = k; a BG(v, k, μ : k × v) exists if and only if there is a (v, k, μ − k)-SBIBD. The case c = r = v is a Latin square, and has k = v, μ = 2v.

Theorem 4.2 Any balanced grid BG(v, k, μ : r × c) satisfies v ≤ r + c − 1.

Proof. Suppose G is a BG(v, k, μ : r × c). We define two (0, 1)-matrices: R is the r × v matrix with r_{ij} = 1 if j occurs in row i of G and 0 otherwise. Each row of R has c entries 1 and each column has k 1’s. Similarly, C is the c × v matrix with c_{ij} = 1 if j occurs in column i of G and 0 otherwise. Each row of C has r entries 1 and each column has k 1’s.

Now consider the matrix (r + c) × v matrix A, defined by

A = \left[{R \atop C}\right] .

A^{T} = [ R^{T} C^{T} ] and A^{T} A = [ R^{T} R + C^{T} C]. Since G is a balanced grid we have

A^{T} A = [ \begin{matrix}2k & μ & μ & μ & … & μ \\ μ & 2k & μ & μ & … & μ \\ μ & μ & 2k & μ & … & μ \\ ⋮ & ... & ... & … & … & ⋮ \\ μ & μ & μ & … & & 2k \end{matrix} ] .

This v × v matrix has determinant

(2k − μ)^{v−1}(vμ − μ + 2k).

Suppose the determinant is zero. If (2k − μ) = 0, then from Theorem 4.1 we know that μ = k \frac{r+c−2}{v−1}, so \frac{r+c−2}{v−1} = 2 and v = \frac{r+c}{2} ≤ r + c − 1, and the Theorem is true in this case. On the other hand, if vμ − μ + 2k = 0, then μ = \frac{−2k}{v−1} < 0, which is impossible.

Hence we need only consider the case where A is non-singular. So

v = rank(A^{T} A) ≤ rank(A) ≤ r + c.

We need to eliminate the possibility v = r + c.

If v = r + c then from (11) and (12),

μ = \frac{rc(r + c − 2)}{(r + c)(r + c − 1)} and k = \frac{rc}{(r + c)},

and both these quantities are integers.

Now the greatest common divisor of (r + c − 1) and (r + c − 2) is 1, so the first equality tells us that (r + c − 1) must divide rc. As (r + c − 1) and (r + c) are coprime, and each divides rc, so their product divides rc. But

r^{2} + c^{2} > r + c ⇒ r^{2} + c^{2} − r − c > 0
⇒ r^{2} + c^{2} − r − c + 2rc > 2rc
⇒ (r + c)(r + c − 1) > 2rc > rc,

a contradiction. □

(The above proof fails in the trivial case r = c = 1, but even there the Theorem is true.)

5 Triple arrays with v = r + c − 1.

In the case v = r + c − 1, all parameters of a triple array can be determined from v, r and λ_{cc}, using Theorems 2.2 and 3.1. Agrawal [1] gave a method that started from a (v + 1, r, λ_{cc})-SBIBD and constructed a T A(v, k, λ_{rr}, λ_{cc}, k : r × c). He could not prove that it always worked, but found it to provide the required array in every case he tried, provided r − λ_{cc} > 2.

Agrawal’s construction can be expressed as follows. Suppose the blocks of a (v + 1, r, λ_{cc})-SBIBD are B_{0}, B_{1}, …, B_{v}, and suppose the elements of B_{0} are labeled e_{1}, e_{2}, …, e_{r}. Denote the elements of the complement of B_{0} by f_{1}, f_{2}, …, f_{c} (this is the correct number of elements, because v = r + c − 1.) Construct an array whose (i, j) entry is the (r − λ_{cc})-set S_{ij} = {h : e_{i} ∉ B_{h}, f_{j} ∈ B_{h}}. Then the (i, j) entry of the triple array A is an element of S_{i,j}, and the rows and the columns of A contain no repetitions.

Subsequently Raghavarao and Nageswarerao [12] claimed to prove that the method always works, but we have pointed out [20] that their proof is faulty. So we have

Conjecture [1, 12] If there is a (v + 1, r, λ_{cc})-SBIBD with r − λ_{cc} > 2 then there is a T A(v, k, λ_{rr}, λ_{cc}, k : r × c) with v = r + c − 1.

We shall now prove the converse of this Conjecture: the existence of the triple array implies the existence of the symmetric balanced incomplete block design.

Lemma 5.1 Suppose A is a T A(v, k, λ_{rr}, λ_{cc}, λ_{rc} : r × c) with v = r + c − 1. Then

λ_{cc} = r − λ_{rc} = v − 2c + λ_{rr} + 1.  (13)

Proof. From the data and (3) we have

rc = vk = (r + c − 1)k = rk + (c − 1)k,

so

r(c − 1) = r(k − 1) + (c − 1)k,

and, using (5),

r = \frac{r(k − 1)}{c − 1} + k = λ_{cc} + λ_{rc},

giving the first equality.

For the second equality, notice that

λ_{cc} − λ_{rr} = (r − λ_{rc}) − \frac{c(k − 1)}{r − 1} (from (4))

= (r − k) − \frac{c(k − 1)}{r − 1}
= \frac{(r − k)(r − 1) − c(k − 1)}{r − 1}
= \frac{r(r − 1) − k(r + c − 1) + c}{r − 1}
= \frac{r(r − 1) − kv + c}{r − 1}
= \frac{r(r − 1) − rc + c}{r − 1} (from (3))
= r − c = r + c − 1 − 2c + 1 = v − 2c + 1.

□

Notice that the first equality can be written as k = r − λ_{cc}, in view of the fact that λ_{rc} = k.

Theorem 5.2 Suppose A is a T A(v, k, λ_{rr}, λ_{cc}, λ_{rc} : r × c) with v = r + c − 1. Then there exists a symmetric balanced incomplete block design with parameters

(v + 1, r, λ_{cc}).  (14)

Proof. Label the rows and columns of A as R_{1}, R_{2}, …, R_{r} and C_{1}, C_{2}, …, C_{c} respectively. Let P denote the set {R_{1}, R_{2}, …, R_{r}, C_{1}, C_{2}, …, C_{c}}. Then |P| = r + c = v + 1. We construct a design with treatment set P.

The i-th block of the BIBD_{C}, \overline{B}_{i} say, consists of those C_{j} that contain entry i. We extend \overline{B}_{i} to a block B_{i} as follows:

B_{i} = \overline{B}_{i} ∪ \{R_{j} : i ∉ R_{j}\}.

Since i belongs to k rows, it is missing from r − k rows, so |B_{i}| = k + (r − k) = r. So we have v blocks of size r. We add one further block, B_{0} = {R_{1}, R_{2}, …, R_{r}}.

The pair C_{i}C_{j} occurs λ_{cc} times among the blocks \overline{B}_{i} so it occurs λ_{cc} times among the blocks B_{i}. The pair C_{j}R_{t} occurs in B_{i} if and only if i is in column j and not in row t. Since column j intersects row t in λ_{rc} elements, it follows that C_{j}R_{t} occurs r − λ_{rc} times; by Lemma 5.1, that is λ_{cc} times. The pair R_{j}R_{t} occurs in B_{i} if and only if i does not occur in row j and does not occur in row t. Since those rows intersect in λ_{rr} places, we see that R_{j}R_{t} occurs in v−2c+λ_{rr} of the B_{i}. It also occurs in B_{0}. So it occurs in λ_{cc} = v−2c+λ_{rr}+1 blocks (using Lemma 5.1 again). So the design is balanced, with the required parameters. □

6 Relations between the arrays

It will be convenient to denote the symmetric design (14) by B, and to let A be a triple array with v = r + c − 1 that gives rise to B as described in Theorem 5.2.

Working back through the proof of Theorem 5.2, we observe that the BIBD_{C} of the triple array is the residual design of B modulo the block B_{0}, and the BIBD_{R} is the complement of the derived design modulo B_{0}.

Two symbols x and y both occur in column j of A if and only if blocks \overline{B}_{x} and \overline{B}_{y} of the BIBD_{C} contain the common element j. So x and y will occur together in |\overline{B}_{x} ∩\overline{B}_{y}| columns. Now \overline{B}_{x} ∩\overline{B}_{y} consists of those elements of B_{x} ∩ B_{y} that do not belong to B_{0}, so

|\overline{B}_{x} ∩ \overline{B}_{y}| = |B_{x} ∩ B_{y}| − |B_{x} ∩ B_{y} ∩ B_{0}|
= λ_{cc} − |B_{x} ∩ B_{y} ∩ B_{0}|.  (15)

Symbols x and y both occur in row i of A if and only if blocks x and y of the BIBD_{R} contain the common element i. Those blocks are B_{0}\B_{x} and B_{0}\B_{y}, and

|(B_{0}\B_{x}) ∩ (B_{0}\B_{y})| = |B_{0}| − |B_{0} ∩ B_{x}| − |B_{0} ∩ B_{y}| + |B_{x} ∩ B_{y} ∩ B_{0}|
= r − 2λ_{cc} + |B_{x} ∩ B_{y} ∩ B_{0}|.  (16)

Combining (15) and (16), we see that x and y occur together r − λ_{cc} = k times in the rows and columns of A. We have proven:

Theorem 6.1 Any T A(r +c−1, k, λ_{rr}, λ_{cc}, k : r ×c) is a BG(r +c−1, k, k : r × c).

The converse is certainly not true; we have found (computationally) large numbers of balanced grids with v = r + c − 1 that are not triple arrays, even at size 5 × 6. However, we have not found a case where the balanced grid is a double array but not a triple array. So we ask:

If A is a double array and a balanced grid, is it necessarily a triple array? Is this true in the particular case v = r + c − 1?

If a balanced grid satisfies v = r + c − 1, then (11) and (12) give μ = k.

7 The existence of balanced incomplete block designs

Although many constructions for balanced incomplete block designs are known, the existence of a design with given parameters is nearly always undecided. Apart from the necessary conditions (1) and (2), the only general nonexistence result is the Bruck-Ryser-Chowla Theorem:

Theorem 7.1 [4, 5, 13] If there exists a symmetric balanced incomplete block design with parameters (v, k, λ), then:

(i) if v is even, k − λ must be a perfect square;

(ii) if v is odd, there must exist integers x, y, and z, not all zero, such that

x^{2} = (k − λ)y^{2} + (−1)^{(v−1)/2}λz^{2}.

There is an extension to some residual designs:

Theorem 7.2 [6, 14, 15] Suppose D is a balanced incomplete block design with parameters (v − k, v − 1, k, k − λ, λ).

(i) If λ = 1 or λ = 2, there is a (v, k, λ)-design of which D is the residual.

(ii) There is a number f(λ), depending only on λ, such that if k ≥ f(λ), there is a (v, k, λ)-design of which D is the residual.

(The number f(λ) grows rapidly with λ. The original bound for f(λ), found in [14, 15], has been improved (see [8, 7]), but the best known bound is still quartic.)

A balanced incomplete block design is called quasi-residual if its parameters are the parameters of a residual design but the design is not the residual of any symmetric balanced incomplete block design. So Theorem 7.2 gives a restriction on the existence of quasi-residual designs.

Theorems 5.2 and 7.1 combine to show that certain triple arrays are impossible. For example, there is no (22, 7, 2)-SBIBD, so there can be no T A(21, 5, 10, 2, 5 : 7 × 15). Theorem 7.2 can also be used to show that some double arrays are impossible. For example, the nonexistence of a symmetric (22, 7, 2)-SBIBD implies that there is no (15, 21, 7, 5, 2)-BIBD; so a DA(21, 5, 10, 2 : 7 × 15) is impossible (the impossible parameters are those required for its BIBD_{C}).

We were interested in parameters such that a BIBD_{R} and a BIBD_{C} are feasible, but the corresponding symmetric balanced incomplete block design does not exist. Such parameters may well be numerous, but few are known. Most known quasi-residual designs have the same parameters as known residual designs. For example, the first reported quasi-residual design, found by Bhattacharya [3], has parameters (16, 24, 9, 6, 3). Although it cannot be embedded in a (25, 9, 3)-SBIBD, such SBIBDs exist. Among quasi-residual designs, many have the parameters of the residual of the complement of a non-existent projective plane, and consequently the corresponding BIBD_{R} is impossible.

One possible candidate was discovered by van Lint, Tonchev and Landgev [18]. It has parameters (28, 42, 15, 10, 5), the residual parameters of the impossible (43, 15, 5)-SBIBD. If it is the BIBD_{C} of a double array, then the BIBD_{R} would be a (15, 42, 28, 10, 18)-BIBD, which also exists. We very quickly found a DA(42, 10, 18, 5 : 15 × 28), which is exhibited in Appendix A.

Another interesting question is this: does there exist a double array that cannot be transformed into a triple array by any permutations of the elements within its columns, even though a triple array with the desired parameters exists? The answer is in the affirmative. We have discovered a double array DA(24, 6, 10, 3 : 9 × 16) whose BIBD_{C} is the (16, 24, 9, 6, 3)-BIBD given by Bhattacharya [3], who proved that this design could not be embedded in any (25, 9, 3)-SBIBD. The double array is also shown in Appendix A. (In fact, many double arrays can be constructed from Bhattacharya’s design). The non-embeddability of the BIBD_{C} means that this cannot be made into a triple array by any permutations of the elements within the columns, but a T A(24, 6, 10, 3, 6 : 9 × 16) is exhibited by Agrawal [1].

8 Triple arrays balanced for intersection

In any triple array, the rc sets formed by intersecting the supports of rows with columns are all sets of size k, and each element occurs in k^{2} of them. One might ask whether these sets might ever form a balanced incomplete block design. The triple array T A(r, k, λ_{rr}, λ_{cc}, k : r × c) (7) actually has this property, and its intersections form a (10, 30, 9, 3, 2)-BIBD. But this is the only case so far discovered.

If there is a triple array whose row-column intersections are balanced, then those intersections form a (v, rc, k^{2}, k, λ′)-BIBD, where from (2)

λ′ = k^{2}(k − 1)/(v − 1).

The requirement that λ′ be an integer turns out to be very restrictive. A search up to r = 100 found only 16 sets of parameters satisfying (1) and (1) for which λ′ was integral, and in 11 of these cases the existence of the corresponding symmetric balanced incomplete block design, guaranteed by Theorem 5.2, is impossible because of Theorem 7.1. (For example, the parameters work for a T A(21, 5, 10, 2, 5 : 7 × 15), but there is no (22, 7, 2)-SBIBD, so no such triple array exists.)

The smallest symmetric designs that could give row-column intersection balanced triple arrays are (11, 5, 2), which gives the design (7), (56, 11, 2) and (66, 26, 10). In the other two cases with r ≤ 100, namely (149, 37, 9) and (569, 72, 9), no symmetric balanced incomplete block design is known. We have constructed a triple array from a (56, 11, 2)-SBIBD, but it does not have the row-column intersection balance property.

9 Trivial cases of triple arrays

In this section we discuss triple arrays whose existence is a direct consequence of their parameters. These trivial cases include triple arrays with k = 1, r = 1 and k = r.

If k = 1, then every element occurs exactly once in the triple array, so v = rc. Distinct rows or columns will have no common members, and any row and column have intersection size 1. So the array is a T A(rc, 1, 0, 0, 1 : r ×c). Such a triple array exists for all r and c.

If r = 1 then the array consists of a single row. Clearly v = c and k = 1; this case is a subcase of the one discussed in the preceding paragraph.

When k = r, every symbol in any column must also belong to any row. So every symbol occurs in every row, and c = v. The array, a T A(v, k, v, λ, k : k × v), will be a Youden square, and as noted previously it will exist if and only if a (v, k, λ)-SBIBD exists.

10 Double and triple arrays with v > r + c − 1

Until recently, many researchers thought that there could be no triple array with v > r + c − 1. However, we have constructed a T A(35, 3, 5, 1, 3 : 7 × 15) (the array is presented in Appendix B). This example is very important, as it fills the gap in Table 1 of [11].

In Table 4, below, we list the parameters of possible small triple arrays with v > r + c − 1.

In each case, one can of course ask whether a double array exists. In particular, we found a DA(63, 5, 6, 3 : 15×21) and a DA(99, 5, 18, 1 : 11×45), which are shown in Appendix A.

11 Small arrays

Double and triple arrays and balanced grids with row or column size 1 are all trivial. If r = 2, the equireplicate property means that either v = c, a trivial case, or v = 2c and k = 1, again trivial (and similarly, of course, for c = 2). It is easy to see that no balanced grid with r = 2 can exist.

The case r = 3 is interesting. The equation vk = rc and the non-triviality condition v > c imply k < 3, so the only non-trivial case is k = 2. For a double or triple array, equation (5) yields c = 4, so v = 6. There is a double array DA(6, 2, 2, 1 : 3 × 4), for example

1 2 3 4 4 1 5 6 5 3 6 2 ,

but no T A(6, 2, 2, 1, 2 : 3×4) exists. If a non-trivial balanced grid with r = 3 exists, then equations (11) and (12) imply that μ = \frac{4c+4}{3c−2}; the only solution is c = 4, μ = 2 and it may be shown by exhaustion that no such grid exists.

We now discuss small non-trivial double and triple arrays.

We saw in Theorem 5.2 that a triple array with v = r + c − 1 exists only if a certain symmetric balanced incomplete block design exists. In Table 1 we list the parameters of triple arrays of this kind with r ≤ 16. The notation A means that the triple array was constructed by Agrawal and appears in [1]. However, it should be noted that a T A(10, 3, 3, 2, 3 : 5 × 6) may be found in [9] and a T A(14, 4, 4, 3, 4 : 7 × 8) is constructed in [10]. We found it very easy to implement Agrawal’s method by computer, and C means that a triple array with the required parameters was constructed by us. Many of these triple arrays can be found in Appendix B; for reasons of space, larger arrays have been omitted, but they are listed at [21]. Preece [11] points out that a T A(22, 6, 6, 5, 6 : 11 × 12) can be constructed by omitting a factor from a design obtainable by Method 2.6 of [2], but our example was found by computer search.

Table 2 shows the cases (for r ≤ 16) where the existence of a symmetric design is undecided.

Table 3 lists the parameters of double arrays for those cases with v = r + c − 1 (r ≤ 16) in which a triple array does not exist, the corresponding symmetric design being impossible. In many cases it is also known (from Theorem 7.2) that a BIBD_{C} does not exist, so no DA is possible; but not always. There is also the one anomalous case, corresponding to the (unique) (7, 3, 1)-SBIBD. Table 4 is a list of parameters with v > r + c − 1, up to

T A  BIBD_{R}  BIBD_{C}  SBIBD
v, k, λ_{rr}, λ_{cc}, λ_{rc} : r × c  r, v, c, k, λ_{rr}  c, v, r, k, λ_{cc}  v + 1, r, λ_{cc}
12, 3, 6, 1, 3 : 4 × 9  4, 12, 9, 3, 6  9, 12, 4, 3, 1  13, 4, 1  A
10, 3, 3, 2, 3 : 5 × 6  5, 10, 6, 3, 3  6, 10, 5, 3, 2  11, 5, 2  A
20, 4, 12, 1, 4 : 5 × 16  5, 20, 16, 4, 12  16, 20, 5, 4, 1  21, 5, 1  A
15, 4, 6, 2, 4 : 6 × 10  6, 15, 10, 4, 6  10, 15, 6, 4, 2  16, 6, 2  A
30, 5, 20, 1, 5 : 6 × 25  6, 30, 25, 5, 20  25, 30, 6, 5, 1  31, 6, 1  A
14, 4, 4, 3, 4 : 7 × 8  7, 14, 8, 4, 4  8, 14, 7, 4, 3  15, 7, 3  A
56, 7, 42, 1, 7 : 8 × 49  8, 56, 49, 7, 42  49, 56, 8, 7, 1  57, 8, 1  C
18, 5, 5, 4, 5 : 9 × 10  9, 18, 10, 5, 5  10, 18, 9, 5, 4  19, 9, 4  A
24, 6, 10, 3, 6 : 9 × 16  9, 24, 16, 6, 10  16, 24, 9, 6, 3  25, 9, 3  A
36, 7, 21, 2, 7 : 9 × 28  9, 36, 28, 7, 21  28, 36, 9, 7, 2  37, 9, 2  C
72, 8, 56, 1, 8 : 9 × 64  9, 72, 64, 8, 56  64, 72, 9, 8, 1  73, 9, 1  C
30, 7, 14, 3, 7 : 10 × 21  10, 30, 21, 7, 14  21, 30, 10, 7, 3  31, 10, 3  C
90, 9, 72, 1, 9 : 10 × 81  10, 90, 81, 9, 72  81, 90, 10, 9, 1  91, 10, 1  C
22, 6, 6, 5, 6 : 11 × 12  11, 22, 12, 6, 6  12, 22, 11, 6, 5  23, 11, 5  C
55, 9, 36, 2, 9 : 11 × 45  11, 55, 45, 9, 36  45, 55, 11, 9, 2  56, 11, 2  C
44, 9, 24, 3, 9 : 12 × 33  12, 44, 33, 9, 24  33, 44, 12, 9, 3  45, 12, 3  C
132, 11, 110, 1, 11 : 12 × 121 12, 132, 121, 11, 110 121, 132, 12, 11, 1 133, 12, 1  C
26, 7, 7, 6, 7 : 13 × 14  13, 26, 14, 7, 7  14, 26, 13, 7, 6  27, 13, 6  C
39, 9, 18, 4, 9 : 13 × 27  13, 39, 27, 9, 18  27, 39, 13, 9, 4  40, 13, 4  C
78, 11, 55, 2, 11 : 13 × 66  13, 78, 66, 11, 55  66, 78, 13, 11, 2 79, 13, 2  C
182, 13, 156, 1, 13 : 14 × 169 14, 182, 169, 13, 156 169, 182, 14, 13, 1 183, 14, 1  C
30, 8, 8, 7, 8 : 15 × 16  15, 30, 16, 8, 8  16, 30, 15, 8, 7  31, 15, 7  C
35, 9, 12, 6, 9 : 15 × 21  15, 35, 21, 9, 12  21, 35, 15, 9, 6  36, 15, 6  C
70, 12, 44, 3, 12 : 15 × 56  15, 70, 56, 12, 44  56, 70, 15, 12, 3 71, 15, 3  C
40, 10, 15, 6, 10 : 16 × 25  16, 40, 25, 10, 15  25, 40, 16, 10, 6 41, 16, 6  C
48, 11, 22, 5, 11 : 16 × 33  16, 48, 33, 11, 22  33, 48, 16, 11, 5 49, 16, 5  C
60, 12, 33, 4, 12 : 16 × 45  16, 60, 45, 12, 33  45, 60, 16, 12, 4 61, 16, 4  C

Table 1: Parameters for a T A with v = r+c−1 where the SBIBD is known. 2 ≤ r ≤ 16, r ≤ c, 2 ≤ k < r, 1 ≤ λ_{cc} < r. r = 16, for a possible double or triple array. In both these tables C again denotes an array we have constructed, while NE means that the indicated array is non-existent.

\begin{matrix}T A & BIBD_{R} & BIBD_{C} & SBIBD \\ v, k, λ_{rr}, λ_{cc}, λ_{rc} : r × c & r, v, c, k, λ_{rr} & c, v, r, k, λ_{cc} & v + 1, r, λ_{cc} \\ 156, 12, 132, 1, 12 : 13 × 144 & 13, 156, 144, 12, 132 & 144, 156, 13, 12, 1 & 157, 13, 1 \\ 80, 13, 52, 3, 13 : 16 × 65 & 16, 80, 65, 13, 52 & 65, 80, 16, 13, 3 & 81, 16, 3 \\ 120, 14, 91, 2, 14 : 16 × 105 & 16, 120, 105, 14, 91 & 105, 120, 16, 14, 2 & 121, 16, 2 \\ 240, 15, 210, 1, 15 : 16 × 225 & 16, 240, 225, 15, 210 & 225, 240, 16, 15, 1 & 241, 16, 1 \end{matrix}

Table 2: Case v = r + c − 1. Possible parameters for a T A when no SBIBD is known. 2 ≤ r ≤ 16, r ≤ c, 2 ≤ k < r, 1 ≤ λ_{cc} < r.

References

[1] H. Agrawal, Some methods of construction of designs for two-way elimination of heterogeneity. J. Amer. Statist. Assoc. 61(1966), 1153–1171.

[2] H. L. Agrawal and R. I. Mishra, Some methods of construction of 4DIB designs. Calcutta Statist. Assoc. Bull. 20(1971), 89–92.

[3] K. N. Bhattacharya, A new balanced incomplete block design, Science and Culture 9 (1944), 508.

[4] R. H. Bruck and H. J. Ryser, The non-existence of certain finite projective planes, Canad. J. Math. 1 (1949), 88–93.

[5] S. Chowla and H. J. Ryser, Combinatorial problems, Canad. J. Math. 2 (1950), 93–99.

[6] M. Hall and W. S. Connor, An embedding theorem for balanced incomplete block designs, Canad. J. Math. 6 (1954), 35–41.

[7] K. Neumaier, Quasi-residual 2-designs, 1\frac{1}{2}-designs, and strongly regular multigraphs. Geom. Dedicata 12(1982), 351–366.

T A  BIBD_{R}  BIBD_{C}  SBIBD DA ?
v, k, λ_{rr}, λ_{cc}, λ_{rc} : r × c  r, v, c, k, λ_{rr}  c, v, r, k, λ_{cc}  v + 1, r, λ_{cc}
6, 2, 2, 1, 2 : 3 × 4  3, 6, 4, 2, 2  4, 6, 3, 2, 1  7, 3, 1  C
21, 5, 10, 2, 5 : 7 × 15  7, 21, 15, 5, 10  15, 21, 7, 5, 2  22, 7, 2  NE
42, 6, 30, 1, 6 : 7 × 36  7, 42, 36, 6, 30  36, 42, 7, 6, 1  43, 7, 1  NE
28, 6, 15, 2, 6 : 8 × 21  8, 28, 21, 6, 15  21, 28, 8, 6, 2  29, 8, 2  NE
45, 8, 28, 2, 8 : 10 × 36  10, 45, 36, 8, 28  36, 45, 10, 8, 2  46, 10, 2  NE
110, 10, 90, 1, 10 : 11 × 100 11, 110, 100, 10, 90 100, 110, 11, 10, 1 111, 11, 1  NE
33, 8, 14, 4, 8 : 12 × 22  12, 33, 22, 8, 14  22, 33, 12, 8, 4  34, 12, 4  ??
66, 10, 45, 2, 10 : 12 × 55  12, 66, 55, 10, 45  55, 66, 12, 10, 2 67, 12, 2  NE
52, 10, 30, 3, 10 : 13 × 40  13, 52, 40, 10, 30  40, 52, 13, 10, 3 53, 13, 3  ??
91, 12, 66, 2, 12 : 14 × 78  14, 91, 78, 12, 66  78, 91, 14, 12, 2 92, 14, 2  NE
42, 10, 18, 5, 10 : 15 × 28  15, 42, 28, 10, 18  28, 42, 15, 10, 5 43, 15, 5  C
105, 13, 78, 2, 13 : 15 × 91 15, 105, 91, 13, 78 91, 105, 15, 13, 2 106, 15, 2  NE
210, 14, 182, 1, 14 : 15 × 196 15, 210, 196, 14, 182 196, 210, 15, 14, 1 211, 15, 1  NE

Table 3: Case v = r + c − 1. Parameters for which there is no T A.

2 ≤ r ≤ 16, r ≤ c, 2 ≤ k < r, 1 ≤ λ_{cc} < r.

\begin{matrix}T A & BIBD_{R} & BIBD_{C} & DA ? \\ v, k, λ_{rr}, λ_{cc}, λ_{rc} : r × c & r, v, c, k, λ_{rr} & c, v, r, k, λ_{cc} & T A ? \\ 35, 3, 5, 1, 3 : 7 × 15 & 7, 35, 15, 3, 5 & 15, 35, 7, 3, 1 & T A C \\ 99, 5, 18, 1, 5 : 11 × 45 & 11, 99, 45, 5, 18 & 45, 99, 11, 5, 1 & DA C \\ 130, 4, 10, 1, 4 : 13 × 40 & 13, 130, 40, 4, 10 & 40, 130, 13, 4, 1 & ?? \\ 63, 5, 6, 3, 5 : 15 × 21 & 15, 63, 21, 5, 6 & 21, 63, 15, 5, 3 & DA C \\ 195, 7, 39, 1, 7 : 15 × 91 & 15, 195, 91, 7, 39 & 91, 195, 15, 7, 1 & ?? \\ 100, 4, 5, 2, 4 : 16 × 25 & 16, 100, 25, 4, 5 & 25, 100, 16, 4, 2 & ?? \\ 216, 6, 27, 1, 6 : 16 × 81 & 16, 216, 81, 6, 27 & 81, 216, 16, 6, 1 & ?? \\ 56, 6, 7, 4, 6 : 16 × 21 & 16, 56, 21, 6, 7 & 21, 56, 16, 6, 4 & ?? \\ 232, 10, 87, 1, 10 : 16 × 145 & 16, 232, 145, 10, 87 & 145, 232, 16, 10, 1 & ?? \end{matrix}

Table 4: Case v > r + c − 1. Possible parameters for a DA or TA. 2 ≤ r ≤ 16, r ≤ c, 2 ≤ k < r, 1 ≤ λ_{cc} < r.

[8] A. Metsch, Quasi-residual designs, 1\frac{1}{2}-designs, and strongly regular multigraphs. Discrete Math. 143(1995), 167–188.

[9] R. F. Potthoff, Three-factor additive designs more general than the Latin square. Technometrics 4 (1962), 187–208.

[10] D. A. Preece, Some row and column designs for two sets of treatments. Biometrics 22 (1966), 1–25.

[11] D. A. Preece, Non-orthogonal graeco-latin designs. Combinatorial Mathematics IV, Proceedings of the Fourth Australian Conference (Springer-Verlag, 1976), 7–26.

[12] D. Raghavarao and G. Nageswarerao, A note on a method of construction of designs for two-way elimination of heterogeneity. Commun. Statist. 3(1974), 197–199.

[13] M. P. Schutzenberger, A non-existence theorem for an infinite family of symmetrical block designs, Ann. Eugenics 14 (1949), 286–287.

[14] N. M. Singhi and S. S. Shrikhande, Embedding of quasi-residual designs with λ = 3, Utilitas Math. 4 (1973), 35–53.

[15] N. M. Singhi and S. S. Shrikhande, Embedding of quasi-residual designs, Geom. Ded. 2 (1974), 509–517.

[16] C. A. B. Smith and H. O. Hartley, The construction of Youden squares. J. Royal Statist. Soc. (series B) 10(1948), 262–263.

[17] R. G. Stanton, Interconnections of related BIBDs. J. Combinatorial Theory 6(1969), 387–391.

[18] J. H. van Lint, V. D. Tonchev and I. N. Landgev, A new design. Coding Theory and Design Theory Part II Design Theory (IMA vol. Math. Appl. 14) (Springer-Verlag, 1990), 251–256.

[19] W. D. Wallis, Combinatorial Designs. (Marcel Dekker, New York, 1988.)

[20] W. D. Wallis and J. L. Yucas, Note on the construction of designs for the elimination of heterogeneity, J. Combin. Math. Combin. Comput. (to appear).

[21] Triple arrays, .

Appendix A: Double arrays

This is a double array DA(6, 2, 2, 1 : 3 × 4):

1 2 3 4 4 1 5 6 5 3 6 2

Here is the DA(42, 10, 18, 5 : 15 × 28), mentioned in Section 7:

16 31 26 27 7 21 2 12 13 35 37 20 39 30 8 3 34 24 5 40 9 18 10 32 33 22 23 38 40 38 22 21 13 25 31 27 14 11 34 41 28 32 4 9 3 23 8 6 19 10 33 36 24 39 17 35 34 12 20 9 42 14 41 39 4 15 26 1 36 18 32 5 10 40 37 24 28 35 11 23 22 33 7 25 37 25 36 12 6 1 35 24 10 42 19 29 8 34 5 38 2 11 16 27 33 26 21 15 13 23 41 40 9 6 11 34 35 29 24 25 28 27 13 7 30 41 2 22 26 3 12 38 17 39 36 16 42 14 20 37 31 35 7 14 37 40 38 1 25 3 15 28 21 39 30 36 23 27 4 10 8 29 13 17 12 18 26 42 11 18 19 39 15 8 22 16 24 32 1 13 31 4 37 26 27 28 41 30 38 9 29 40 5 2 14 36 2 3 31 19 32 10 12 9 41 37 40 14 42 1 23 25 20 5 28 16 27 33 30 38 17 6 15 39 6 10 39 41 28 11 26 13 17 29 4 2 3 16 42 1 38 21 33 32 7 40 18 20 34 15 24 31 3 7 8 32 21 34 15 42 39 18 12 5 2 22 35 40 33 4 25 14 11 17 27 29 30 16 19 41 20 17 42 5 22 31 9 23 34 12 28 35 29 3 1 19 4 30 6 26 16 8 41 13 18 40 36 33 5 41 18 6 24 7 23 10 2 14 31 27 15 9 17 32 42 35 29 36 34 20 19 4 21 13 37 30 18 19 5 20 10 22 30 36 11 25 6 31 14 7 16 28 29 33 24 8 42 1 37 21 38 35 3 32 17 21 4 23 20 37 8 31 32 26 30 38 6 29 19 2 22 39 36 7 15 12 9 11 1 25 33 34 24 4 13 8 9 23 11 3 26 5 27 16 17 15 10 21 6 7 22 18 25 28 2 12 14 19 1 20

The DA(24, 6, 10, 3 : 9×16) whose column design is the (16, 24, 9, 6, 3)-BIBD due to Bhattacharya [3] (see Section 7):

A DA(63, 5, 6, 3 : 15 × 21): 24 15 37 36 58 50 13 55 14 44 16 46 61 27 42 29 1 31 51 10 23 45 28 14 52 11 59 51 56 1 2 17 38 15 37 62 43 30 24 32 25 47 48 57 29 15 16 12 60 31 53 33 1 44 39 25 38 18 2 3 63 52 26 54 34 26 27 39 61 30 19 32 58 13 17 45 4 49 1 40 2 3 46 53 14 55 16 59 31 40 33 35 62 54 3 18 47 20 41 27 28 50 4 5 2 3 29 5 6 32 17 55 21 15 63 34 56 36 19 28 60 51 41 42 4 48 7 49 56 30 52 33 18 42 35 57 37 4 5 61 20 22 43 29 46 1 6 6 50 58 38 7 53 62 34 57 36 43 2 19 16 21 8 23 44 30 47 5 35 7 51 9 37 8 39 63 20 16 58 59 3 48 17 6 22 45 24 54 44 49 4 8 17 18 38 9 52 36 23 59 25 60 40 7 21 61 10 45 31 55 56 8 50 31 53 19 41 10 22 37 24 60 18 46 5 39 9 62 11 26 32 12 46 9 51 10 32 54 40 11 42 38 23 57 6 47 63 19 20 25 33 27 33 13 47 10 28 11 20 61 41 12 55 39 24 58 26 48 7 52 21 43 34 27 25 35 48 49 29 34 13 56 21 22 14 40 62 59 42 44 8 53 12 11 28 36 30 57 60 54 12 14 43 15 45 35 26 41 63 50 49 23 9 22 13

21 18 11 19 23 12 7 1 3 6 20 14 5 4 9 13 23 3 4 12 2 5 11 13 21 16 24 17 6 8 15 20 17 10 12 9 6 22 1 16 4 14 11 20 8 23 24 19 16 1 3 10 12 18 13 14 9 7 2 4 24 11 17 15 1 12 8 13 4 15 5 2 23 21 10 7 19 14 22 24 13 6 2 14 20 11 18 22 10 15 17 5 16 19 1 21 5 17 21 7 19 16 2 4 22 11 23 9 10 18 8 3 19 20 17 22 15 8 9 3 18 23 13 24 2 1 6 7 12 14 7 8 9 20 6 15 5 10 22 16 3 24 21 18 25 A DA(99, 5, 18, 1 : 11 × 45):

34 12 86 91 15 1 75 71 53 92 64 56 81 93 59 20 5 31 82 3 26 27 36
81 82 83 48 4 61 92 21 37 90 15 2 93 79 10 59 27 17 57 94 16 50 28
50 72 91 84 49 11 62 36 77 5 29 93 61 82 14 51 60 88 94 58 95 66 6
19 7 8 17 18 39 6 92 89 23 84 67 41 4 28 26 94 1 29 83 70 40 78
71 35 13 9 85 79 2 52 8 73 93 7 68 42 5 84 16 62 63 90 49 57 46
91 20 31 14 10 86 25 3 64 9 6 85 8 69 63 94 61 28 32 30 76 17 58
11 70 66 87 75 92 51 76 4 65 44 77 26 62 43 86 22 53 18 64 9 21 95
5 1 16 32 33 74 87 88 22 38 60 30 78 27 93 65 52 56 54 19 89 10 67
6 46 2 67 88 24 12 13 72 78 1 45 57 9 83 34 35 94 89 55 39 90 86
89 91 73 3 68 10 40 7 14 54 76 65 12 58 80 21 87 23 2 25 56 95 18
69 90 47 74 91 55 80 63 92 15 66 11 3 13 70 4 85 81 24 33 25 77 22

47 48 14 80 23 42 78 4 97 16 69 60 9 25 37 49 58 45 70 38 67 89
87 60 54 71 76 24 13 35 5 43 72 70 46 65 6 38 98 49 32 26 39 68
7 38 16 22 18 28 25 80 55 71 17 3 40 47 73 83 39 69 99 33 27 44
59 95 96 15 72 12 50 74 37 51 52 73 85 81 56 62 45 61 30 63 34 48
95 24 30 96 27 19 29 41 20 38 97 18 31 60 82 74 75 51 86 53 64 40
19 80 75 47 83 96 74 54 42 97 39 53 41 72 21 98 50 36 52 87 43 65
37 88 81 55 48 73 20 97 31 32 59 40 98 10 33 7 84 29 15 42 54 99
23 8 21 82 96 49 85 66 76 77 44 45 71 98 43 34 63 99 41 11 12 55
79 20 44 17 11 77 53 56 75 68 33 97 64 42 61 22 23 31 50 66 99 28
29 69 79 45 51 84 43 36 67 1 78 34 24 32 98 57 35 90 62 46 47 13
68 30 46 26 41 52 96 19 57 58 2 79 59 36 48 44 8 14 37 99 88 35

Appendix B: Triple arrays

Here is a T A(35, 3, 5, 1, 3 : 7 × 15); see Section 10:

31 1 18 16 7 10 5 3 4 2 33 14 19 15 12 26 32 1 2 29 30 28 20 27 11 5 34 3 8 4 1 17 13 9 3 4 21 22 6 35 25 5 24 2 23 6 27 33 28 16 13 35 30 15 10 9 26 12 17 29 16 12 23 32 34 21 15 33 24 22 11 10 8 25 20 21 22 28 24 25 19 7 14 18 29 27 23 26 30 31 11 7 8 14 13 32 20 6 34 18 19 17 35 31 9 .

The following arrays were constructed by computer, using Agrawal’s construction. They fill in the holes in Table 1 that are marked C. A T A(56, 7, 42, 1, 7 : 8 × 49)

50 23 31 46 26 20 35 33 34 19 37 38 47 51 39 49 21 24 14 52 27 11 15 16 40
36 50 3 39 40 41 49 51 18 44 20 22 15 24 1 52 43 4 34 46 29 37 2 26 53
29 30 45 25 12 50 7 9 26 27 4 46 51 40 52 31 3 44 36 37 38 47 53 49 43
8 44 17 50 47 13 42 41 51 11 29 21 14 32 48 40 12 52 16 6 7 34 35 53 30
22 9 10 4 5 48 50 49 43 51 45 13 6 8 28 2 23 42 52 26 47 21 25 39 14
43 2 24 18 50 27 28 1 10 35 51 30 31 7 19 22 32 13 45 17 52 53 48 3 4
15 37 50 11 19 34 21 25 2 3 12 51 39 16 30 20 52 33 5 35 9 1 38 29 17
1 16 38 32 33 6 14 17 42 36 28 5 23 48 10 11 41 15 25 8 18 24 12 13 27
53 32 36 42 28 54 8 43 25 41 13 29 30 48 10 55 12 44 45 9 22 17 18 56
5 45 7 16 32 48 54 35 21 30 23 55 25 31 27 33 17 38 56 28 47 42 6 19
41 42 23 1 54 33 34 39 6 11 35 14 8 55 5 28 22 32 2 56 10 48 24 13
18 9 46 31 36 3 19 20 10 54 45 2 55 4 37 38 39 1 33 15 56 5 49 43
44 19 53 12 17 18 38 54 40 15 1 24 3 36 55 16 7 20 27 46 41 11 56 37
8 6 33 54 47 14 49 5 29 26 55 46 20 9 15 11 44 56 21 34 16 23 12 25
28 53 10 27 13 22 23 24 54 7 18 41 42 26 32 6 55 14 8 40 4 56 36 31
31 22 20 46 2 37 4 9 44 45 40 19 47 21 49 43 34 26 39 3 35 29 30 7

A T A(36, 7, 21, 2, 7 : 9 × 28):

1 8 6 11 3 30 36 16 13 9 2 7 33 5 25 17 28 23 10 27 12 24 15 20 29 18 19 31
33 18 4 29 12 31 8 7 10 35 17 15 3 9 5 19 22 20 11 25 13 27 14 26 30 1 32 21
15 30 20 33 8 6 32 34 27 11 21 2 16 18 10 26 9 22 23 4 5 14 19 28 36 31 12 13
36 1 10 7 30 23 14 33 11 12 15 18 8 4 16 20 13 25 24 22 17 6 28 29 21 32 35 34
27 4 1 5 22 35 31 12 34 36 14 13 23 20 19 7 21 10 26 24 28 18 30 16 17 29 2 3
35 25 3 28 5 7 24 26 2 18 31 32 14 17 6 22 1 9 21 11 23 33 27 8 16 34 30 20
23 26 27 21 6 4 10 9 35 28 12 22 17 34 18 36 8 2 3 31 25 29 7 15 32 19 24 33
22 2 28 4 34 13 5 10 17 14 1 3 19 15 35 6 24 29 30 16 32 26 25 31 9 11 33 36
5 36 32 2 29 9 7 1 8 3 6 16 4 24 21 11 19 14 15 12 26 13 34 35 27 23 20 25

A T A(72, 8, 56, 1, 8 : 9 × 64): — See [21]

A T A(30, 7, 14, 3, 7 : 10 × 21):

18 19 2 29 22 11 1 16 13 30 6 3 23 24 12 10 21 8 26 7 15
19 3 23 15 16 29 17 30 4 14 24 25 1 20 2 11 7 12 13 27 9
25 14 4 24 29 16 18 21 28 5 2 8 26 30 3 17 12 13 20 10 1
29 22 8 13 6 5 26 11 30 27 17 9 21 2 19 3 18 25 14 15 4
28 29 12 3 10 7 27 6 15 18 23 30 4 26 5 20 14 19 9 8 16
10 11 29 21 24 8 9 27 7 22 30 20 19 5 17 13 4 6 16 1 28
7 20 21 9 15 25 29 28 12 23 14 18 30 10 22 6 5 1 2 17 11
13 28 20 23 25 26 24 12 17 16 19 22 9 27 10 18 11 15 21 14 8
2 26 27 5 4 17 6 3 22 1 28 24 25 15 16 23 19 20 7 21 18
27 1 22 28 14 23 12 25 26 13 8 7 10 11 9 4 24 5 6 3 2

A T A(90, 9, 72, 1, 9 : 10 × 81): — See [21]

13 21 15 7 19 10 20 4 22 1 3 5
6 16 8 4 17 22 11 13 19 20 1 2
22 4 6 15 10 9 2 21 3 18 17 16
20 9 10 14 16 18 7 8 21 2 19 1
12 5 18 19 13 11 10 14 2 6 21 22
21 20 11 16 6 13 3 1 12 15 9 14
18 17 19 9 12 1 22 15 7 11 14 4
8 12 14 6 7 16 17 10 15 5 22 20
7 11 4 13 3 5 14 17 16 21 8 18
9 19 20 2 18 15 13 12 8 17 5 3
4 10 3 5 1 8 9 2 11 7 6 12

A T A(55, 9, 36, 2, 9 : 11 × 45): — See [21]

A T A(22, 6, 6, 5, 6 : 12 × 33):

34 38 6 44 8 41 29 22 43 13 32 25 15 4 12 5 26 17 10 20 28 19 31 23 9 7 11 16 37 18 14 40 35
37 26 36 28 27 38 10 11 33 14 30 24 20 12 23 43 44 2 18 16 21 15 13 9 34 3 1 7 8 31 17 41 40
22 2 4 38 35 19 24 40 21 15 18 44 1 14 6 13 3 43 30 11 5 16 17 32 36 27 25 37 33 12 41 29 10
31 20 40 5 9 8 36 34 13 44 43 17 42 21 7 1 4 15 29 30 25 26 32 2 24 22 6 38 14 39 3 18 16
28 35 33 21 29 22 43 10 26 27 19 40 9 39 44 11 18 7 6 2 23 3 8 31 4 36 16 1 17 38 42 12 5
40 1 20 24 43 30 25 32 42 23 34 33 44 19 2 9 13 39 14 28 3 11 27 10 12 5 15 4 38 35 6 7 8
3 44 43 41 32 36 12 39 22 31 23 28 17 8 16 24 37 25 1 27 29 5 33 4 26 14 35 10 34 15 9 42 30
1 41 30 6 21 7 20 44 35 29 16 39 19 43 14 18 27 26 28 9 13 31 12 25 2 34 36 32 5 37 11 33 42
43 29 37 34 24 44 31 21 28 36 17 35 10 3 42 22 11 41 8 15 30 7 20 33 19 18 23 39 2 6 32 4 13
25 3 26 31 7 33 11 30 38 39 27 16 21 20 37 23 42 6 19 4 17 24 22 14 35 10 34 13 29 9 40 1 41
2 23 5 4 40 25 38 12 14 19 42 20 37 41 24 39 8 27 26 22 7 32 1 18 17 35 21 36 11 30 28 15 31
19 32 23 27 37 9 42 26 15 40 38 18 5 16 22 41 25 10 24 29 12 33 6 21 13 20 8 28 39 3 36 34 2

A T A(132, 11, 110, 1, 11 : 12 × 121): — See [21] 30 A T A(78, 11, 55, 2, 11 : 13 × 66): — See [21]

A T A(182, 13, 156, 1, 13 : 14 × 169): — See [21]

A T A(30, 8, 8, 7, 8 : 15 × 16)

25 26 20 9 6 14 2 3 24 30 18 27 16 29 1 15
9 5 21 23 19 1 18 27 29 2 30 12 6 28 4 17
28 6 9 22 7 26 10 23 11 24 3 1 2 17 14 4
2 3 4 18 23 8 15 29 12 11 10 5 7 24 27 25
4 9 3 12 24 11 5 28 19 16 13 26 8 25 30 6
8 10 6 11 21 15 27 14 30 18 1 28 26 5 13 7
7 17 30 29 9 12 13 16 20 3 23 15 28 8 10 1
20 19 11 1 12 16 24 13 17 21 5 7 27 14 3 2
14 8 18 6 13 25 12 17 28 15 20 3 4 21 2 22
16 21 7 5 14 4 9 18 15 23 26 22 29 3 19 13
10 15 16 24 30 23 17 6 14 8 4 19 20 27 22 5
19 29 12 8 25 17 22 10 18 1 24 6 21 7 26 16
18 11 27 20 2 9 26 25 7 19 17 23 13 22 8 30
1 20 10 13 15 27 28 19 4 22 21 25 24 9 29 11
5 2 22 14 10 21 16 11 26 28 25 20 23 30 12 29

A T A(35, 9, 12, 6, 9 : 15 × 21)

31 8 28 32 23 6 19 34 20 22 9 24 7 4 33 35 30 17 12 25 15
9 29 7 8 2 1 16 32 10 4 34 13 24 12 5 30 35 33 27 14 31
13 9 8 15 26 16 14 3 24 12 11 7 2 25 19 17 18 23 22 21 28
28 7 27 35 34 29 8 30 25 10 23 5 22 16 26 6 13 20 33 32 3
7 11 21 9 20 5 17 13 34 35 2 12 18 26 1 10 23 19 4 30 16
19 4 17 22 3 32 23 14 16 28 15 33 25 27 21 26 31 29 1 5 11
34 17 31 25 4 10 6 7 1 33 13 35 29 30 27 2 5 3 32 28 19
4 6 14 19 15 2 18 5 17 16 12 20 33 3 9 21 24 22 7 8 26
22 26 9 1 18 13 28 17 32 2 30 15 34 14 25 27 21 24 20 23 33
5 20 2 18 6 35 15 16 12 17 32 14 11 8 29 25 9 10 31 33 24
25 14 24 7 12 21 27 18 11 26 10 3 23 22 16 20 19 15 29 31 9
16 35 11 12 28 3 33 26 30 18 19 25 27 24 34 31 1 4 17 2 6
8 5 1 3 31 27 35 15 18 9 4 11 6 23 14 19 20 21 13 10 29
10 23 34 29 1 24 13 21 6 11 27 28 26 31 20 15 22 8 30 18 32
6 32 3 2 5 4 1 22 8 21 14 10 13 35 12 7 11 34 28 29 30

A T A(70, 12, 44, 3, 12 : 15 × 56): — See [21]

5 22 36 18 40 6 39 1 21 13 19 4 12 32 33 9 35 15 8 24 7 23 17 30 16
24 40 31 26 33 36 10 11 37 5 14 23 2 19 13 18 7 22 34 17 8 9 25 20 1
34 1 2 32 35 23 15 25 16 27 36 24 18 12 14 6 10 38 37 8 20 3 9 21 19
21 6 10 2 25 17 37 20 7 22 16 3 4 28 35 39 31 33 9 38 13 24 19 15 11
31 29 3 39 38 22 18 40 4 17 5 12 25 34 20 10 32 7 11 16 23 8 14 6 21
36 28 33 22 23 14 29 13 9 10 35 20 27 5 2 12 40 6 39 11 3 21 32 26 24
4 25 30 3 34 1 7 24 14 36 22 37 16 33 15 29 13 12 23 40 28 31 27 10 6
28 5 7 37 6 4 23 8 26 21 2 35 24 25 38 36 14 32 13 34 30 29 15 11 17
1 8 9 24 7 37 38 30 39 15 3 26 5 21 29 35 11 31 33 14 12 18 22 25 27
8 32 23 4 9 28 12 38 2 40 34 15 11 39 22 31 21 19 27 30 25 13 10 1 26
10 16 32 8 27 39 40 19 25 3 11 17 36 14 1 15 18 28 7 35 2 26 4 33 29
27 9 29 30 4 11 2 36 20 37 31 40 33 3 21 17 6 8 15 12 18 28 5 16 34
7 35 17 34 19 9 5 3 36 26 30 11 38 1 18 13 37 20 32 10 22 4 29 28 12
35 31 38 10 5 18 19 6 12 8 39 1 13 37 4 26 30 14 29 33 27 16 20 23 2
20 2 1 6 3 27 28 39 30 38 15 31 32 13 40 34 19 26 16 9 17 14 24 5 7
39 37 21 33 26 38 24 29 40 16 23 32 31 17 34 25 27 36 20 28 35 19 30 18 22

A T A(48, 11, 22, 5, 11 : 16 × 33):

37 44 41 17 4 3 39 8 25 11 6 23 38 2 22 31 14 26 43 28 34 12 21 46 18 1 29 7 32 35 16 9 42
9 35 28 8 40 21 32 15 24 44 2 12 34 6 20 11 47 45 13 29 16 25 18 48 36 30 17 42 39 3 19 22 41
10 5 18 32 38 1 23 13 19 30 29 39 8 33 26 44 25 2 42 35 12 3 36 17 7 24 27 43 47 40 9 4 22
45 14 43 6 19 41 12 1 35 40 46 30 32 21 15 5 4 8 31 39 20 22 23 13 24 17 26 29 16 44 27 48 38
35 8 36 33 46 17 10 7 21 9 13 41 11 31 37 32 15 43 24 20 38 26 30 47 44 2 4 14 28 12 25 45 19
38 25 46 27 36 9 31 10 26 41 47 42 39 34 17 40 7 19 48 12 14 23 28 18 3 21 30 45 5 4 8 6 20
41 28 27 14 3 26 1 11 39 23 37 15 6 24 35 48 18 5 4 40 25 20 44 31 8 34 19 9 13 33 43 36 2
5 40 22 46 11 15 36 9 38 31 42 4 47 20 39 37 29 12 34 48 44 21 8 33 26 10 16 13 2 18 32 14 27
23 46 2 36 15 47 48 17 11 29 19 16 4 5 7 24 21 34 9 30 45 27 37 22 31 39 25 44 14 10 3 1 35
18 42 9 35 32 28 43 6 36 47 5 14 27 23 12 17 24 29 3 33 1 11 38 45 46 37 15 34 40 31 21 13 30
29 22 5 41 7 48 28 16 33 10 17 24 45 8 36 42 40 11 20 4 23 14 35 43 1 18 34 19 26 21 37 32 47
15 10 24 48 34 22 2 19 46 16 23 33 28 7 27 12 38 37 35 9 40 29 13 8 42 26 31 41 45 6 47 25 1
32 15 45 3 22 44 42 14 6 26 28 37 10 9 43 27 48 38 17 11 2 24 16 23 20 40 33 39 7 19 46 30 18
20 30 16 2 23 5 21 12 42 43 4 47 44 32 34 7 6 3 10 46 33 13 48 25 15 41 18 27 35 45 1 26 11
39 43 4 29 41 33 15 5 16 36 20 8 1 22 6 25 2 30 38 7 17 10 27 11 45 13 28 21 3 37 40 42 31
25 34 12 10 13 38 19 18 5 6 44 3 24 30 47 41 43 48 16 1 36 28 7 39 29 46 32 33 31 22 20 37 14

A T A(60, 12, 33, 4, 12 : 16 × 45): — See [21]