Hamming scheme

The Hamming scheme, named after <a href="/facts/Richard_Hamming/plAXy9p0">Richard Hamming</a>, is also known as the hyper-cubic association scheme, and it is the most important example for <a href="/facts/Coding_theory/SBqStoGL">coding theory</a>. In this scheme 
 
 
 
 X
 =
 
 
 
 F
 
 
 
 n
 
 
 ,
 
 
 {\displaystyle X={\mathcal {F}}^{n},}
 
 the set of binary vectors of length 
 
 
 
 n
 ,
 
 
 {\displaystyle n,}
 
 and two vectors 
 
 
 
 x
 ,
 y
 ∈
 
 
 
 F
 
 
 
 n
 
 
 
 
 {\displaystyle x,y\in {\mathcal {F}}^{n}}
 
 are 
 
 
 
 i
 
 
 {\displaystyle i}
 
-th associates if they are <a href="/facts/Hamming_distance/MgdtbYPo">Hamming distance</a> 
 
 
 
 i
 
 
 {\displaystyle i}
 
 apart.
Recall that an <a href="/facts/Association_scheme/MLqL2NEB">association scheme</a> is visualized as a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> with labeled edges. The graph has 
 
 
 
 v
 
 
 {\displaystyle v}
 
 vertices, one for each point of 
 
 
 
 X
 ,
 
 
 {\displaystyle X,}
 
 and the edge joining vertices 
 
 
 
 x
 
 
 {\displaystyle x}
 
 and 
 
 
 
 y
 
 
 {\displaystyle y}
 
 is labeled 
 
 
 
 i
 
 
 {\displaystyle i}
 
 if 
 
 
 
 x
 
 
 {\displaystyle x}
 
 and 
 
 
 
 y
 
 
 {\displaystyle y}
 
 are 
 
 
 
 i
 
 
 {\displaystyle i}
 
-th associates. Each edge has a unique label, and the number of triangles with a fixed base labeled 
 
 
 
 k
 
 
 {\displaystyle k}
 
 having the other edges labeled 
 
 
 
 i
 
 
 {\displaystyle i}
 
 and 
 
 
 
 j
 
 
 {\displaystyle j}
 
 is a constant 
 
 
 
 
 c
 
 i
 j
 k
 
 
 ,
 
 
 {\displaystyle c_{ijk},}
 
 depending on 
 
 
 
 i
 ,
 j
 ,
 k
 
 
 {\displaystyle i,j,k}
 
 but not on the choice of the base. In particular, each vertex is incident with exactly 
 
 
 
 
 c
 
 i
 i
 0
 
 
 =
 
 v
 
 i
 
 
 
 
 {\displaystyle c_{ii0}=v_{i}}
 
 edges labeled 
 
 
 
 i
 
 
 {\displaystyle i}
 
; 
 
 
 
 
 v
 
 i
 
 
 
 
 {\displaystyle v_{i}}
 
 is the <a href="/facts/Adjacency_relation/kw3eIBUe">valency</a> of the <a href="/facts/Relation_(mathematics)/HjblDaMy">relation</a> 
 
 
 
 
 R
 
 i
 
 
 .
 
 
 {\displaystyle R_{i}.}
 
 The 
 
 
 
 
 c
 
 i
 j
 k
 
 
 
 
 {\displaystyle c_{ijk}}
 
 in a Hamming scheme are given by

c
          
            i
            j
            k
          
        
        =
        
          
            {
            
              
                
                  
                    
                      
                        
                          (
                        
                        
                          k
                          
                            
                              
                                1
                                2
                              
                            
                            (
                            i
                            −
                            j
                            +
                            k
                            )
                          
                        
                        
                          )
                        
                      
                    
                  
                  
                    
                      
                        
                          (
                        
                        
                          
                            n
                            −
                            k
                          
                          
                            
                              
                                1
                                2
                              
                            
                            (
                            i
                            +
                            j
                            −
                            k
                            )
                          
                        
                        
                          )
                        
                      
                    
                  
                
                
                  i
                  +
                  j
                  −
                  k
                  ≡
                  0
                  
                    
                    (
                    mod
                    
                    2
                    )
                  
                
              
              
                
              
              
                
                  0
                
                
                  i
                  +
                  j
                  −
                  k
                  ≡
                  1
                  
                    
                    (
                    mod
                    
                    2
                    )
                  
                
              
            
            
          
        
      
    
    {\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, 
 
 
 
 v
 =
 
 |
 
 X
 
 |
 
 =
 
 2
 
 n
 
 
 
 
 {\displaystyle v=|X|=2^{n}}
 
 and 
 
 
 
 
 v
 
 i
 
 
 =
 
 
 
 
 (
 
 
 n
 i
 
 
 )
 
 
 
 
 .
 
 
 {\displaystyle v_{i}={\tbinom {n}{i}}.}
 
 The <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrices</a> in the <a href="/facts/Bose%25E2%2580%2593Mesner_algebra/1ovWTsIG">Bose-Mesner algebra</a> are 
 
 
 
 
 2
 
 n
 
 
 ×
 
 2
 
 n
 
 
 
 
 {\displaystyle 2^{n}\times 2^{n}}
 
 <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrices</a>, with rows and columns labeled by vectors 
 
 
 
 x
 ∈
 
 
 
 F
 
 
 
 n
 
 
 .
 
 
 {\displaystyle x\in {\mathcal {F}}^{n}.}
 
 In particular the 
 
 
 
 (
 x
 ,
 y
 )
 
 
 {\displaystyle (x,y)}
 
-th entry of 
 
 
 
 
 D
 
 k
 
 
 
 
 {\displaystyle D_{k}}
 
 is 
 
 
 
 1
 
 
 {\displaystyle 1}
 
 if and only if 
 
 
 
 
 d
 
 H
 
 
 (
 x
 ,
 y
 )
 =
 k
 .
 
 
 {\displaystyle d_{H}(x,y)=k.}

Hamming scheme open-in-new

Hamming scheme