Mathematical
Surveys
and
Monographs
Volume 175

Algebraic Design Theory

Warwick de Launey
Dane Flannery

American Mathematical Society

www.TechnicalBooksPDF.com


Mathematical
Surveys
and
Monographs
Volume 175

Algebraic Design Theory

Warwick de Launey
Dane Flannery

American Mathematical Society
Providence, Rhode Island

www.TechnicalBooksPDF.com

EDITORIAL COMMITTEE
Ralph L. Cohen, Chair
Michael A. Singer
Jordan S. Ellenberg
Benjamin Sudakov
Michael I. Weinstein
2010 Mathematics Subject Classification. Primary 05-02, 05Bxx, 05E18, 16B99, 20Dxx;
Secondary 05-04, 15A24, 16S99, 20B20, 20J06.

For additional information and updates on this book, visit
www.ams.org/bookpages/surv-175

Library of Congress Cataloging-in-Publication Data
De Launey, Warwick, 1958–
Algebraic design theory / Warwick De Launey, Dane Flannery.
p. cm. — (Mathematical surveys and monographs ; v. 175)
Includes bibliographical references and index.
ISBN 978-0-8218-4496-0 (alk. paper)
1. Combinatorial designs and configurations. I. Flannery, D. L. (Dane Laurence), 1965–
II. Title
QA166.25.D43
511 .6–dc23

2011
2011014837

Copying and reprinting. Individual readers of this publication, and nonprofit libraries
acting for them, are permitted to make fair use of the material, such as to copy a chapter for use

in teaching or research. Permission is granted to quote brief passages from this publication in
reviews, provided the customary acknowledgment of the source is given.
Republication, systematic copying, or multiple reproduction of any material in this publication
is permitted only under license from the American Mathematical Society. Requests for such
permission should be addressed to the Acquisitions Department, American Mathematical Society,
201 Charles Street, Providence, Rhode Island 02904-2294 USA. Requests can also be made by
e-mail to
c 2011 by the American Mathematical Society. All rights reserved.
The American Mathematical Society retains all rights
except those granted to the United States Government.
Printed in the United States of America.
∞ The paper used in this book is acid-free and falls within the guidelines

established to ensure permanence and durability.
Visit the AMS home page at />10 9 8 7 6 5 4 3 2 1

16 15 14 13 12 11

www.TechnicalBooksPDF.com


To Scott Godfrey MD, Richard Lam MD, and Mark Scholz MD
— Warwick de Launey

To my parents, Lois and Ivan
— Dane Flannery

www.TechnicalBooksPDF.com



www.TechnicalBooksPDF.com


Contents
Preface

ix

Chapter 1. Overview
1.1. What is a combinatorial design?
1.2. What is Algebraic Design Theory?
1.3. What is in this book?

1
1
1
2

Chapter 2. Many Kinds of Pairwise Combinatorial Designs
2.1. Orthogonality sets
2.2. Symmetric balanced incomplete block designs
2.3. Hadamard matrices
2.4. Weighing matrices
2.5. Balanced weighing matrices
2.6. Orthogonal designs
2.7. Complex Hadamard matrices
2.8. Complex generalized Hadamard matrices
2.9. Complex generalized weighing matrices
2.10. Generalized Hadamard matrices over groups
2.11. Balanced generalized weighing matrices

2.12. Generalized weighing matrices
2.13. Summary

7
7
9
11
12
13
14
16
18
19
19
22
23
24

Chapter 3. A Primer for Algebraic Design Theory
3.1. Groups
3.2. Monoids
3.3. Group actions
3.4. Rings
3.5. Matrices
3.6. Linear and related groups
3.7. Representations

27
27
34

35
39
41
42
44

Chapter 4. Orthogonality
4.1. How many rows can be pairwise Λ-orthogonal?
4.2. Non-trivial orthogonality sets
4.3. A big picture
4.4. Equivalence
4.5. Matrices, arrays, and designs

49
49
50
51
54
60

Chapter 5. Modeling Λ-Equivalence
5.1. A first look at the automorphism group
5.2. Ambient rings with a model for Λ-equivalence

63
63
65

v


www.TechnicalBooksPDF.com


vi

CONTENTS

5.3. Ambient rings for the familiar orthogonality sets

68

Chapter 6. The Grammian
6.1. Orthogonality as a Grammian property
6.2. Non-degeneracy
6.3. Gram completions and composition of orthogonality sets
6.4. The Gram Property and Λ-equivalence

71
71
72
73
74

Chapter 7. Transposability
7.1. The main problems
7.2. A functional approach to self-duality
7.3. Conjugate equivalence operations
7.4. A matrix algebra approach to transposability and self-duality
7.5. A different kind of transposable orthogonality set


77
77
78
80
80
82

Chapter 8. New Designs from Old
8.1. Composition
8.2. Transference

85
85
93

Chapter 9. Automorphism Groups
9.1. Automorphism groups of pairwise combinatorial designs
9.2. A class of generalized Hadamard matrices
9.3. A bound on the size of the automorphism group
9.4. Permutation automorphism groups
9.5. Automorphism groups of orthogonal designs
9.6. Expanded designs
9.7. Computing automorphism groups
9.8. The associated design
9.9. Associated designs and group divisible designs
9.10. An isomorphism for weighing matrices

99
99
100

103
105
106
108
112
114
116
117

Chapter
10.1.
10.2.
10.3.
10.4.
10.5.
10.6.
10.7.
10.8.

10. Group Development and Regular Actions on Arrays
Matrix preliminaries
Group-developed arrays
Regular embeddings
Difference sets and relative difference sets
Group ring equations and associates
Finding all associates of an array
An algorithm for solving Problems 10.2.3 and 10.2.4
Composition via associates

119

119
119
121
124
127
129
131
132

Chapter
11.1.
11.2.
11.3.

11. Origins of Cocyclic Development
First derivation
Second derivation
Cocycles for cyclic groups

135
135
140
142

Chapter
12.1.
12.2.
12.3.
12.4.


12. Group Extensions and Cocycles
Central extensions
Cocycles for product groups
Polycyclic presentations
Cocycles from collection in polycyclic groups

145
145
150
151
153

www.TechnicalBooksPDF.com


CONTENTS

