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.[1][2][3] In this scheme ${\displaystyle X={\mathcal {F}}^{n},}$ the set of binary vectors of length ${\displaystyle n,}$ and two vectors ${\displaystyle x,y\in {\mathcal {F}}^{n}}$ are ${\displaystyle i}$-th associates if they are Hamming distance ${\displaystyle i}$ apart.

Recall that an association scheme is visualized as a complete graph with labeled edges. The graph has ${\displaystyle v}$ vertices, one for each point of ${\displaystyle X,}$ and the edge joining vertices ${\displaystyle x}$ and ${\displaystyle y}$ is labeled ${\displaystyle i}$ if ${\displaystyle x}$ and ${\displaystyle y}$ are ${\displaystyle i}$-th associates. Each edge has a unique label, and the number of triangles with a fixed base labeled ${\displaystyle k}$ having the other edges labeled ${\displaystyle i}$ and ${\displaystyle j}$ is a constant ${\displaystyle c_{ijk},}$ depending on ${\displaystyle i,j,k}$ but not on the choice of the base. In particular, each vertex is incident with exactly ${\displaystyle c_{ii0}=v_{i}}$ edges labeled ${\displaystyle i}$; ${\displaystyle v_{i}}$ is the valency of the relation ${\displaystyle R_{i}.}$ The ${\displaystyle c_{ijk}}$ in a Hamming scheme are given by

${\displaystyle c_{ijk}={\begin{cases}{\dbinom {k}{{\frac {1}{2}}(i-j+k)}}{\dbinom {n-k}{{\frac {1}{2}}(i-j+k)}}&i+j-k\equiv 0{\pmod {2}}\\\\0&i+j-k\equiv 1{\pmod {2}}\end{cases}}}$

Here, ${\displaystyle v=|X|=2^{n}}$ and ${\displaystyle v_{i}={\tbinom {n}{i}}.}$ The matrices in the Bose-Mesner algebra are ${\displaystyle 2^{n}\times 2^{n}}$ matrices, with rows and columns labeled by vectors ${\displaystyle x\in {\mathcal {F}}^{n}.}$ In particular the ${\displaystyle (x,y)}$-th entry of ${\displaystyle D_{k}}$ is ${\displaystyle 1}$ if and only if ${\displaystyle d_{H}(x,y)=k.}$