Association scheme

Remarks

Many authors, following Bose and Mesner, require the scheme to be symmetric in the definition. In terms of the adjacency matrices $A_i$ of the relations, clause 3 says $A_i A_j = \sum_k p^k_{ij} A_k$. So the $A_i$ span an algebra of matrices, the Bose–Mesner algebra, which is commutative exactly when the scheme is commutative.

Example: on any finite set $X$ with at least $2$ points, let $R_0$ be the diagonal and $R_1$ the set of pairs of distinct points. Clauses 1 and 2 hold, and clause 3 holds with $p^0_{11} = \abs{X} - 1$ and $p^1_{11} = \abs{X} - 2$, while every other $p^k_{ij}$ is $0$ or $1$.

Non-example: let $X = \set{a, b, c}$ with $R_0$ the diagonal, $R_1$ the edges of the path $a - b - c$ in both directions, and $R_2 = \set{(a, c), (c, a)}$. Clause 3 fails for $i = j = 1$, $k = 0$: for $(a, a)$ there is one $z$ with $(a, z), (z, a) \in R_1$, but for $(b, b)$ there are two.

A symmetric scheme with $2$ classes is the same as a strongly regular graph that is neither complete nor edgeless, with $R_1$ as its edge relation.