12.5. Monomial representations and cocycles

vii

157

Chapter
13.1.
13.2.
13.3.
13.4.
13.5.


13. Cocyclic Pairwise Combinatorial Designs
The main definitions
Ambient rings with a central group
Some big problems
Central extensions of a design
Approaches to cocyclic designs

161
161
162
164
164
165

Chapter
14.1.
14.2.
14.3.
14.4.
14.5.
14.6.
14.7.
14.8.

14. Centrally Regular Actions
Cocyclic forms
A lesser expanded design
A pair of lifting homomorphisms
The lift
Translation

Centrally regular embeddings
Finding cocyclic forms
All the cocycles of a design

167
167
167
168
169
170
171
173
176

Chapter
15.1.
15.2.
15.3.
15.4.
15.5.
15.6.
15.7.
15.8.

15. Cocyclic Associates
Definition of cocyclic associates
The group ring equation for cocyclic associates
The familiar designs
Cocyclic designs and relative difference sets
Normal p-complements

Existence conditions for cocyclic Hadamard matrices
Cyclotomic rings and circulant complex Hadamard matrices
Composition of cocyclic associates

177
177
178
180
181
182
183
185
190

Chapter
16.1.
16.2.
16.3.
16.4.
16.5.

16. Special Classes of Cocyclic Designs
Cocyclic Hadamard matrices
Cocyclic weighing matrices
Cocyclic orthogonal designs
A cocyclic substitution scheme
Cocyclic complex Hadamard matrices

195
195

197
198
200
201

Chapter
17.1.
17.2.
17.3.

17. The Paley Matrices
Actions of 2-dimensional linear and semilinear groups
The Paley matrices and their automorphism groups
The regular actions

203
203
205
209

Chapter
18.1.
18.2.
18.3.
18.4.
18.5.

18. A Large Family of Cocyclic Hadamard Matrices
On the orders covered
A construction for prime powers congruent to 3 (mod 4)

A construction for prime powers congruent to 1 (mod 4)
Plug-in matrices
Proof of the main theorem and a generalization

215
215
216
218
220
221

Chapter 19. Substitution Schemes for Cocyclic Hadamard Matrices
19.1. General substitution schemes
19.2. Number-theoretic constraints

www.TechnicalBooksPDF.com

223
224
226


viii

CONTENTS

19.3.
19.4.
19.5.
19.6.

19.7.

Further results for group-developed plug-in matrices
Inverting action
Trivial action
Complementary pairs and the Cocyclic Hadamard Conjecture
Existence of group-developed complementary pairs

227
228
230
232
233

Chapter 20. Calculating Cocyclic Development Rules
20.1. Introduction to development tables
20.2. Development tables for abelian groups
20.3. Development tables revisited
20.4. Group cohomology
20.5. Constructing a free table
20.6. Group homology
20.7. Presentations and the Schur multiplier
20.8. Constructing a torsion table
20.9. Listing the elements of the second cohomology group
20.10. Another look at the Cocyclic Hadamard Conjecture

239
239
240
241

242
243
244
246
249
253
255

Chapter 21. Cocyclic Hadamard Matrices Indexed by Elementary Abelian
Groups
21.1. Motivation: indexing groups for the Sylvester matrices
21.2. The extension problem
21.3. Pure Hadamard collection cocycles
21.4. Bilinearity and Hadamard cocycles
21.5. Solution of the Hadamard cocycle problem

257
257
258
261
262
263

Chapter
22.1.
22.2.
22.3.
22.4.
22.5.
22.6.


22. Cocyclic Concordant Systems of Orthogonal Designs
Existence and uniqueness of cocyclic systems of OD(n; 1k )
A reduction
Solution of the reduced problem
Proof of Theorem 22.1.1
Removing the zeros
Examples

267
267
268
269
270
271
272

Chapter
23.1.
23.2.
23.3.
23.4.
23.5.

23. Asymptotic Existence of Cocyclic Hadamard Matrices
Complex sequences with zero aperiodic autocorrelation
Sets of Hermitian and skew-Hermitian circulant matrices
Sets of cocyclic signed permutation matrices
Existence of cocyclic complex Hadamard matrices
Concluding remarks


279
279
281
282
283
284

Bibliography

287

Index

295

www.TechnicalBooksPDF.com


Preface

Over the past several decades, algebra has become increasingly important in
combinatorial design theory. The flow of ideas has for the most part been from
algebra to design theory. Moreover, despite our successes, fundamental algebraic
questions in design theory remain open. It seems that new or more sophisticated
ideas and techniques will be needed to make progress on these questions. In the
meantime, design theory is a fertile source of problems that are ideal for spurring
the development of algorithms in the active field of computational algebra.
We hope that this book will encourage the investigation, by researchers at all
levels, of the algebraic questions posed by design theory. To this end, we provide

a large selection of the algebraic objects and applications to be found in design
theory. We also isolate a small number of problems that we think are important.
This book is a technical work that takes an unusually abstract approach. While
the approach is non-standard, it offers uniformity and enables us to highlight the
principal themes in such a way that they can be studied for their own sake, rather
than as a means to an end in special cases.
Everything begins with the following notion of orthogonality. Fix an integer
b > 1, and a non-empty set A (an ‘alphabet’) excluding zero. Let Λ be a set (an
‘orthogonality set’) of 2 × b arrays whose non-zero entries come from A. Much of
design theory is concerned with instances of the question
When does there exist a v × b array D such that every 2 × b
subarray of D is in Λ?
If D exists, then we say that its rows are pairwise Λ-orthogonal. Since essentially
combinatorial constraints are being placed on pairs of distinct rows, and because
of antecedents in the design of experiments, we call D a pairwise combinatorial
design, or PCD(v, Λ) for short. Chapter 2 describes families of widely-studied pairwise combinatorial designs. These designs are of interest in diverse fields including
electrical engineering, statistical analysis, and finite geometry.
This book develops a theory of square pairwise combinatorial designs, i.e., those
with v = b. For such designs we use the abbreviated notation PCD(Λ). Each of the
principal design-theoretic themes finds expression. The ‘ambient rings’ introduced
in Chapter 5 allow the free interplay of these themes: orthogonality, equivalence,
transposability, composition, transference, the proliferation of inequivalent designs,
the automorphism group, and links to group ring (norm) equations.
We pay particular attention to designs that possess a type of regular group
action. The acting group has a certain central subgroup Z, and the corresponding
2-cocycles with coefficients in Z have a significant influence on properties of the
design. Such a design is said to be cocyclic. This book contains a general theory for
ix

