Double Arrays, Triple Arrays, and Balanced Grids with v = r + c − 1

John P. McSorley, Department of Mathematics, Southern Illinois University, Carbondale. IL 62901-4408. mcsorley60@hotmail.com

Abstract

In Theorem 6.1 of [3] it was shown that, when v = r + c − 1, every triple array T A(v, k, λ_{rr}, λ_{cc}, k : r × c) is a balanced grid BG(v, k, k : r×c). Here we prove the converse of this Theorem. Our final result is: Let v = r + c − 1. Then every triple array is a T A(v, k, c − k, r − k, k : r × c) and every balanced grid is a BG(v, k, k : r × c), and they are equivalent.

Keywords: arrays, double arrays, triple arrays, balanced grids, designs

1 Introduction, Main Result

We briefly introduce the main players: arrays, double arrays, triple arrays, and balanced grids. See [3] for more details.

Consider a rectangle with r rows and c columns, in which each cell contains exactly one element from the set V = {1, 2, …, v}. Suppose that the rectangle is binary, i.e., every row contains distinct elements and every column contains distinct elements. Further, suppose that the rectangle is equireplicate, i.e., every element of V occurs exactly k times in the rectangle for some k ≥ 1. Call such a rectangle a r × c array based on the set V, and denote it by A = A(v, k : r × c).

An array A is a double array if it satisfies the following two 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.

Such an array is denoted by DA(v, k, λ_{rr}, λ_{cc} : r × c). Suppose further that A satisfies the third property:

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

then A is called a triple array, a T A(v, k, λ_{rr}, λ_{cc}, λ_{rc} : r × c).

Now consider a pair of distinct elements x ∈ V and y ∈ V. If both occur in the same row of A then we say that the pair {x, y} occurs in this row, similarly for columns. Suppose that {x, y} occurs in r_{1} rows of A and in c_{1} columns of A, then we say that it occurs μ_{{x,y}} = r_{1} + c_{1} times in the grid A. We call A a balanced grid if there is a constant μ such that μ = μ_{{x,y}} for every x and y. We denote such a balanced grid by BG(v, k, μ : r × c).

In Theorem 6.1 of [3] it was shown that, when v = r + c − 1, every triple array T A(v, k, λ_{rr}, λ_{cc}, k : r × c) is a balanced grid BG(v, k, k : r × c). It was then stated that examples to the converse of this Theorem had been found. In Theorem 2.5 of this paper we prove the converse of Theorem 6.1 of [3]. Our main result (Theorem 2.6) is: Let v = r + c − 1. Then every triple array is a T A(v, k, c − k, r − k, k : r × c) and every balanced grid is a BG(v, k, k : r × c), and they are equivalent.

Finally, we restate a conjecture of Agrawal [1] concerning symmetric balanced incomplete block designs and triple arrays.

2 For v=r+c-1, TA and BG are equivalent

We work mainly with the variables r, c, and k; writing other variables in terms of these three variables, see Theorems 2.2, 3.1, and 4.1 of [3].

v = \frac{rc}{k}, λ_{rr} = \frac{c(k − 1)}{r − 1}, λ_{cc} = \frac{r(k − 1)}{c − 1}, λ_{rc} = k, μ = \frac{k^{2}(r + c − 2)}{rc − k}. (1)

When v = r + c − 1 if values of the two parameters r and c are given then all parameters in (1) can be expressed in terms of them, and so are ‘forced’. But we prefer to keep k in our formulae:

Lemma 2.1

(i) In a triple array T A(v, k, λ_{rr}, λ_{cc}, k : r×c) the following are equivalent: v = r + c − 1 and λ_{rr} = c − k and λ_{cc} = r − k.

(ii) In a balanced grid BG(v, k, μ : r × c) we have v = r + c − 1 if and only if μ = k.

Proof. (i) If v = r + c − 1 then c = v − r + 1. Then ck = vk − rk + k = rc − rk + k, and so ck − c = rc − rk − c + k = (r − 1)(c − k). But, from (1), λ_{rr} = \frac{c(k−1)}{r−1}, and so λ_{rr} = c−k. The converse is given by working backwards. Hence v = r + c − 1 if and only if λ_{rr} = c − k. Similarly we can prove that v = r + c − 1 if and only if λ_{cc} = r − k. (ii) Suppose that v = r + c − 1. Then, from (1), v = \frac{rc}{k} = r + c − 1. So \frac{rc}{k} − 1 = \frac{rc−k}{k} = r + c − 2. Now (1) gives μ = k. The converse is given by working backwards.

The following Corollary was not explicitly stated in [3].

Corollary 2.2 When v = r + c − 1 every triple array is a T A(v, k, c − k, r − k, k : r × c), and every balanced grid is a BG(v, k, k : r × c).

