% A LaTeX file for a three page document
%
\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\setlength{\textwidth}{6.2in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\topmargin}{0pt}
\hyphenpenalty=1000
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000),
\#N5\hfill}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\bibliographystyle{plain}
\title{\textbf{A construction method for complete sets
of mutually orthogonal frequency squares}}
\author{V\ C\ Mavron\\
Department of Mathematics,\\
University of Wales,\\
Aberystwyth, SY23 3BZ\\
U.K.\\
{\small\texttt vcm@aber.ac.uk}\\
{Submitted: May 17, 2000; Accepted: August 22, 2000.}
}
\date{}
\begin{document}
\thispagestyle{empty}
\maketitle
\begin{abstract}
A construction is described for combining affine designs with complete sets of
mutually orthogonal frequency squares to produce other complete sets.
\par\medskip
\noindent
{{\em Key words\/}: Matrices, orthogonal arrays, Latin squares, affine designs.
\hfill}\\
{{\em AMS subject classifications\/}: Primary 05B20, Secondary 05B05, 05B15.}
\end{abstract}
\section{Introduction}
A \emph{frequency square }$M$ of type $F(n;\lambda)$ is an $n\times n$ matrix
over an $m$-set $S$, where $n=\lambda m$, such that every element of $S$
occurs exactly $\lambda$ times in each row and each column of $M$. When
$\lambda=1$, $F$ is a latin square.
Two frequency squares of the same type over $S$ are \emph{orthogonal} if, when
one is superimposed on the other, each element of $S\times S$ appears
$\lambda^{2}$ times. These definitions accord with those in
\cite[Chap.20]{CD},
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;\lambda)$ is a \emph{complete set} of type $F(n;\lambda)$.
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
\cite{L}
(see also IV.20.8(3) in
\cite{CD}),
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
\break
2-$(v,k,\lambda)$ design, with $v=km$, $\lambda=(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 $\mu=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$.
\section{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$.
\begin{theorem}
Suppose there exists an $AD(k,m)$ and a complete set of MOFS of type
$F(km\lambda;\lambda)$. Then there exists a complete set MOFS of type
%%\newline
$F(km\lambda;k\lambda)$.
\end{theorem}
\begin{proof}
Let $\Gamma$ be an $AD(k,m)$. Then $\Gamma$ has exactly $km$ points. Therefore
we can assume the given complete set is defined over the point set of $\Gamma$.
Let $C$ be any of the $(km-1)/(m-1)$ parallel classes of $\Gamma$ and $F$ be
any of the type $F(km\lambda;\lambda)$ frequency squares. Then we define as
follows a $km\lambda\times km\lambda$ frequency square $M$.
If $1\leq i,j\leq km\lambda$ and $F_{ij}=\alpha$, where $\alpha$ is a point of
$\Gamma$, let $C_{\beta}$ be the unique block of $C$ on $\alpha$ in $\Gamma$,
where $1\leq\alpha\leq m$. Then we define $M_{ij}=\beta$.
To show $M$ is a frequency square, let $i$ $(1\leq i\leq km\lambda)$ and
$\beta$ $(1\leq\beta\leq m)$ be given. There are $k$ points $\alpha$ of
$\Gamma$ on $C_{\beta}$ and then, for each such $\alpha$, there are $\lambda$
values of $j$ for which $F_{ij}=\alpha$
(since $F$ is an $F(km\lambda;\lambda)$ frequency square).
Hence $\beta$ occurs exactly $k\lambda$ times in any row of $M$; and this is
also true for columns by a similar argument. Therefore $M$ is a type
$F(km\lambda;k\lambda)$ square.
Next we show that by varying $C$ and $F$ we obtain a complete set of MOFS.
Let $C^{\prime}$ be a parallel class of $\Gamma$ and $F^{\prime}$ any of the
given type $F(km\lambda;\lambda)$ frequency squares. Let $M^{\prime}$ be the
corresponding type $F(km\lambda;k\lambda)$ frequency squares defined as before.
Assume $M\neq M^{\prime}$. Then we show that $M$ and $M^{\prime}$ are
orthogonal. Let $1\leq\beta,\beta^{\prime}\leq m$. We count that number of
order pairs $i,j$ for which $M_{ij}=\beta$ and
$M_{ij}^{\prime}=\beta^{\prime}$.
First consider the case $F\neq F^{\prime}$. Let $\alpha$ be any of the $k$
points on $C_{\beta}$ and $\alpha^{\prime}$ any point on $C_{\beta}^{\prime}$.
Since $F,F^{\prime}$ are orthogonal, there are $\lambda^{2}$ ordered pairs
$i,j$ such that $F_{ij}=\alpha$ and $F_{ij}^{\prime}=\alpha^{\prime}$. Hence
there are $k^{2}\lambda^{2}$ ordered pairs $i,j$ for which $M_{ij}=\beta$ and
$M_{ij}^{\prime}=\beta^{\prime}$.
Next consider the case $F=F^{\prime}$. Then $C\neq C^{\prime}$. Choose
$\alpha$ to be any of the $k/m$ points in the intersection of $C_{\alpha}$ and
$C_{\alpha}^{\prime}$. Then there are exactly $km\lambda^{2}$ ordered pairs
$i,j$ for which $F_{ij}=\alpha$, since $\alpha$ occurs $\lambda$ times in each
row of $F$. For such a pair $i,j$ it follows that $M_{ij}=\beta$ and
$M_{ij}^{\prime}=\beta^{\prime}$; so there are exactly $km\lambda^{2}\times
k/m=k^{2}\lambda^{2}$ such pairs.
It follows that $M$ and $M^{\prime}$ are orthogonal.
Now there are $(km-1)/(m-1)$ possible parallel classes and $(km\lambda
- -1)^{2}/(km-1)$ possible $F$. Hence we have $(km\lambda-1)^{2}/(m-1)$
frequency squares $M$; that is, a complete set of type $F(km\lambda;k\lambda
)$, as required.
\end{proof}
\begin{corollary}
\ 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)$.
\end{corollary}
\begin{proof}
This is the case $\lambda=1$ of the theorem.
\end{proof}
\begin{remark}
Laywine proves the above corollary
(see \cite[IV.20.8(3)]{CD},\cite{L} or \cite{LM})
for the case when $k$ is a power of $m$.
\end{remark}
\begin{corollary}
If there exists an affine plane of order $m$ and complete set of type
$F(\lambda m^{2};\lambda)$, then there exists a complete set of type
$F(\lambda m^{2};\lambda m)$.
\end{corollary}
\begin{proof}
This is the special case $k=m$ of the theorem.
\end{proof}
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.
\begin{corollary}
If there is a Hadamard matrix of order $2k$ and a complete set of type
$F(2k\lambda;\lambda)$, then there exists a complete set of type
$F(2k\lambda;k\lambda)$.
\end{corollary}
\begin{proof}
This follows from the theorem, putting $m=2$ and noting the well known result
\cite[IV.24.8, p371]{CD}
that an $AD(k,2)$ exists if and only if there exists a Hadamard matrix of
order $2k$.
\end{proof}
By a result of Federer and Mandeli
\cite[IV.20.9, p355]{CD},
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\lambda;k\lambda)$ complete set without requiring
the existence of a Hadamard matrix of order $2k\lambda$. (Though of course
such a matrix will exist if the Hadamard conjecture is true.)
\begin{thebibliography}{9}
\bibitem{CD}C\ J\ Colbourn, J\ H\ Dinitz (eds.):\ The CRC Handbook of
Combinatorial Designs (CRC Press, 1996).
\bibitem{L}C\ F\ Laywine, A geometric construction for sets of mutually
orthogonal frequency squares, Utilitas Math. \textbf{35} (1989), 95-102.
\bibitem{LM}C\ F\ Laywine, G\ L\ Mullen: Discrete Mathematics Using Latin
Squares (Wiley, 1998).
\end{thebibliography}
\end{document}