21.3. СХЕМА ОТНОШЕНИЙ ХЭММИНГА
Наиболее важным для теории кодирования примером схем отношений является схема Хэмминга, или гиперкубическая схема. В этой схеме 
т. е. множество двоичных векторов длины 
причем два вектора х, 
i-связаны, если они находятся друг от друга на расстоянии Хэмминга 
Ясно, что условия 
определения схемы отношений выполнены. Упражнение (19) из гл. 1 показывает, что условие 
также выполнено, причем 
Кроме того, 
и Матрицы алгебры Боуза-Меснера 
представляют собой 
-матрицы, строки и столбцы которых перенумерованы векторами 
. В частности, 
элемент матрицы 
если и только если 
Пусть, например, 
и строки, и столбцы матриц нумеруются векторами 
. Граф, ребра которого имеют номер 1, представляет собой куб (рис. 21.1):
Диагонали граней куба занумерованы цифрой 2, а четыре главные диагонали занумерованы цифрой 3. Матрицы смежностей имеют следующий вид: 
Рис. 21.1. Граф для кубической схемы
Заметим, что
Теорема 5. Примитивный идемпотент 
схемы Хэмминга представляет собой матрицу, 
элемент которой равен
Собственные значения схемы определяются равенствами
где 
многочлен Кравчука, определяемый выражением (5.14).
Доказательство. Пусть А обозначает матрицу, элемент которой в позиции 
задается равенством (21.24). Покажем, что
и поэтому Затем мы докажем справедливость равенств (21.8) — (21.10), откуда будет следовать, что 
примитивные идемпотенты. Далее из (21.26) вытекает, что 
и из (21.18) (и теоремы 17 гл. 5) следует, что
Чтобы доказать (21.26), вспомним, что согласно упражнению (14) гл. 5
и, следовательно,
Элемент в позиции 
матрицы 
равен
что приводит к выражению
представляющему собой 
элемент матрицы 
и доказывает соотношения (21.8) и (21.9). Соотношение (21.10) легко выводится.
Соотношения (21.16) превращаются теперь в знакомые нам соотношения ортогональности для многочленов Кравчука (теорема 16 из гл. 5).
Например, когда 
(см. скан)
тогда
(см. скан)
является 
столбец матрицы 
при 