www.TechnicalBooksPDF.com



x

PREFACE

cocyclic pairwise combinatorial designs, plus many case studies. Along the way, we
encounter numerous classical designs and other well-known mathematical objects.
This is a book of ideas. It is our opinion that design theory is still—even now—
in its infancy. Thus, at this stage, ideas are more valuable than a compendium of
our present state of knowledge (which will keep growing rapidly beyond the confines
of a single volume). We have aimed to stimulate a creative reader rather than to
be encyclopedic.
With respect to cocyclic designs, the chief omissions from our book are Noboru
Ito’s work on Hadamard groups; and work by Kathy Horadam, her colleagues, and
her students.
Our book covers some of Ito’s results, but from a different perspective. Starting
in the 1980s, Ito produced a sequence of papers identifying regular group actions
on the expanded design of a Hadamard matrix. We are content to refer the reader
to those papers.
The first author, together with Horadam, founded the theory of cocyclic designs
in the early 1990s. Horadam and her school have since published many results
focusing on Hadamard, complex Hadamard, and generalized Hadamard matrices.
That material is covered in Horadam’s engaging book [87]. There one will find
topics such as shift equivalence of cocycles, equivalence classes of relative difference
sets, and the connection between generalized Hadamard matrices and presemifields,
that are not in this book.
We have tried to make the book as accessible as possible; we especially hope
that our treatment of the new ideas is welcoming and open-ended. Proofs are given
for nearly all results outside of the ‘algebraic primer’ chapter and the chapter on

Paley matrices. The book also contains a wealth of examples and case studies which
should persuade the reader that the concepts involved are worthy of pursuit.
Acknowledgments. We are indebted to K. T. Arasu, Robert Craigen, Kathy
Horadam, Hadi Kharaghani, S. L. Ma, Michael J. Smith, and Richard M. Stafford,
whose collaborations with the first author form the basis of several chapters and
sections.
We received useful advice and feedback from Joe Buhler, Alla Detinko, John
´ Cath´
Dillon, Al Hales, Kathy Horadam, Bill Kantor, Padraig O
ain, Dick Stafford,
Tobias Rossmann, and Jennifer Seberry. We are grateful to everyone for their help.
Many thanks are due as well to Sergei Gelfand and Christine Thivierge of the
American Mathematical Society, who guided us toward publication.
Finally, we thank Science Foundation Ireland for financial assistance from the
Research Frontiers Programme and Mathematics Initiative 2007 (grants 08/RFP/
MTH1331 and 07/MI/007).

www.TechnicalBooksPDF.com


On November 8, 2010, Warwick de Launey passed away after a long illness.
This book represents Warwick’s vision for Design Theory, gained from his years
of experience and achievement in the subject. It was my privilege to share in the
struggle to bring this vision to a wider audience.
The support of Warwick’s wife, Ione Rummery, was constant throughout our
writing of the book, and is deeply appreciated.
Warwick has dedicated the book to his doctors. Their care gave him the time
he needed to complete his vision.

Dane Flannery

March 27, 2011

www.TechnicalBooksPDF.com


www.TechnicalBooksPDF.com


CHAPTER 1

Overview
1.1. What is a combinatorial design?
An experimental scientist, statistician, or engineer often studies variables that
depend on several factors. Usually the experimenter has specific goals. She may
wish to eliminate (as far as possible) the effect of one factor, or to gauge the effects
of certain factors on the response variable. An experimental design is a schedule for
a series of measurements that efficiently meets these needs. For example, it may be
necessary to measure the weights of samples using a beam balance, or to compare
the yields of strains of a crop. In the former case, the estimates are most accurate
if the objects are weighed in combinations prescribed by a ‘weighing matrix’. In
the latter case, one can use a ‘balanced incomplete block design’.
These and other efficient designs obey simple combinatorial rules determined
by the setting. For example, a weighing matrix W(n, k) is an n × n matrix of 0s,
1s, and −1s such that
• each row and column contains exactly k non-zero entries,
• each pair of distinct rows has inner product equal to zero.
Also, a balanced incomplete block design BIBD(v, b, r, k, λ) is a v ì b matrix of 0s
and 1s such that
ã each row contains exactly r 1s,
• each column contains exactly k 1s,

• each pair of distinct rows has inner product equal to λ.
The realization that an optimal experimental design corresponds to a schedule
satisfying combinatorial rules, and that these designs may be used to save time
and money, led to the development of combinatorial design theory: the field of
mathematics concerned with finite objects, called combinatorial designs, obeying
specified combinatorial rules. The field grows apace. It now has major interactions
with coding theory, the study of sequences with autocorrelation properties, extremal
graph theory, and finite geometry. In this book, we focus on pairwise combinatorial
designs, each of which can be displayed as a square array whose rows taken pairwise
obey a combinatorial rule. These seem to be the most pervasive sort of design.
1.2. What is Algebraic Design Theory?
This book is about the emerging area that we call algebraic design theory: the
application of algebra and algebraic modes of reasoning in design theory.
The unresolved problems for pairwise combinatorial designs are not so easily
categorized. It seems that these problems are algebraic, and some of them may
be classed as a modern kind of Diophantine problem. In the situations where a
design corresponds to a solution of a group ring (or norm) equation, this judgment
1

www.TechnicalBooksPDF.com


2

1. OVERVIEW

is obviously correct; however, current algebraic techniques have not succeeded in
answering vital questions. Thus, we sometimes fall back on constructions that
supply us with examples and insights, but bypass the issue of extending current
techniques to the point where they can answer our questions.

