21.7. ПОДМНОЖЕСТВА СХЕМ ОТНОШЕНИЙ

Код является подмножеством схемы Хэмминга. В этом параграфе мы рассмотрим непустое подмножество У произвольной схемы отношений X с отношениями

Предположим, что Внутренним спектром У называется -вектор с рациональными компонентами, где представляет собой среднее число точек которые -связаны с точкой Для схемы

Хэмминга вектор является спектром расстояний (см. § 2.1) кода У.

Конечно,

и

Дельсарт заметил, что некоторые линейные комбинации чисел также неотрицательны.

Теорема 12. (Дельсарт.)

для где собственные значения, определенные в § 21.2.

Доказательство. Пусть и обозначает вектор, указывающий, какие элементы X принадлежат У:

Тогда

Так как идемпотент, то его собственные значения равны 0 или 1 и, следовательно, неотрицательно определенная матрица. Поэтому .

Например, применяя теорему 12 к кодам, мы получим другое доказательство теоремы 6 гл. 5. Применяя ее к схеме Джонсона, мы получим результаты по равновесным кодам, которыми мы пользовались на с. 527 гл. 17. В общем случае равенство (21.46) позволяет применить методы линейного программирования ко многим задачам, которые включают отыскание наибольшего подмножества схемы отношений, удовлетворяющего некоторым ограничениям на числа Такую задачу можно сформулировать следующим образом: максимизировать сумму где удовлетворяют условиям (21.45), (21.47) и любым дополнительным ограничениям. Примеры см. на с. 520 и 528 гл. 17.