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 [math]\displaystyle{ X=\mathcal{F}^n, }[/math] the set of binary vectors of length [math]\displaystyle{ n, }[/math] and two vectors [math]\displaystyle{ x, y\in \mathcal{F}^n }[/math] are [math]\displaystyle{ i }[/math]-th associates if they are Hamming distance [math]\displaystyle{ i }[/math] apart. Recall that an association scheme is visualized as a complete graph with labeled edges. The graph has [math]\displaystyle{ v }[/math] vertices, one for each point of [math]\displaystyle{ X, }[/math] and the edge joining vertices [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] is labeled [math]\displaystyle{ i }[/math] if [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] are [math]\displaystyle{ i }[/math]-th associates. Each edge has a unique label, and the number of triangles with a fixed base labeled [math]\displaystyle{ k }[/math] having the other edges labeled [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] is a constant [math]\displaystyle{ c_{ijk}, }[/math] depending on [math]\displaystyle{ i,j,k }[/math] but not on the choice of the base. In particular, each vertex is incident with exactly [math]\displaystyle{ c_{ii0}=v_i }[/math] edges labeled [math]\displaystyle{ i }[/math]; [math]\displaystyle{ v_{i} }[/math] is the valency of the relation [math]\displaystyle{ R_i. }[/math] The [math]\displaystyle{ c_{ijk} }[/math] in a Hamming scheme are given by

[math]\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} }[/math]

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