A construction method for complete sets of mutually orthogonal frequency squares

V C Mavron Department of Mathematics, University of Wales, Aberystwyth, SY23 3BZ U.K.

vcm@aber.ac.uk

Submitted: May 17, 2000; Accepted: August 22, 2000.

Abstract

A construction is described for combining affine designs with complete sets of mutually orthogonal frequency squares to produce other complete sets.

Key words: Matrices, orthogonal arrays, Latin squares, affine designs. AMS subject classifications: Primary 05B20, Secondary 05B05, 05B15.

1 Introduction

A frequency square M of type F (n; λ) is an n×n matrix over an m-set S, where n = λm, such that every element of S occurs exactly λ times in each row and each column of M. When λ = 1, F is a latin square.

Two frequency squares of the same type over S are orthogonal if, when one is superimposed on the other, each element of S × S appears λ^{2} times. These definitions accord with those in [1, Chap.20], where can be found a survey of frequency squares.

A set of (n − 1)^{2}/(m − 1) mutually orthogonal frequency squares (MOFS) of type F (n; λ) is a complete set of type F (n; λ).

We shall describe a construction for complete sets of MOFS using another set of MOFS and an affine design. A special case is Laywine’s construction [2] (see also IV.20.8(3) in [1]), which uses a complete set of MOLS in place of the MOFS and the affine design has the parameters of the design of the points and hyperplanes of some affine geometry.

With the usual design theory notation, an affine design AD(k, m) is an affine 2-(v, k, λ) design, with v = km, λ = (k − 1)/(m − 1), whose blocks can be partitioned into r = (km − 1)/(m − 1) subsets of m blocks, called parallel classes, such that any two blocks from different parallel classes meet in exactly μ = k/m = k^{2}/v points.

Any AD(m, m) is an affine plane of order m. A classical theorem of Bose states that an affine plane of order m exists if and only if there exists a complete set of orthogonal frequency squares of type F (m; 1); that is, a complete set of mutually orthogonal latin squares (MOLS) of order m.

2 The construction

The construction that is described in the following theorem provides a way of generating complete sets of MOFS but assumes the existence of affine designs with suitable parameters. However, the known AD(k, m) designs have either m = 2 and 2k is the order of a Hadamard matrix, or else m is a prime power and k a power of m.

Theorem 1 Suppose there exists an AD(k, m) and a complete set of MOFS of type F (kmλ; λ). Then there exists a complete set MOFS of type F (kmλ; kλ).

Proof. Let Γ be an AD(k, m). Then Γ has exactly km points. Therefore we can assume the given complete set is defined over the point set of Γ.

Let C be any of the (km − 1)/(m − 1) parallel classes of Γ and F be any of the type F (kmλ; λ) frequency squares. Then we define as follows a kmλ × kmλ frequency square M.

If 1 ≤ i, j ≤ kmλ and F_{ij} = α, where α is a point of Γ, let C_{β} be the unique block of C on α in Γ, where 1 ≤ α ≤ m. Then we define M_{ij} = β.

To show M is a frequency square, let i (1 ≤ i ≤ kmλ) and β (1 ≤ β ≤ m) be given. There are k points α of Γ on C_{β} and then, for each such α, there are λ values of j for which F_{ij} = α (since F is an F (kmλ; λ) frequency square). Hence β occurs exactly kλ times in any row of M; and this is also true for columns by a similar argument. Therefore M is a type F (kmλ; kλ) square.

Next we show that by varying C and F we obtain a complete set of MOFS.

Let C′ be a parallel class of Γ and F′ any of the given type F (kmλ; λ) frequency squares. Let M′ be the corresponding type F (kmλ; kλ) frequency squares defined as before.

Assume M ≠ M′. Then we show that M and M′ are orthogonal. Let 1 ≤ β, β′ ≤ m. We count that number of order pairs i, j for which M_{ij} = β and M′_{ij} = β′.

First consider the case F ≠ F′. Let α be any of the k points on C_{β} and α′ any point on C′_{β}. Since F, F′ are orthogonal, there are λ^{2} ordered pairs i, j such that F_{ij} = α and F′_{ij} = α′. Hence there are k^{2}λ^{2} ordered pairs i, j for which M_{ij} = β and M′_{ij} = β′.

Next consider the case F = F′. Then C ≠ C′. Choose α to be any of the k/m points in the intersection of C_{α} and C′_{α}. Then there are exactly kmλ^{2} ordered pairs i, j for which F_{ij} = α, since α occurs λ times in each row of F. For such a pair i, j it follows that M_{ij} = β and M′_{ij} = β′; so there are exactly kmλ^{2} × k/m = k^{2}λ^{2} such pairs.

It follows that M and M′ are orthogonal.

Now there are (km − 1)/(m − 1) possible parallel classes and (kmλ − −1)^{2}/(km − 1) possible F. Hence we have (kmλ−1)^{2}/(m−1) frequency squares M; that is, a complete set of type F (kmλ; kλ), as required.

Corollary 2 If there exists an affine plane of order km (or equivalently a complete set of MOLS of order km) and an AD(k, m), then there exists a complete set of MOFS of type F (km; k).

Proof. This is the case λ = 1 of the theorem.

Remark 3 Laywine proves the above corollary (see [1, IV.20.8(3)],[2] or [3]) for the case when k is a power of m.

Corollary 4 If there exists an affine plane of order m and complete set of type F (λm^{2}; λ), then there exists a complete set of type F (λm^{2}; λm).

Proof. This is the special case k = m of the theorem.

It follows from Corollary 4 that a type F (m^{2}; m) complete set exists if m and m^{2} are orders of affine planes.

Corollary 5 If there is a Hadamard matrix of order 2k and a complete set of type F (2kλ; λ), then there exists a complete set of type F (2kλ; kλ).

Proof. This follows from the theorem, putting m = 2 and noting the well known result [1, IV.24.8, p371] that an AD(k, 2) exists if and only if there exists a Hadamard matrix of order 2k.

By a result of Federer and Mandeli [1, IV.20.9, p355], a type F (4t; 2t) complete set exists if there exists a Hadamard matrix of order 4t. Note that Corollary 5 asserts the existence of a type F (2kλ; kλ) complete set without requiring the existence of a Hadamard matrix of order 2kλ. (Though of course such a matrix will exist if the Hadamard conjecture is true.)

References

[1] C J Colbourn, J H Dinitz (eds.): The CRC Handbook of Combinatorial Designs (CRC Press, 1996).

[2] C F Laywine, A geometric construction for sets of mutually orthogonal frequency squares, Utilitas Math. 35 (1989), 95-102.

[3] C F Laywine, G L Mullen: Discrete Mathematics Using Latin Squares (Wiley, 1998).