1.3. What is in this book?
Chapters 3–16 and Chapter 20 establish a general abstract framework for pairwise combinatorial designs. Chapters 2, 17, 18, 19, 21, 22, and 23 are case studies.
1.3.1. Theory.
Algebraic essentials. Chapter 3 collects together basic algebraic definitions and
results. Parts of this chapter could be skipped by a reader with sufficient algebraic
background. More algebra is filled in as we proceed through the book.
Orthogonality. Chapter 2 introduces the notions of orthogonality set Λ and
pairwise combinatorial design PCD(Λ). We give many examples of familiar designs
that are PCD(Λ)s. Then Chapter 4 treats orthogonality in design theory at greater
length. A natural and important problem is to determine, for each orthogonality set
Λ, the maximum number of rows that are pairwise Λ-orthogonal. After discussing
this problem, we show how the lattice of orthogonality sets with a given alphabet
A may be studied using dual maps λ and δ between orthogonality sets and design
sets. We further show how Λ determines a range of Λ-equivalence operations. These
col
make up the group ΠΛ = Πrow
of row and column equivalence operations,
Λ , ΠΛ
and the group ΦΛ incorporating ΠΛ and the global equivalence operations. We
calculate ΠΛ and ΦΛ for all the designs from Chapter 2.
Ambient rings. Chapter 5 constructs several rings for the necessary matrix
algebra with designs. Let Λ be an orthogonality set with alphabet A. At the very
least, an ambient ring for Λ is just a ring containing A. More productively, it is
an involutory ring that also contains a row group R ∼
and a column group
= Πrow
Λ
col
C ∼
Π

in
its
group
of
units.
This
kind
of
ambient
ring
has
a matrix algebra
= Λ
model for Λ-equivalence. Section 5.2 constructs such a ring for any Λ. Later, in
col
Chapter 13, we show that a central group Z ∼
= Πrow
Λ ∩ ΠΛ may always be included
in R ∩ C. This extra structure is needed to model cocyclic development.
In Chapter 6 we consider Λ-orthogonality as a ‘Gram Property’: a (0, A)-array
D is a PCD(Λ) if and only if the Gram matrix DD∗ over an ambient ring R with
involution ∗ lies in a prescribed set GramR (Λ). Thus, although we start from a
definition of orthogonality shorn of algebra, we can in fact think of each PCD(Λ)
as a solution to a matrix ring equation.
Transposability. When does Λ-orthogonality, a pairwise condition on the rows
of an array, impose a pairwise condition on the array’s columns? In Chapter 7
we prove a theorem that answers this question for orthogonality sets like those in
Chapter 2, as well as the new case of generalized weighing matrices over a nonabelian group. We also describe transposable orthogonality sets outside the scope
of our theorem.
Composition and transference. Chapter 8 discusses the construction of new

designs from other (generally smaller) designs. This is an old and recurring theme.
The chapter divides into two sections: one on composition, the other on transference.
These ideas have some overlap, but it is convenient to have both at our disposal.
Designs may be composed by means of a substitution scheme, which consists
of a template array and a set of plug-in matrices that satisfy relations determined

www.TechnicalBooksPDF.com


1.3. WHAT IS IN THIS BOOK?

3

by the ambient ring for the template array. Since there is more than one choice of
ring, a single template array can be employed in different compositions.
Transference (a term of our coinage) is a vehicle for another recurring theme in
design theory. Here, existence of one kind of design implies the existence of another
kind of design. The connections can be quite unexpected, and, to our eyes, exhibit
no discernible common pattern. In Chapter 8 we give examples of transference.
These depend on special properties of the alphabet.
The automorphism group. Let R be any ambient ring with row group R ∼
=
col
∼
Πrow
and
column
group
C
Π

.
The
ordered
pair
(P,
Q)
of
monomial
matrices
=
Λ
Λ
P ∈ Mon(v, R) and Q ∈ Mon(v, C) is an automorphism of a PCD(Λ), D, if
P DQ∗ = D.
Then Aut(D) consists of all automorphisms of D. This group is independent of the
choice of ambient ring R.
In Chapter 9 we show that Λ-orthogonality bounds the size of Aut(D). As an
example, we find the automorphism groups for a class of generalized Hadamard
matrices. We show that, in this case, the bound is nearly sharp. We then find the
automorphism groups of some familiar orthogonal designs. Chapter 9 also presents
a simple depth-first backtrack algorithm for computing Aut(D).
Expanded and associated designs. Chapter 9 introduces the expanded design
and associated design of a pairwise combinatorial design. The associated design
of a balanced generalized weighing matrix is a group divisible design. If D is a
PCD(Λ) with ambient ring R, then the expanded design of D is the block matrix
E(D) = [ rDc]r∈R,c∈C
(the multiplication being done over R). The expanded design E(D) is used to
compute the automorphism group of D, and it figures prominently in the theory of
cocyclic development.
Group-developed arrays. Chapter 10 is about a host of concepts: regular actions

on square arrays, group development, associates, and group ring equations. The
(0, A)-array A is group-developed modulo a group G if its rows and columns can
be labeled with the elements of G so that, for some map h : G → {0} ∪ A,
A = [ h(xy)]x,y∈G .
This is equivalent to G acting regularly on A. For each such h we get an element
h(x)x
x∈G

of the group ring R[G] of G over an ambient ring R, called a G-associate of A.
Associates and group ring equations. In Chapter 10 we show how each Gassociate corresponds to a solution of a group ring equation with (0, A)-coefficients.
The particulars of the group ring equation depend on the orthogonality set Λ. So
the enumeration of group-developed PCD(Λ)s is equivalent to solving a group ring
equation. The connection is akin to that between pairwise combinatorial designs
and the Gram Property.
Associates and regular subgroups. We also show that the G-associates of an
array correspond to the conjugacy classes of regular subgroups in the automorphism
group of the array. We thereby gain a practical method to find all G-associates of
a PCD(Λ).

www.TechnicalBooksPDF.com


4

1. OVERVIEW

Associates and difference sets. Finally, in Chapter 10 we see how the Gassociates of designs give rise to (relative) difference sets.
Origins of cocyclic development. Chapter 11 elucidates the origins of cocyclic
design theory. We give two derivations, both of which begin with the notion of an
f -developed array

