
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 coworkers. 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 {C_{0}, C_{1}, ..., C_{r}} of binary relations on a set Omega (that is, subsets of the set Omega^{2} of ordered pairs of elements of Omega), satisfying the following four conditions:
The relations C_{0}, C_{1}, ..., C_{r} are the associate classes of the scheme; two points x and y are ith associates if (x,y) in C_{i}
A binary relation C on Omega can be represented by a zeroone 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 zeroone matrices A_{0}, ..., A_{r} satisfying the following conditions:
A_{i}A_{j} = Sum_{k=0}^{r} p_{ij}^{k}A_{k};in other words, the span of {A_{0}, ..., A_{r}} is an algebra.
This is often taken as the definition of an association scheme. The algebra referred to in (AS4) is the BoseMesner 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 nonadjacency form an association scheme. Many such graphs exist, and there are extensive catalogues.
The Johnson scheme J(v,k) has as points the kelement subsets of a velement set, where k<=v/2; two points are ith associates if they intersect in ki points.
The Hamming scheme H(n,q) has as points all ntuples over an alphabet of cardinality q; two points are ith associates if they agree in ni positions. For q=2, this is the ndimensional 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 q1 (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 (q1)/r in the multiplicative group of the field as K_{1}, ..., K_{r}, with K_{0} = {0}, the points x and y are ith associates if xy in K_{i}.
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 Omega^{2}; so
Omega^{2} 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 C_{k}, where
C_{k} 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 C_{i},
(z,y) in C_{j}}
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 BoseMesner 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
R^{Omega} = V_{0} + ... + V_{r}of R^{Omega} as a direct sum of orthogonal subspaces such that each basis matrix as a scalar on each V_{i}. The subspaces V_{i} are the strata.
Let E_{i} be the orthogonal projection onto the subspace V_{i}. Then the matrices E_{0}, ..., E_{r} form an alternative basis for the BoseMesner algebra, consisting of pairwise orthogonal idempotents. If
A_{i} = Sum P_{i}(j)E_{j},then the numbers P_{i}(j) , for j = 0, ..., r, are the eigenvalues of A_{i}. (Thus P_{i} is a character of the algebra.)
The dimensions of the subspaces V_{i} (that is, the ranks of the E_{i}) are algebraic functions of the combinatorial parameters p_{ij}^{k}. 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 BoseMesner algebra is closed under pointwise (Hadamard) product, since it has a basis of zeroone matrices. The Hadamard product E_{i}°E_{j} of idempotents is positive semidefinite, so its eigenvalues (which can be computed) are nonnegative.
An incompleteblock 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 incompleteblock designs in statistics  see Bailey [2] for this. We mention two types of examples of such designs.
A 2design (balanced incompleteblock design) is said to be quasisymmetric 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 quasisymmetric 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 Omega^{2} 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 C_{}_{0}, ..., C_{r} 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 Omega^{2} 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].