Hamming scheme

The Hamming scheme, named after Richard Hamming, is also known as the hyper-cubic association scheme, and it is the most important example for coding theory. In this scheme $X={{ℱ}}^n,$ the set of binary vectors of length $n,$ and two vectors $x,y\in {{ℱ}}^n$ are $i$-th associates if they are Hamming distance $i$ apart. Recall that an association scheme is visualized as a complete graph with labeled edges. The graph has $v$ vertices, one for each point of $X,$ and the edge joining vertices $x$ and $y$ is labeled $i$ if $x$ and $y$ are $i$-th associates. Each edge has a unique label, and the number of triangles with a fixed base labeled $k$ having the other edges labeled $i$ and $j$ is a constant $c_{ijk},$ depending on $i,j,k$ but not on the choice of the base. In particular, each vertex is incident with exactly $c_{ii0}=v_i$ edges labeled $i$; $v_i$ is the valency of the relation $R_i.$ The $c_{ijk}$ in a Hamming scheme are given by

$c_{ijk}=\{\begin{array}{ll}(\genfrac{}{}{0ex}{}{k}{\frac{1}{2}(i-j+k)})(\genfrac{}{}{0ex}{}{n-k}{\frac{1}{2}(i-j+k)})& i+j-k\equiv 0(\mathrm{mod}2)\\ \\ 0& i+j-k\equiv 1(\mathrm{mod}2)\end{array}$

Here, $v=|X|=2^n$ and $v_i=(\genfrac{}{}{0ex}{}{n}{i}).$ The matrices in the Bose-Mesner algebra are $2^n\times 2^n$ matrices, with rows and columns labeled by vectors $x\in {{ℱ}}^n.$ In particular the $(x,y)$-th entry of $D_k$ is $1$ if and only if $d_H(x,y)=k.$