[ f (x, y)(g(xy))]x,y∈G ,
where f : G × G → Sym(A ∪ {0}) is a map fixing 0. The first derivation is in the
context of higher-dimensional designs. The second derivation springs from the fact
that a group-developed array A = [ g(xy)]x,y∈G is equivalent, via row and column
permutations, to the array [ g(axy)]x,y∈G obtained by developing the ath row of A
for any a. If one requires that an f -developed array is Λ-equivalent to the array
obtained by ‘f -developing’ the ath row of A, then f must be a 2-cocycle.
Cocycles. Let G and Z be groups, where Z is abelian. A map f : G × G → Z
such that
f (a, b)f (ab, c) = f (b, c)f (a, bc)
∀ a, b, c ∈ G
is a 2-cocycle. Chapter 12 contains an elementary exposition of 2-cocycles. The
discussion revolves around central short exact sequences
ι

π

1 −→ Z −→ E −→ G −→ 1.
Each map (apart from the first) is a group homomorphism whose kernel is the image
of the preceding homomorphism, and ι maps into the center of the extension group
E. We define a cocycle fι,τ : G × G → Z for each ‘transversal map’ τ : G → E;
moreover, every cocycle f : G × G → Z arises in this way. Chapter 12 discusses
cocycles of product groups, cocycles calculated by collection within a polycyclic
group, and monomial representations from a cocycle.
Cocyclic pairwise combinatorial designs. Chapter 13 formulates the theory of
cocyclic designs in terms of matrix algebra.
Let D be a PCD(Λ), where Λ has ambient ring R containing the row group
R, column group C, and central group Z. Then D is cocyclic if for some cocycle
f : G × G → Z there are monomial matrices P ∈ Mon(v, R), Q ∈ Mon(v, C) and a
map g : G → {0} ∪ A such that

D = P [ f (x, y)g(xy)]x,y∈G Q
over R. We say that f is a cocycle of D with indexing group G, and that f is a
Λ-cocycle. Any extension group for f is an extension group of D. Chapter 13 asks
1.3.1. Question. Given a PCD(Λ), D, what are all the cocycles of D?
1.3.2. Question. Given an orthogonality set Λ and a cocycle f : G × G → Z,
is there a PCD(Λ) with cocycle f ?
Four approaches to cocyclic designs are proposed.
1.3.3. For a given orthogonality set Λ,
(1) study the cocycles of known highly-structured PCD(Λ)s;
(2) determine Λ-cocycles via the extension group;
(3) determine Λ-cocycles via the indexing group;
(4) use composition to prove existence of PCD(Λ)s.
All these approaches are taken in the book.

www.TechnicalBooksPDF.com


1.3. WHAT IS IN THIS BOOK?

5

Centrally regular actions, cocyclic associates, and group ring equations. Chapters 14 and 15 set out more theory of cocyclic designs. We describe relationships
between cocyclic development, actions on the expanded design, cocyclic associates,
and group ring equations. Taken together, Chapters 14 and 15 are analogous to
Chapter 10.
Chapter 15 contains deeper material: an application of character theory to
the existence question for circulant complex Hadamard matrices, and Ito’s striking
results on allowable extension groups of cocyclic Hadamard matrices (in line with
part (2) of 1.3.3).
Cocyclic development tables. A development table displays all the ways in which

a cocyclic PCD(Λ) with indexing group G may be f -developed for some cocycle
f : G × G → Z. Chapter 20 explains how to compute development tables when G
is solvable.
The theory for familiar classes of designs. Chapter 16 is a ‘bridging’ chapter.
It refreshes some of the preceding theory in the book, with particular regard to
(complex) Hadamard matrices, balanced weighing matrices, and orthogonal designs.
Theoretical results needed for the case studies are here.
1.3.2. Practice.
Many pairwise combinatorial designs. In Chapter 2 we prove basic results about
familiar PCD(Λ)s, and state what is done in the book concerning those designs.
Paley matrices. The automorphism groups and all the regular actions for the
Paley conference and Hadamard matrices are described in Chapter 17. This case
study is extremely rich, yet it is tractable enough that we can answer Question 1.3.1
and carry out part (1) of the agenda 1.3.3.
A large family of cocyclic Hadamard matrices. Chapter 18 is a nice example of
part (4) of 1.3.3. Beginning with Paley matrices and applying plug-in techniques,
we obtain a large family of cocyclic Hadamard matrices, and thus many maximalsized relative difference sets with central forbidden subgroup of size 2.
Substitution schemes. Chapter 19 considers the cocyclic Hadamard matrices
with cocycle f : G × G → −1 obtained from a central short exact sequence
1 −→ −1 −→ E = L

π

N −→ G = K

N −→ 1,

where |K| = 4, π is the identity on N , and π(L) = K (this includes the atomic case
|G| = 4p, p > 3 prime). All such Hadamard matrices are defined by a substitution
scheme that, among other things, generalizes the Williamson construction. This

study is an instance of part (3) of 1.3.3.
Cocyclic Hadamard matrices and elementary abelian groups. A primary aim in
the study of cocyclic Hadamard matrices is to answer Question 1.3.2 for a given
group G. For most G this problem breaks up into a practicable algebraic component
and a difficult combinatorial component. However, if G is an elementary abelian
2-group then we show in Chapter 21 that the problem can be solved algebraically:
here, nearly every cocycle is a cocycle of a Sylvester Hadamard matrix. Chapter 21
is a good example of parts (2) and (3) of the agenda 1.3.3.
Systems of cocyclic orthogonal designs. Chapter 22 gives a complete algebraic
solution of the problem of classifying concordant systems {D1 , . . . , Dr } of cocyclic
orthogonal designs, where in each Di every relevant indeterminate appears exactly
once in each row and column. The approach is via the extension group, and there
is a strong reliance on Chapter 21.

www.TechnicalBooksPDF.com


6

1. OVERVIEW

Asymptotic existence of cocyclic Hadamard matrices. In the final chapter we
present a proof of the best known (to date) asymptotic existence result for cocyclic
Hadamard matrices. Our proof combines knowledge about the existence of complex
complementary sequences with ideas from Chapters 21 and 22.

www.TechnicalBooksPDF.com


CHAPTER 2


