|
Encyclopaedia of DesignTheory: Topic Essay |
A printable PDF version of this document is available.
The origins of association schemes lie in statistics, in the work of R. C. Bose and his co-workers. The subject has close connections with permutation groups (D. G. Higman, B. Weisfeiler), coding theory (P. Delsarte), and even knot theory (F. Jaeger).
Combinatorially, an association scheme is a set {C0, C1, ..., Cr} of binary relations on a set Omega (that is, subsets of the set Omega2 of ordered pairs of elements of Omega), satisfying the following four conditions:
The relations C0, C1, ..., Cr are the associate classes of the scheme; two points x and y are ith associates if (x,y) in Ci
A binary relation C on Omega can be represented by a zero-one matrix whose rows and columns are indexed by Omega, having (x,y) entry 1 if (x,y) in C, and 0 otherwise. If we translate the relations of an association scheme into matrices in this way, we obtain zero-one matrices A0, ..., Ar satisfying the following conditions:
AiAj = Sumk=0r pijkAk;in other words, the span of {A0, ..., Ar} is an algebra.
This is often taken as the definition of an association scheme. The algebra referred to in (AS4) is the Bose-Mesner algebra of the scheme.
There are many good references to association schemes; books on the topic include Bailey [2], Bannai and Ito [3], Brauer, Cohen and Neumaier [5], and Godsil [8].
There are many examples of association schemes. For example, a graph is called strongly regular if the relations of equality, adjacency and non-adjacency form an association scheme. Many such graphs exist, and there are extensive catalogues.
The Johnson scheme J(v,k) has as points the k-element subsets of a v-element set, where k<=v/2; two points are ith associates if they intersect in k-i points.
The Hamming scheme H(n,q) has as points all n-tuples over an alphabet of cardinality q; two points are ith associates if they agree in n-i positions. For q=2, this is the n-dimensional cube; an example appears here.
Delsarte gave a detailed treatment of subsets of association schemes; his results for Hamming and Johnson schemes have important applications in coding theory and design theory respectively.
The cyclotomic scheme C(q,r), where r divides q-1 (and the quotient is even if q is odd) has as points the elements of the finite field GF(q). Numbering the cosets of the subgroup of order (q-1)/r in the multiplicative group of the field as K1, ..., Kr, with K0 = {0}, the points x and y are ith associates if x-y in Ki.
Many other examples are derived from permutation groups, as described below.
One final example is the rectangular association scheme, whose points are the cells of an m×n grid; the associate classes are `equal', `same row', `same column', and `other'.
A permutation group G acting on a set Omega is said to be generously transitive if, given any two elements x and y of Omega, there is a permutation g in G which interchanges x and y. In particular, we see that a generously transitive group is transitive.
There is a natural action of G on the set Omega2; so
Omega2 is partitioned into orbits of G. The generous
transitivity now guarantees that the orbit partition satisfies (AS2) and
(AS3). The fact that the parts are orbits guarantees that (AS4) also holds:
for, if (x,y), (x',y') in Ck, where
Ck is a part of the partition, then there exists
g in G mapping (x,y) to (x',y');
then g maps the set
{z:(x,z) in Ci,
(z,y) in Cj}
to the corresponding set involving x' and y',
so the numbers of such points are equal.
Thus, every generously transitive group gives rise in a natural way to an association scheme.There are very many examples of such groups!
Weaker conditions than generous transitivity suffice for a permutation group to act on an association scheme; it is necessary to take unions of orbits as associate classes. This is explored in [1]. More background on permutation groups can be found in [6].
If the product of two real symmetric matrices is symmetric, the matrices commute. Hence the Bose-Mesner algebra is commutative. The spectral theorem for real symmetric matrices implies that the basis matrices can be simultaneously diagonalised by an orthogonal transformation. That is, there is an expression
ROmega = V0 + ... + Vrof ROmega as a direct sum of orthogonal subspaces such that each basis matrix as a scalar on each Vi. The subspaces Vi are the strata.
Let Ei be the orthogonal projection onto the subspace Vi. Then the matrices E0, ..., Er form an alternative basis for the Bose-Mesner algebra, consisting of pairwise orthogonal idempotents. If
Ai = Sum Pi(j)Ej,then the numbers Pi(j) , for j = 0, ..., r, are the eigenvalues of Ai. (Thus Pi is a character of the algebra.)
The dimensions of the subspaces Vi (that is, the ranks of the Ei) are algebraic functions of the combinatorial parameters pijk. The fact that they are positive integers gives necessary conditions (the integrality conditions) for the existence of an association scheme with specified parameters.
Further necessary conditions can be derived from the fact that the Bose-Mesner algebra is closed under pointwise (Hadamard) product, since it has a basis of zero-one matrices. The Hadamard product Ei°Ej of idempotents is positive semi-definite, so its eigenvalues (which can be computed) are non-negative.
An incomplete-block design is said to be partially balanced with respect to an association scheme on the set of points if the number of blocks incident with two points x and y depends only on the associate class containing the pair (x,y). Such a design is called a PBIBD for short.
Partially balanced designs were introduced by Bose and Nair [4]. They have many of the advantages of BIBDs but, unlike the latter, are not bound by Fisher's Inequality asserting that there must be at least as many blocks as treatments. We cannot describe here in detail the uses of partially balanced incomplete-block designs in statistics - see Bailey [2] for this. We mention two types of examples of such designs.
A 2-design (balanced incomplete-block design) is said to be quasi-symmetric if the number of points incident with two distinct blocks takes just two different values. See [11] for a survey of such designs. Now the dual of a quasi-symmetric BIBD is a PBIBD with respect to an association scheme on the set of blocks, where the associate classes are defined by the sizes of the intersections of the blocks.
Let G be a generously transitive permutation group on Omega, and H an intransitive subgroup of G. Taking blocks to be the translates of any union of orbits of H, we obtain a design which is partially balanced with respect to the association scheme defined by the orbits of G.
If G is an arbitrary permutation group on Omega (not necessarily generously transitive), then the orbits of G on Omega2 form a partition, which satisfies conditions (AS1) and (AS4), but only weaker versions of the other two conditions. To model this situation, a coherent configuration is defined to be a set C0, ..., Cr of binary relations on Omega satisfying the following conditions:
Thus, the orbits of any permutation group form a coherent configuration. The last condition again implies that the matrices of the relations span an algebra, called the basis algebra of the configuration. Unlike for association schemes, this algebra is not in general commutative, so its representation theory is more complicated.
A coherent configuration is homogeneous if, in place of (CC2), it satisfies the stronger condition (AS2). Thus, the orbits of a transitive permutation group form a homogeneous coherent configuration. Hanaki and Miyamoto [9] have determined all homogeneous coherent configurations on up to 30 points.
A completely different generalisation of association schemes has been proposed in statistics, where symmetry of the matrices is more important than closure under multiplication. The set of real symmetric matrices is closed under the operation of Jordan product A * B = (1/2)(AB+BA). Thus, a Jordan scheme is a partition of Omega2 satisfying (AS1)-(AS3), but with (AS4) (closure under multiplication) replaced by closure under Jordan product. Then the span of the basis matrices is a Jordan algebra, and we must use the structure theory for these, rather than associative algebras. See [10].