Matching BIBD’s

Let D_{1} be a (v_{1}, b, r_{1}, κ, λ_{1}) − BIBD based on a v_{1}-set V_{1}, and D_{2} a (v_{2}, b, r_{2}, κ, λ_{2}) − BIBD based on a v_{2}-set V_{2}, with v_{1}v_{2} = bκ. Let the b blocks of D_{1} be arranged in any fixed order, and let the κ elements in each block be arranged in any fixed order. Then D_{1} and D_{2} are matching if the b blocks of D_{2}, and the κ elements within each block, can be arranged so that when D_{2} is superimposed onto D_{1} then each of the v_{1}v_{2} pairs from V_{1} × V_{2} appears exactly once amongst the bκ pairs covered. See Preece [4] Section 6, definition (b), for an equivalent definition of matching BIBD’s. Such superimpositions are generally known as Graeco-Latin designs.

Example 1 Two matching BIBD’s: a (5, 10, 6, 3, 3) − BIBD based on {R_{1}, R_{2}, R_{3}, R_{4}, R_{5}} and a (6, 10, 5, 3, 2)−BIBD based on {C_{1}, C_{2}, C_{3}, C_{4}, C_{5}, C_{6}}, and their superimposition.

\begin{matrix}R_{1} & R_{2} & R_{3} & C_{1} & C_{4} & C_{5} & R_{1}C_{1} & R_{2}C_{4} & R_{3}C_{5} \\ R_{1} & R_{3} & R_{5} & C_{2} & C_{3} & C_{5} & R_{1}C_{2} & R_{3}C_{3} & R_{5}C_{5} \\ R_{1} & R_{3} & R_{4} & C_{3} & C_{5} & C_{6} & R_{1}C_{3} & R_{3}C_{6} & R_{4}C_{5} \\ R_{1} & R_{4} & R_{5} & C_{1} & C_{3} & C_{4} & R_{1}C_{4} & R_{4}C_{3} & R_{5}C_{1} \\ R_{1} & R_{2} & R_{5} & C_{1} & C_{5} & C_{6} & R_{1}C_{5} & R_{2}C_{1} & R_{5}C_{6} \\ R_{1} & R_{2} & R_{4} & C_{2} & C_{4} & C_{6} & R_{1}C_{6} & R_{2}C_{2} & R_{4}C_{4} \\ R_{2} & R_{4} & R_{5} & C_{3} & C_{4} & C_{6} & R_{2}C_{3} & R_{4}C_{6} & R_{5}C_{4} \\ R_{2} & R_{3} & R_{4} & C_{2} & C_{4} & C_{5} & R_{2}C_{5} & R_{3}C_{4} & R_{4}C_{2} \\ R_{2} & R_{3} & R_{5} & C_{1} & C_{2} & C_{6} & R_{2}C_{6} & R_{3}C_{1} & R_{5}C_{2} \\ R_{3} & R_{4} & R_{5} & C_{1} & C_{2} & C_{3} & R_{3}C_{2} & R_{4}C_{1} & R_{5}C_{3} \end{matrix}

Block structures R^{⊥}, C^{⊥}, and S

Let A be an arbitrary array A(v, k : r × c). Label the r rows of A with R_{1}, R_{2}, …, R_{r}, and the c columns with C_{1}, C_{2}, …, C_{c}.

Let R = {R_{1}, R_{2}, …, R_{r}} be the block structure composed of the r rows of A. Similarly, let C = {C_{1}, C_{2}, …, C_{c}} be the block structure composed of the c columns of A.

For any x ∈ V let R_{x}^{⊥} = {R_{i} | x ∈ R_{i}}. Then R^{⊥} = {R_{x}^{⊥} | x ∈ V } is the dual of R and is a block structure based on the set {R_{1}, R_{2}, …, R_{r}} with v blocks each of size k. Similarly, for any x ∈ V let C_{x}^{⊥} = {C_{j} | x ∈ C_{j}}. Then C^{⊥} = {C_{x}^{⊥} | x ∈ V } is the dual of C and is a block structure based on the set {C_{1}, C_{2}, …, C_{c}} with v blocks each of size k.

Define S_{x} = R_{x}^{⊥} ∪ C_{x}^{⊥} for every x ∈ V, and let S be the block structure {S_{x} | x ∈ V }.

By definition of a double array and matching BIBD’s we have (compare Lemma 2.1 of [3]):

Lemma 2.3 Let A be an arbitrary array A(v, k : r × c). Then A is a double array DA(v, k, λ_{rr}, λ_{cc} : r × c) if and only if R^{⊥} is a (r, v, c, k, λ_{rr}) − BIBD and C^{⊥} is a (c, v, r, k, λ_{cc}) − BIBD, and R^{⊥} and C^{⊥} are matching.