Many Kinds of Pairwise Combinatorial Designs
This chapter introduces the fundamental concepts of orthogonality set Λ and
pairwise combinatorial design PCD(Λ). We will see that many familiar designs are
PCD(Λ)s. The orthogonality set Λ in these cases is almost always transposable: D
is a PCD(Λ) if and only if the transpose D is a PCD(Λ). When this is so, we give
a justification of transposability.
Throughout the chapter we occasionally use terminology from design theory
and algebra without definition. That terminology will be defined later. We adopt
the conventions that i denotes a square root of −1, and if X is a matrix with entries
from the field C of complex numbers, then X ∗ is the complex conjugate transpose
of X. For a matrix X whose non-zero entries all lie in a group, X ∗ denotes the
transpose of the matrix obtained from X by inverting its non-zero entries. The
v × v identity matrix and the v × v matrix of 1s are denoted Iv , Jv respectively.
For natural numbers a and b, b = 0, we write a/b for the integer part of a/b, and
{a/b} = a/b − a/b for its fractional part.
The computer algebra system Magma [14] was used to generate many of the
examples in this chapter; these were output in a canonical form based on maximal
lexicographic ordering.
2.1. Orthogonality sets
Our first definition is the most important one in the book.
2.1.1. Definition. Let A be a non-empty finite set (an ‘alphabet’) such that
0 ∈ A. Let Λ be a set of 2 × b (0, A)-arrays that is closed under row and column
permutations; i.e., if
x1 x 2 · · · xb
y1 y2 · · · yb
is in Λ, then, for any permutation π of {1, 2, . . . , b},
y1
x1


y2
x2

···
···

yb
xb

xπ(1)
yπ(1)

and

xπ(2)
yπ(2)

···
···

xπ(b)
yπ(b)

are in Λ. Suppose also that no array in Λ has a repeated row. Then we call Λ an
orthogonality set. We say that (x1 , x2 , . . . , xb ) and (y1 , y2 , . . . , yb ) are Λ-orthogonal
if
x1 x 2 · · · x b
∈ Λ.
y1 y2 · · · yb
2.1.2. Remark. To begin with, 0 in Definition 2.1.1 is simply a special element

not contained in the alphabet A; but eventually we will define it as the zero of an
‘ambient’ ring for Λ.
7

www.TechnicalBooksPDF.com


8

2. MANY KINDS OF PAIRWISE COMBINATORIAL DESIGNS

We are interested in arrays whose rows are pairwise Λ-orthogonal.
2.1.3. Definition. Let Λ be an orthogonality set of 2 × b (0, A)-arrays. A
pairwise combinatorial design PCD(v, Λ) is a v × b array D such that all pairs of
distinct rows of D are Λ-orthogonal. If v = b, then we just write PCD(Λ).
Definitions 2.1.1 and 2.1.3 are entirely combinatorial. They are also very broad,
covering many different kinds of orthogonality and combinatorial designs.
2.1.4. Example. A Latin square of order n is an n × n array with entries from
A = {1, . . . , n} such that each element of A appears exactly once in each row and
column. In this case Λ is the set of 2 × n A-arrays with no repeated element in any
row or column.
2.1.5. Example. A binary error-correcting block code of length b, with v codewords and distance d, is equivalent to a v × b (0, 1)-array where every two distinct
rows differ in at least d columns. The alphabet is {1}, and the orthogonality set is
all 2 × b (0, 1)-arrays with at least d columns containing different entries.
2.1.6. Example. A set of v mutually orthogonal Latin squares of order n
corresponds to a (v + 2) × n2 array of entries from A = {1, . . . , n} such that every
pair of rows contains each ordered pair of elements of A exactly once. Here Λ is
the orbit of
1 1 ···
1 2 ···


···
···

1 2 2
n 1 2

···
···

2
n

n
1

···
···

n
2

n
n

under row and column permutations.
The following are mutually orthogonal Latin squares for n = 5.
1
2
3

4
5

2
3
4
5
1

3
4
5
1
2

4
5
1
2
3

5
1
2
3
4

1
3
5

2
4

2
4
1
3
5

3
5
2
4
1

4
1
3
5
2

5
2
4
1
3

1
4
2

5
3

2
5
3
1
4

3
1
4
2
5

4
2
5
3
1

5
3
1
4
2

1
5
4

3
2

2
1
5
4
3

3
2
1
5
4

4
3
2
1
5

5
4
3
2
1

We now form a 6 × 25 array A. The ith row of A for 1 ≤ i ≤ 4 is the concatenation
of rows 1, 2, 3, 4, 5 (in that order) of the ith Latin square. Adding the canonical
rows

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5
yields A as follows.

(2.1)

1
1
1
1
1
1

2
2
2
2
2
1

3
3
3
3
3
1

4
4
4

4
4
1

5
5
5
5
5
1

2
3
4
5
1
2

3
4
5
1
2
2

4
5
1
2
3

2

5
1
2
3
4
2

1
2
3
4
5
2

3
5
2
4
1
3

4
1
3
5
2
3


5
2
4
1
3
3

1
3
5
2
4
3

2
4
1
3
5
3

4
2
5
3
1
4

5
3

1
4
2
4

1
4
2
5
3
4

2
5
3
1
4
4

3
1
4
2
5
4

5
4
3
2

1
5

1
5
4
3
2
5

2
1
5
4
3
5

3
2
1
5
4
5

4
3
2
1
5
5


Notice that orthogonality with the last two rows ensures that each of the other
rows is the concatenation of the rows of a Latin square. Furthermore, rows i and
j = i being orthogonal for all i, j ∈ {1, 2, 3, 4} ensures that the Latin squares are
mutually orthogonal.

www.TechnicalBooksPDF.com


2.2. SYMMETRIC BALANCED INCOMPLETE BLOCK DESIGNS

9

2.1.7. Example. An orthogonal array of strength 2 and index λ is equivalent
to a v × λn2 array of entries from A = {1, . . . , n} such that, for all a, b ∈ A, every
pair of distinct rows contains exactly λ columns equal to [a, b] . The 6 × 25 array
(2.1) is an orthogonal array of strength 2 and index 1.
2.1.8. Example. An orthogonal array of strength 3 and index 1 is equivalent
to a v × n3 array of entries from A = {1, . . . , n} such that, for all a, b, c ∈ A, every
triple of distinct rows contains exactly one column equal to [a, b, c] .
In Example 2.1.8, the combinatorial nature of the array depends on how triples
rather than pairs of rows behave. Even here the notion of an orthogonality set
is pertinent, since every orthogonal array of strength 3 is an orthogonal array of
strength 2.
This book deals with square pairwise combinatorial designs. We discuss some
familiar PCD(Λ)s in the subsequent sections.
2.2. Symmetric balanced incomplete block designs
2.2.1. Definition. Let v, k, λ be integers, where v > k > λ ≥ 0. A symmetric
balanced incomplete block design SBIBD(v, k, λ) is a set of v subsets of size k, called
blocks, of a fixed set of v elements, called varieties, such that each unordered pair

