21.2. СХЕМЫ ОТНОШЕНИЙ

В этом разделе излагаются основы теории.

Определение. Схемой отношений с классами (или отношениями) называется конечное множество X из точек, на котором заданы отношений удовлетворяющих следующим условиям:

(i). Каждое симметрично:

Для любых двух точек условие выполняется точно для одного значения i.

(iii). представляет собой тождественное отношение.

iv). Если то число точек таких, что является константой зависящей от чисел не зависящей от выбора точек х и у.

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

Полезно иногда представлять схему отношений в виде полного графа, ребра которого занумерованы. Граф имеет вершин, по одной для каждой точки из X, причем ребро, соединяющее вершины х и у, имеет номер если соответствующие точки х и у -связаны. Каждое ребро имеет точно один номер и число треугольников с фиксированным основанием с номером два других ребра которого имеют номера является константой зависящей от но не зависящей от выбора основания. В частности, каждой вершине соответствует точно ребер, имеющих номера называется валентностью отношения

В каждой вершине этого графа имеется также петля с номером 0, соответствующая отношению

В следующих разделах будут приведены примеры схем отношений. Для теории кодирования наиболее важными являются

схемы Хэмминга, Джонсона и схемы, образованные симплектическими формами.

Коэффициенты удовлетворяют нескольким тождествам. Теорема 1.

Доказательство. Последнее тождество следует из подсчета числа четырехугольников вида

Мы будем описывать отношения с помощью их матриц смежности. Матрица смежности отношения представляет собой -матрицу, строки и столбцы которой занумерованы точками множества X, определяемую следующим образом:

Определение схемы отношений эквивалентно утверждению, что являются -матрицами из элементов 0, 1, удовлетворяющими следующим свойствам:

Действительно, элемент с координатами стоящий в левой части равенства (21.5), равен числу путей вида в графе. Кроме того, строки и столбцы матрицы содержат единиц:

Алгебра Боуза-Меснера. Рассмотрим векторное пространство , состоящее из всех матриц вида действительные числа. Согласно условию (i) эти матрицы симметричны. В силу (ii) матрицы линейно независимы и размерность пространства равна По условию замкнуто относительно умножения, причем умножение коммутативно. Кроме того, умножение ассоциативно (умножение матриц всегда ассоциативно; ассоциативность следует также из (21.2)). Эта ассоциативная коммутативная алгебра называется алгеброй Боуза-Меснера схемы отношений.

Так как матрицы алгебры симметричны и коммутируют друг с другом, то они могут быть одновременно диагонализированы (Маркус и Минк [915]), т. е. существует матрица такая, что каждой матрице соответствует диагональная матрица где

Следовательно, алгебра полупроста и имеет однозначно определяемый базис из примитивных идемпотентов Они представляют собой действительные -матрицы, удовлетворяющие условиям (см. Барроу [212], Огава [1008], Веддербарн

Согласно условиям (21.3) и (21.6) матрица является примитивным идемпотентом, поэтому мы всегда можем выбрать

Итак, мы имеем два базиса алгебры и поэтому выразим один базис через другой, положив

где - однозначно определенные действительные числа.

Из соотношений (21.8), (21.9) и (21.11) получается, что

Следовательно, числа являются собственными значениями матрицы Кроме того, линейная оболочка столбцов матрицы совпадает с собственным подпространством шсех матриц Обозначим через размерность собственного подпространства, т. е. кратность собственного значения

Обратно, чтобы выразить через матрицы обозначим через действительную -матрицу

и пусть

Будем называть собственными матрицами схемы. Тогда

Теорема 2.

Доказательство. Нетривиально лишь последнее равенство. Так как — идемпотент, то диагональными элементами матрицы (см. равенство (21.7)) являются элементы 0 и 1. Следовательно,

Поскольку ибог, из (21.15) получается, что

Упражнение. (1). Показать, что Теорема 3. Собственные значения удовлетворяют следующим соотношениям ортогональности:

Кроме того,

На матричном языке это означает, что

где

Доказательство. Собственными значениями матрицы являются числа кратность которых равна В силу (21.5)

что доказывает равенства (21.16) и (21.19). Согласно (21.19)

что доказывает равенства (21.17), (21.18) и (21.20).

Следствие 4.

Доказательство. Приравняем собственные значения в выражении (21.5).

Изоморфная алгебра -матриц. Мы кратко отметим, что существует алгебра -матриц, изоморфная алгебре с которой часто проще работать. Пусть

Тогда из равенства (21.2) получается, что

Таким образом, матрицы перемножаются так же, как и матрицы Так как то отсюда следует, что линейно независимы. Следовательно, алгебра состоящая из всех матриц вида действительные числа), представляет собой ассоциативную коммутативную алгебру, изоморфную алгебре при отображении Согласно следствию 4

откуда вытекает, что являются собственными значениями матрицы (Или, иначе, матрицы имеют одинаковые собственные значения, так как алгебры изоморфны). Поскольку много меньше чем то числа иногда легче найти таким способом.

Рассмотрим теперь несколько примеров.