When A is a double array we call R^{⊥} its BIBD_{R} and C^{⊥} its BIBD_{C}.

Example 2 A double array DA(10, 3, 3, 2 : 5×6) whose matching BIBD_{R} and BIBD_{C} were given above in Example 1.

C_{1} C_{2} C_{3} C_{4} C_{5} C_{6}
R_{1} 1 2 3 4 5 6
R_{2} 5 6 7 1 8 9
R_{3} 9 10 2 8 1 3
R_{4} 10 8 4 6 3 7
R_{5} 4 9 10 7 2 5

Before the next Theorem, we need the following result of Ryser [6], Chapter 8, Theorem 2.2:

Let B be an incidence structure based on a v-set with v blocks each of size k, in which any two distinct blocks intersect in the same number λ of elements. Then B is a (v, k, λ) − SBIBD.

Compare the following Theorem with Theorem 5.2 of [3].

Theorem 2.4 Let G be a BG(v, k, μ : r × c) with v = r + c − 1. Then there exists a (v + 1, r, r − k)-SBIBD.

Proof. Recall the definitions of the block structures R^{⊥} and C^{⊥} above. Let B_{0} = \{R_{1}, R_{2}, …, R_{r}\}. For each x ∈ V put \overline{R}_{x}^{⊥} = B_{0}\R_{x}^{⊥}, then |\overline{R}_{x}^{⊥}| = r − k.

Let B_{x} = \overline{R}_{x}^{⊥} ∪ C_{x}^{⊥} for each x ∈ V. Then |B_{x}| = (r − k) + k = r. Now consider the block structure B = {B_{x}|x ∈ V } ∪ {B_{0}}. It is based on the r + c = v + 1 elements from R ∪ C = {R_{1}, R_{2}, …, R_{r}, C_{1}, C_{2}, …, C_{c}} and has v + 1 blocks each of size r. We now show that B is the required (v + 1, r, r − k) − SBIBD.

Now G is a BG in which every pair {x, y} occurs μ = k (Lemma 2.1(ii)) times, so |S_{x}^{⊥} ∩ S_{y}^{⊥}| = |R_{x}^{⊥} ∩ R_{y}^{⊥}| + |C_{x}^{⊥} ∩ C_{y}^{⊥}| = k. We have:

|B_{x} ∩ B_{y}| = |\overline{R}_{x}^{⊥} ∩ \overline{R}_{y}^{⊥}| + |C_{x}^{⊥} ∩ C_{y}^{⊥}|
= |\overline{R}_{x}^{⊥}| + |\overline{R}_{y}^{⊥}| − |\overline{R}_{x}^{⊥} ∪ \overline{R}_{y}^{⊥}| + |C_{x}^{⊥} ∩ C_{y}^{⊥}|
= (r − k) + (r − k) − |\overline{R_{x}^{⊥} ∩ R_{y}^{⊥}}| + |C_{x}^{⊥} ∩ C_{y}^{⊥}|
= 2r − 2k − (r − |R_{x}^{⊥} ∩ R_{y}^{⊥}|) + |C_{x}^{⊥} ∩ C_{y}^{⊥}|
= r − 2k + (|R_{x}^{⊥} ∩ R_{y}^{⊥}| + |C_{x}^{⊥} ∩ C_{y}^{⊥}|)
= r − 2k + k = r − k.

Also, for all x ∈ V, we have |B_{x} ∩ B_{0}| = r − k. Thus any two distinct blocks of B intersect in r − k elements. So, from Ryser’s result above, B is a (v + 1, r, r − k) − SBIBD.

Next is the converse to Theorem 6.1 of [3]:

Theorem 2.5 Let v = r+c−1. Every BG(v, k, k : r×c) is a T A(v, k, c− k, r − k, k : r × c).

Proof. Let G be a BG(v, k, k : r×c). Recall from Theorem 2.4 above that B is a (v+1, r, r−k)−SBIBD. The construction of B from R^{⊥} and C^{⊥} gives: Firstly, R^{⊥} is the complement of the derived design of B with respect to block B_{0}, hence R^{⊥} is a (r, v, c, k, c − k) − BIBD. Secondly, C^{⊥} is the residual design of B with respect to B_{0}, hence C^{⊥} is a (c, v, r, k, r −k)−BIBD. Since R^{⊥} and C^{⊥} are also constructed from an array, they are matching. Hence, via Lemma 2.3, G is a double array, a DA(v, k, c − k, r − k : r × c).