of distinct varieties is in exactly λ blocks.
Symmetric balanced incomplete block designs are among the earliest kinds of
designs to have been studied. Of paramount concern is the existence question: for
which v, k, λ does there exist an SBIBD(v, k, λ)? Infinite families of these designs
are rare. Most of the families are constructed using other designs in this chapter;
see [92, 93, 94, 95, 96, 103, 104, 110].
We now recast the definition of SBIBD(v, k, λ). An incidence matrix for the
design is a v × v (0, 1)-matrix A = [ aij ] such that aij = 1 if and only if variety i is
contained in block j.
2.2.2. Example. We display incidence matrices for an SBIBD(11, 5, 2) and an
SBIBD(13, 4, 1).
⎡1 1 1 1 0 0 0 0 0 0 0 0 0⎤
⎡1 1 1 1 1 0 0 0 0 0 0⎤
1 0 0 0 1 1 1 0 0 0 0 0 0
⎢1 0 0 0 0 0 0 1 1 1 0 0 0⎥
1 1 0 0 0 1 1 1 0 0 0
⎢1 0 0 0 0 0 0 0 0 0 1 1 1⎥
⎢1 0 1 0 0 1 0 0 1 1 0⎥
⎥
⎢
⎢1 0 0 1 0 0 1 0 1 0 1⎥
⎢0 1 0 0 1 0 0 1 0 0 1 0 0⎥
⎢
⎥
⎢
⎥
⎢1 0 0 0 1 0 0 1 0 1 1⎥
⎢ 00 11 00 00 00 10 01 00 10 01 00 10 01 ⎥
⎢0 1 1 0 0 0 1 0 0 1 1⎥
⎥

⎢
⎢0 1 0 1 0 0 0 1 1 1 0⎥
⎢0 0 1 0 1 0 0 0 1 0 0 0 1⎥
⎢
⎥
⎢
⎥
⎢0 1 0 0 1 1 0 0 1 0 1⎥
⎢ 00 00 11 00 00 10 01 01 00 10 10 01 00 ⎥
⎣0 0 1 1 0 1 0 1 0 0 1⎦
⎥
⎢
⎣0 0 0 1 1 0 0 0 0 1 0 1 0⎦
0 0 1 0 1 0 1 1 1 0 0
0 0 0 1 1 1 1 0 0 1 0

0 0 0 1 0 1 0 1 0 0 0 0 1
0 0 0 1 0 0 1 0 1 0 1 0 0

Every column in the first design has five 1s and every pair of rows has precisely
two columns of 1s. Similarly, every column in the second design has four 1s, and
every pair of rows has precisely one column of 1s. Note also that every row of the
first design contains five 1s, and every row of the second design contains four 1s.
We show below that this regularity is not a coincidence.
Since each block contains exactly k varieties,
(2.2)

Jv A = kJv .

www.TechnicalBooksPDF.com



10

2. MANY KINDS OF PAIRWISE COMBINATORIAL DESIGNS

We now prove that
AA = kIv + λ(Jv − Iv ).

(2.3)

The inner product of any two distinct rows of A is λ, so we only need to show
that every row of A contains exactly k 1s. Let ri denote the number of columns
of A containing a 1 in the ith row. Let B be the v × ri submatrix of A obtained
by removing all columns not containing 1 in the ith row of A. Since the ith row
of B consists of ri 1s and the other rows each contain λ 1s, B contains exactly
ri + λ(v − 1) 1s. Each column of B has exactly k 1s, so ri k = ri + λ(v − 1). Thus
ri = λ(v − 1)/(k − 1). Now counting the number of 1s in A first by row and then
by column, we get vri = vk. This proves (2.3), and additionally
λ(v − 1) = k(k − 1).

(2.4)

Since this is a necessary condition for there to be an SBIBD(v, k, λ), we will suppose
in the remainder of this section that (2.4) holds.
2.2.3. Definition. Let v > k > λ ≥ 0 be integers satisfying equation (2.4),
and let ΛSBIBD(v,k,λ) be the set of 2 × v (0, 1)-matrices X such that
XX

=


k
λ

λ
k

.

2.2.4. Remark. ΛSBIBD(v,k,λ) is non-empty by definition, and is the orbit under
row and column permutations of the matrix
···
···

1
1

1
1

1
0

···
···

1
0

0

1

···
···

0
1

···
···

0
0

0
0

,

with λ columns [1, 1] , k − λ columns [1, 0] , k − λ columns [0, 1] , and v − 2k + λ
columns [0, 0] ; see the next lemma.
2.2.5. Lemma. For v > k > λ ≥ 0 satisfying (2.4), v ≥ 2k − λ.
Proof. Let x and y = x be non-negative integers such that xy ≥ k(k − 1).
Then (x + y)2 − (x − y)2 ≥ 4k(k − 1), and so (x + y)2 − (2k − 1)2 ≥ (x − y)2 − 1 ≥ 0.
Thus x + y ≥ 2k − 1. So by (2.4), λ + v − 1 ≥ 2k − 1, i.e., v ≥ 2k − λ.
2.2.6. Theorem. A is an incidence matrix of an SBIBD(v, k, λ) if and only if
it is a PCD(ΛSBIBD(v,k,λ) ).
Proof. Since an incidence matrix A of any SBIBD(v, k, λ) satisfies (2.3), we
have the forward implication. Assuming (2.3) and (2.4), we verify that A has every
column sum equal to k.

Let ki denote the number of 1s in the ith column. Then
v

v

ki (ki − 1) = λv(v − 1),

(2.5)
i=1

Using (2.4) and (2.5) we get
v

v
i=1

ki2 = vk(k − 1) +

