of the relation . There are also loops labeled at each vertex , corresponding to . The relations are described by their adjacency matrices. is the adjacency matrix of for and is a v × v matrix with rows and columns labeled by the points of . The definition of a symmetric association scheme is equivalent to saying that the are v × v (0,1)-matrices which satisfy I. is symmetric, II. (the all-ones matrix), III. , IV. . The (x, y)-th entry of the left side of (IV) is the number of paths of length two between x and y with labels i and j in the graph. Note that the rows and columns of contain 's: Terminology The numbers are called the parameters of the scheme. They are also referred to as the structural constants. History The term association scheme is due to but the concept is already inherent in . These authors were studying what statisticians have called partially balanced incomplete block designs (PBIBDs). The subject became an object of algebraic interest with the publication of and the introduction of the Bose–Mesner algebra. The most important contribution to the theory was the thesis of P. Delsarte who recognized and fully used the connections with coding theory and design theory. Generalizations have been studied by D. G. Higman (coherent configurations) and B. Weisfeiler (distance regular graphs). Basic facts , i.e. if then and the only such that is . , this is because the partition . The Bose–Mesner algebra The adjacency matrices of the graphs generate a commutative and associative algebra (over the real or complex numbers) both for the matrix product and the pointwise product. This associative, commutative algebra is called the Bose–Mesner algebra of the association scheme. Since the matrices in are symmetric and commute with each other, they can be diagonalized simultaneously. Therefore, is semi-simple and has a unique basis of primitive idempotents . There is another algebra of matrices which is isomorphic to , and is often easier to work with. Examples The Johnson scheme, denoted J(v, k), is defined as follows. Let S be a set with v elements. The points of the scheme J(v, k) are the subsets of S with k elements. Two k-element subsets A, B of S are i th associates when their intersection has size k − i. The Hamming scheme, denoted H(n, q), is defined as follows. The