association scheme

Association schemes were introduced by statisticians in the 1950’s to analyze designs of statistical experiments. Today, association schemes are useful not only in experimental designs, but in other areas of mathematics such as combinatorics (coding theory) and group theory (permutation groupsMathworldPlanetmathPlanetmath).

There are several equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath ways to define an association schemes. Three useful ones are illustrated here:

Let Ω be a non-empty set with n elements, and s a positive integer.

Definition 1. An association scheme 𝒬 on Ω is a partitionMathworldPlanetmathPlanetmath on Ω×Ω into sets C0,C1,,Cs called associate classes, such that

  • each Ci is a symmetric relationMathworldPlanetmath on Ω, and C0 in particular is the diagonal relation,

  • for i,j,k{0,1,,s}, there is an integer pijk such that, for any (a,b)Ck,

    |{cΩ(a,c)Ci and (c,b)Cj}|=pijk.

If we write C(a,b;i,j) for the set {cΩ(a,c)Ci and (c,b)Cj}, then the second condition says that for any (a,b)Ck, the value |C(a,b;i,j)| is a constant, depending only on i,j and k, and not on the particular elements of Ck. This implies that, for any i,j{0,1,,n}, the relationMathworldPlanetmathPlanetmath CiCj is a union of (some of) the Ck’s.

The definition above can be restated in graph theoretic terminology. First, think of Ω is a set of vertices, and two-element subsets of Ω are edges. The complete graphMathworldPlanetmath on Ω is just the set of all two-element subsets of Ω. We may color the edges of the graph. Say there are colors labeled 1 through s. For each color i, let Ci be the set of edges with color i. Then each Ci is just a symmetric relation on Ω, and that all the Ci’s, together with the diagonal relation, partition the set Ω×Ω. This is basically the first condition of the definition above. In this regard, we can redefine an association scheme graph theoretically, as follows:

Definition 2. An association scheme 𝒬 is a surjectivePlanetmathPlanetmath coloringMathworldPlanetmath on the edge set of a complete graph whose vertex set is Ω, by a set of s colors (numbered 1 through s), such that

for any i,j,k{1,,s}, there is an integer pijk such that if 𝒬(a,b)=k (the edge {a,b} has color k), then

|{cΩ𝒬(a,c)=i and 𝒬(c,b)=j}|=pijk.

In words, the definition says that, for any color k, and any given edge e with color k, the number of triangles (a triangle in a graph is a cycle consisting of three edges) with e as an edge, and two other edges with colors i,j respectively, is pijk.

The first definition can also be viewed in terms of matrices, and adjacency matricesMathworldPlanetmath more specifically. Given a finite setMathworldPlanetmath Ω, a binary relation R on Ω naturally corresponds to matrix A called the adjacency matrix of R. Entry (i,j) is 1 if the i-th element and the j-th element are related by R, and 0 otherwise. If R is reflexiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath, then A has all 1’s in its diagonal, and if R is symmetricPlanetmathPlanetmath, then so is A. Also, it is easy to see that the compositionMathworldPlanetmathPlanetmath of two binary relations is the same as the productPlanetmathPlanetmath of their corresponding adjacency matrices. Then the comment in the paragraph after the first definition is the same as saying that the adjacency matrix of CiCj is a linear combinationMathworldPlanetmath of the adjacency matrices of C0,C1,,Cs. This gives us the third definition below:

Definition 3. An association scheme is a finite set 𝒬 of n×n non-zero matrices A0,A1,,As whose entries are 0’s and 1’s, such that

  • each Ai is a symmetric matrix, with A0=In, the identity matrixMathworldPlanetmath,

  • A0+A1++As=Jn, the matrix whose entries are all 1’s, and

  • for any i,j{0,,s}, AiAj is a linear combination of A0,A1,,As.

By the definitions of the matrices Ai and the second condition, for every pair (r,s), exactly one of the s+1 matrices has 1 in cell (r,s), and all others have 0 in the corresponding cell. As a result, the s+1 matrices are linearly independentMathworldPlanetmath.

Also, in view of the discussion above, it is easy to see that


Some terminology. s is called the rank of the association scheme 𝒬. Any aΩ, an element c𝒬 is said to be an i-associate of a if (a,c)Ci. For each aΩ, define:


So Ci(a) is the set of all i-associates of a. Then

|Ci(a)Cj(b)|=pijk, whenever (a,b)Ck,

and because of the above equation, each pijk is called an intersection number of 𝒬. For each i, the intersection number pii0 is called the valency of Ci, denoted by ai.

Some basic properties of the intersection numbers:

  • pijk=pjik

  • pi0k={1if i=k0otherwise.
  • |Ci(c)|=pii0=ai for all cΩ.


  • 1 R. A. Bailey, Association Schemes, Designed Experiments, Algebra and Combinatorics, Cambridge University Press (2004)
Title association scheme
Canonical name AssociationScheme
Date of creation 2013-03-22 19:15:03
Last modified on 2013-03-22 19:15:03
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Definition
Classification msc 05E30
Defines associate class
Defines rank
Defines intersection number
Defines valency