v

(ki − k)2 =
i=1

ki = vk.
i=1

ki = vk2 , and then

v


ki2 + vk2 − 2k
i=1

v
i=1

ki = vk2 + vk2 − 2k(vk) = 0.
i=1

Thus ki = k for all i.
In particular, if A is a PCD(ΛSBIBD(v,k,λ) ), then (2.2) holds.

www.TechnicalBooksPDF.com


2.3. HADAMARD MATRICES

2.2.7. Theorem. A

11

is a PCD(ΛSBIBD(v,k,λ) ) if and only if A is too.

Proof. Suppose that A is a PCD(ΛSBIBD(v,k,λ) ). Then by (2.2) and (2.3) we
have
(2.6)

Jv A = AJv .

Moreover, det(AA ) = (k − λ)v−1 (k + (v − 1)λ) = k2 (k − λ)v−1 = 0. Therefore A

is invertible. By (2.6),
A A = A−1 AA A = A−1 (kIv + λ(Jv − Iv ))A = kIv + λ(Jv − Iv )
as required.
2.2.8. Corollary. ΛSBIBD(v,k,λ) is transposable.
2.3. Hadamard matrices
2.3.1. Definition. A Hadamard matrix of order n is an n × n (1, −1)-matrix
H such that
(2.7)

HH

= nIn .

2.3.2. Example. Writing − for −1, here is a Hadamard matrix of order 12:
⎡
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣

1
1

1
1
1
1
1
1
1
1
1
1

1
1
1
1
1
1
−
−
−
−
−
−

1
1
1
−
−
−

1
1
1
−
−
−

1
1
−
1
−
−
1
−
−
1
1
−

1
1
−
−
1
−
−
1
−
1

−
1

1
1
−
−
−
1
−
−
1
−
1
1

1
−
1
1
−
−
−
−
1
1
−
1

1

−
1
−
1
−
1
−
−
−
1
1

1
−
1
−
−
1
−
1
−
1
1
−

1
−
−
1
1

−
−
1
1
−
1
−

1
−
−
1
−
1
1
1
−
−
−
1

1
−
−
−
1
1
1
−
1

1
−
−

⎥
⎥
⎥
⎥
⎥
⎥.
⎥
⎥
⎥
⎥
⎦

2.3.3. Definition. Let ΛH(n) denote the set of 2 × n (1, −1)-matrices X such
that XX = nI2 .
2.3.4. Remarks.
(1) ΛH(n) is non-empty if and only if n is even.
(2) ΛH(n) consists of two orbits under row and column permutations if n = 2,
and ( n4 + 1)( n2 + 1) orbits if n ≥ 4.
2.3.5. Theorem. An n × n (1, −1)-matrix is a Hadamard matrix if and only if
it is a PCD(ΛH(n) ).
2.3.6. Theorem. ΛH(n) is transposable.
Proof. Certainly (2.7) implies that H is invertible over the rational field Q,
with H −1 = n1 H . So H H = nIn .
Hadamard matrices were first studied by Sylvester [149] and Hadamard [80] in
the 19th century, and over the years have become the subject of vigorous research
activity. Applications occur, for example, in electrical engineering (circuit design)

and statistics (experimental design). Horadam’s book [87] is an excellent reference
for the use of these matrices in signal and data processing. Overall, the literature
on Hadamard matrices is immense.

www.TechnicalBooksPDF.com


12

2. MANY KINDS OF PAIRWISE COMBINATORIAL DESIGNS

Hadamard matrices are a source of block designs. Normalize any Hadamard
matrix H of order 4t, and remove the first row and column to obtain the matrix
A; then (A + J)/2 is an incidence matrix of an SBIBD(4t − 1, 2t − 1, t − 1). If
H has constant row and column sums then the same trick of replacing −1s with
zeros applied directly to H results in another symmetric balanced incomplete block
design.
We note the following widely-known result.
2.3.7. Theorem. A Hadamard matrix H with constant row and column sums
has square order.
Proof. Let n be the order of H, and let s be the constant row and column
sum. Then nJn = Jn HH = sJn H = s2 Jn , so n = s2 .
One may easily show that a Hadamard matrix of order n > 2 can exist only
if 4 divides n. The famous Hadamard Conjecture states that this condition on the
order is sufficient for existence.
1. Conjecture. There is a Hadamard matrix of order 4t for all t ≥ 1.
This book gives a comprehensive account of Hadamard matrices characterized
by a special regular group action: cocyclic Hadamard matrices. The Sylvester
and Paley matrices are discussed in detail. A result on the asymptotic existence of
cocyclic Hadamard matrices is proved. We describe most of the direct constructions

known for cocyclic Hadamard matrices. Finally, a large family of cocyclic Hadamard
matrices is given, which in turn provides a large class of central relative difference
sets. This material is drawn from [43, 47, 51, 54, 55, 56, 57, 65].
2.4. Weighing matrices
2.4.1. Definition. Let n ≥ k ≥ 1. A weighing matrix W(n, k) of order n and
weight k is an n × n (0, ±1)-matrix W such that
WW

= kIn .

2.4.2. Example. We display a W(10, 8) below.
⎡1 1 1 1 1 1 1 1 0
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣

1
1
1
1
1
1
1
0
0


0
1 1 1 − − − − 0 0
− 1 − 1 − 0 0 1 1
− − 1 − 1 0 0 1 1
1 − − 0 0 1 − − 1
1 − − 0 0 − 1 1 −
− 0 0 1 1 − − − −
− 0 0 − − 1 1 − −
0 1 − − 1 − 1 − 1
0 1 − − 1 1 − 1 −

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦

2.4.3. Definition. Let ΛW(n,k) be the set of 2 × n (0, ±1)-matrices X such
that XX = kI2 .
2.4.4. Remark. ΛW(n,k) is non-empty if and only if n ≥ k + {k/2}.
2.4.5. Theorem. An n × n (0, ±1)-matrix is a W(n, k) if and only if it is a
PCD(ΛW(n,k) ).
2.4.6. Theorem. The orthogonality set ΛW(n,k) is transposable.
Proof. Cf. the proof of Theorem 2.3.6; a W(n, k) is invertible over Q.


www.TechnicalBooksPDF.com