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={\mathcal {F}}^{n}$, the set of binary vectors of length $n$, and two vectors $x$, $y\in {\mathcal {F}}^{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{cases}{\dbinom {k}{\frac {i-j+k}{2}}}{\dbinom {n-k}{\frac {i+j-k}{2}}},&{\text{if }}i+j-k{\text{ is even,}}\\\;\;\;\;\;\;\;\;\;\;0\;\;\;\;\;\;\;\;\;\;\;,\;\;&{\text{if }}i+j-k{\text{ is odd.}}\end{cases}}$

Here, $v=\left|X\right|=2^{n}$ and $v_{i}={\binom {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 {\mathcal {F}}^{n}$. In particular the $\left(x,y\right)$-th entry of $D_{k}$ is $1$ if and only if $d_{H}(x,y)=k$.