Consider any pair {R_{i}, C_{j}}. Then C_{j} occurs r times in the first v blocks of B, and pair {R_{i}, C_{j}} occurs r − k times in these blocks. So, amongst the first v blocks of B, there are r − (r − k) = k blocks which do not contain R_{i} but do contain C_{j}. Hence, in S, there are k blocks containing pair {R_{i}, C_{j}}. Thus |R_{i} ∩ C_{j}| = k for every i and j, and so G is a triple array, a T A(v, k, c − k, r − k, k : r × c).

Using Theorem 6.1 from [3] and Corollary 2.2 above, we have:

Theorem 2.6 Let v = r + c − 1. Then every triple array is a T A(v, k, c − k, r − k, k : r × c) and every balanced grid is a BG(v, k, k : r × c), and they are equivalent.

Example 3 An array A, a A(10, 3 : 5 × 6), which is both a balanced grid BG(10, 3, 3 : 5 × 6) and a triple array T A(10, 3, 3, 2, 3 : 5 × 6). The three block structures shown are its BIBD_{R}, a (5, 10, 6, 3, 3)−BIBD; its BIBD_{C}, a (6, 10, 5, 3, 2) − BIBD; and B, a (11, 5, 2) − SBIBD.

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

R_{1} R_{2} R_{4}  C_{1} C_{3} C_{5}  R_{3} R_{5} C_{1} C_{3} C_{5}
R_{1} R_{3} R_{4}  C_{1} C_{2} C_{6}  R_{2} R_{5} C_{1} C_{2} C_{6}
R_{1} R_{2} R_{3}  C_{3} C_{4} C_{6}  R_{4} R_{5} C_{3} C_{4} C_{6}
R_{1} R_{2} R_{5}  C_{1} C_{2} C_{4}  R_{3} R_{4} C_{1} C_{2} C_{4}
R_{1} R_{3} R_{5}  C_{2} C_{3} C_{5}  R_{2} R_{4} C_{2} C_{3} C_{5}
R_{1} R_{4} R_{5}  C_{4} C_{5} C_{6}  R_{2} R_{3} C_{4} C_{5} C_{6}
R_{2} R_{4} R_{5}  C_{2} C_{3} C_{6}  R_{1} R_{3} C_{2} C_{3} C_{6}
R_{2} R_{3} R_{4}  C_{2} C_{4} C_{5}  R_{1} R_{5} C_{2} C_{4} C_{5}
R_{2} R_{3} R_{5}  C_{1} C_{5} C_{6}  R_{1} R_{4} C_{1} C_{5} C_{6}
R_{3} R_{4} R_{5}  C_{1} C_{3} C_{4}  R_{1} R_{2} C_{1} C_{3} C_{4}
R_{1} R_{2} R_{3} R_{4} R_{5}

Agrawal’s Conjecture

The second paragraph in the proof of Theorem 2.5 above is essentially Agrawal’s method of constructing a triple array T A(v, k, c−k, r−k, k : r×c) with v = r+c−1 from a (v+1, r, r−k)−SBIBD with k > 2, see Agrawal [1]. It seems worthwhile to restate his conjecture in terms of matching BIBD’s:

Let S be a (v_{s}, k_{s}, λ_{s}) − SBIBD with k_{s} − λ_{s} > 2. For any fixed block S_{0} let S_{der} denote the derived design of S with respect to S_{0}, and let S_{res} denote the residual design of S with respect to S_{0}.

Then the complement of S_{der} and S_{res} are matching.

An incorrect proof of this conjecture appeared in Raghavarao and Nageswararao [5], as was pointed out in Bailey and Heidtmann [2], and Wallis and Yucas [7]. It appears that this conjecture is still open.

If Agrawal’s conjecture is correct then any (v_{s}, k_{s}, λ_{s}) − SBIBD with k_{s} − λ_{s} > 2 gives rise to a T A(v_{s} − 1, k_{s} − λ_{s}, v_{s} − 2k_{s} + λ_{s}, λ_{s}, k_{s} − λ_{s} : k_{s} × (v_{s} − k_{s})), a triple array with ‘v = r + c − 1’.

References

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

[2] R.A.Bailey, P.Heidtmann. Personal communication.

[3] J.P.McSorley, N.C.K.Phillips, W.D.Wallis, J.L.Yucas. Double Arrays, Triple Arrays, and Balanced Grids, Designs, Codes, and Cryptography. Vol.35, (2005), pp.21–45.

[4] D.A.Preece. Non-orthogonal Graeco-Latin designs, Combinatorial Mathematics IV, Lecture Notes in Mathematics 560, Springer-Verlag, (1976), pp.7–26.

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

[6] H.Ryser. Combinatorial Mathematics, Carus Mathematical Monographs 14, Mathematical Association of America, (1963).

[7] W.D.Wallis, J.L.Yucas. Note on the construction of designs for the elimination of heterogeneity, Jour. Combin. Maths. Combin. Comput. Vol.46, (2003), pp.155–160.