[МУЗЫКА] [МУЗЫКА] Итак, мы, наконец, готовы переходить к третьему определению схемы отношений в матричной терминологии. Как же мы сделаем шаг в мир матриц? Рассмотрим схему отношений с d классами (R0, R1, ..., Rd). Определим для каждого из отношений Ri соответствующую ему матрицу смежности Ai следующим образом: на xi-той позиции матрицы Ai стоит единица, если (x, y) принадлежит нашему отношению Ri, и ноль в обратном случае. Если вспомнить графовую интерпретацию схем отношений, то матрица Ai — это будет, соответственно, матрица смежности графа, построенного на множестве Ω, и с ребрами, соответствующими отношению Ri. Что же, формальное определение: схема отношения с d классами, определенная на множестве Ω мощности n, называется такой набор квадратных матриц A0, A1, ..., Ad порядка n, состоящий только из нулей и единиц, для которых выполняются следующие условия: первое условие — A0 матрица — это в точности единичная матрица; второе условие — каждая из матриц Ai является симметричной для всех i от единицы до d; третье условие — для произвольных i, j из множества от единицы до d произведение матриц Ai * Aj является линейной комбинацией матриц A0, ..., Ad. Иными словами, Ai, умноженная на Aj, — это сумма Ak-тых с коэффициентами pijk, где суммирование у нас идет по k от нуля до n. И заключительное условие, что сумма всех матриц дает матрицу, целиком состоящую из единиц, при этом ни одна из матриц Ai тождественно не равна нулевой матрице. Давайте обсудим получившееся определение. Во-первых, заметим, что нам даже не нужно накладывать условия на то, чтобы коэффициенты pijk из третьего условия были целыми. Так как наши матрицы состоят только из нулей и единиц, то и в их произведении, очевидно, будут получаться лишь целые неотрицательные числа. Почему же условие 3 все-таки будет иметь именно такой вид? Давайте посмотрим на это как на матричное уравнение и посмотрим, что у нас получается слева и справа на позиции xi. Так как пара (x, y) обязательно принадлежит к какому-то отношению Rk, то справа на соответствующей позиции будет стоять в точности значение pijk, которое нас интересует. Что же в это время у нас происходит в левой части? Начнем с того, что просто по определению мы распишем операцию перемножения матриц. Далее заметим, что выражение Ai(x, z), умноженное на Aj(z, y) не равно нулю тогда и только тогда, когда не равен нулю каждый из сомножителей. То есть когда одновременно (x, z) принадлежит Ri, потому что именно в таком случае у нас будет стоять единичка на этой позиции, а пара (z, y) у нас будет принадлежать отношению Rj. Таким образом, мы в точности получаем определение индекса пересечения pijk, как указано на экране. Переходим к следующей лемме, которая будет важна для материала следующей лекции. Итак, пусть есть матрица смежности некоторой схемы отношений, тогда для любых i, j от нуля до d матрицы Ai и Aj коммутируют, то есть произведение матриц не зависит от порядка, в котором мы эти матрицы умножили. Так как наши матрицы симметричны, мы получаем следующую цепочку. Рассмотрим Aj, умноженную на Ai. В силу симметричности Aj транспонированная совпадает с Aj, а Ai транспонированная совпадает с Ai. Запишем это, вынесем транспонирование вовне и запишем выражение под знаком транспонирования в виде суммы, то есть линейной комбинации матриц. А дальше опять вспоминаем, что у нас все матрицы симметричные, вносим транспонирование и меняем Ak-тую транспонированную на Ak. Таким образом, в итоге мы получаем выражение для Ai, умноженное на Aj. Смотрим на правую часть, смотрим на левую часть — наши матрицы коммутируют, что и требовалось доказать. Итак, после всего вышеперечисленного, если мы очень хорошо и внимательно разобрались с каждым из определений, у нас должно возникнуть ощущение, что мы все время говорили об одном и том же. И это правильно, потому что это были три эквивалентных определения одного и того же понятия. Теперь мы проделаем обратный трюк и, наоборот, посмотрим, как из схемы отношений возникают какие-то другие объекты, с которыми мы уже хорошо знакомы. Но, прежде чем перейти к этому, давайте обсудим, что мы можем сказать про индексы пересечений, исходя только из определения, пока не уходя ни в какую конкретику схемы отношений. Прежде всего заметим, что из требований симметричности мы сразу получаем, что pijk у нас равен pjik. Кроме того, при i, не равном j, параметр pij0 равен нулю; аналогично p0jk равен нулю при j, не равном k, и pi0k равен нулю, если i не равно k. Значения p0jj и pi0i — оба равны единице. Для произвольного элемента x из множества Ω число элементов y таких, что (x, y) принадлежит отношению Ri, которое мы обозначали за Ai в прошлой лекции, в точности равно pii0. Это как раз регулярность нашего монохромного графа в терминах графовой интерпретации. Нетрудно увидеть, что сумма pijk при суммировании от нуля до d по индексу i у нас будет в точности aj, а сумма всех ai-тых значений это будет n, то есть мощность нашего множества Ω. Кроме того, pijk, умноженное на ak, равно pikj, умноженное на aj. Теперь выберем произвольную пару (ω, z) из отношения Rm и двумя способами посчитаем четырехугольники на вершинах ω, x, y, z, где (ω, x) у нас из отношения Ri, а (x, y) — из отношения Rj, и последняя пара (y, z) — из отношения Rk. Мы получим следующее выражение, которое с вашего позволения я не буду зачитывать — вы можете посмотреть на экране. И перечислим все, что мы с вами рассмотрели, в виде итоговой теоремы, которая указана на слайде. Напомню, что δij — это символ Кронекера, который равен единице, если индекс i равен j, и нулю, если индексы не совпадают. А теперь переходим к обещанной связи с объектами, с которыми вы уже должны быть хорошо знакомы. Для этого нам потребуется особый класс схем отношений, которые называются «метрические схемы отношений». Что же это такое? Такие схемы возникают в том случае, когда существует некоторая нумерация отношений, что Ri у нас соответствует отношению нахождения на расстоянии i, то есть пара (x, y) принадлежит отношению Ri тогда и только тогда, когда расстояние между ними равно i, если мы рассматриваем граф во множестве Ω с ребрами, соответствующими отношению R1. Таким образом, мы можем сформулировать эквивалентное определение дистанционно регулярного графа, что связанный граф Г диаметра d называется дистанционно регулярным, если Гi образует схему отношений, где Гi — это множество всех пар, находящихся на расстоянии i. Таким образом, любой дистанционно регулярный граф задает схему отношений, а некоторые из получающихся схем отношений представляют особый интерес у специалистов из разных областей. Например, схема Хэмминга и схема Джонсона для специалистов по теории кодирования являются как объектом изучения, так и инструментом, с помощью которого можно изучать различные структуры, которые им интересны. Как пишет в своей работе [НЕРАЗБОРЧИВО] Левенштейн, все рекодирование в смежных областях схемы отношений можно рассматривать как некоторое структурированное пространство, в котором живут интересующие исследователя объекты, такие как коды или дизайны. Давайте посмотрим, что же за схема Хэмминга. Схема Хэмминга, как можно, очевидно, догадаться возникает из дистанционно регулярного графа Хэмминга. Давайте вспомним, как она получается. Пусть Q — это алфавит из q символов, множеством вершин графа Хэмминга и соответственно множеством вершин нашей схемы отношений будет являться набор всех слов длины n с элементами из нашего алфавита Q, и два слова будут i-связаны, то есть находиться в отношении Ri, если они отличаются в i позициях. Данная схема будет иметь n классов. Второй схемой отношений, которой мы уделим внимание, будет являться схема Джонсона, которая соответственно возникает из графа Джонсона. В качестве множества Ω тут у нас уже выступают k-элементные подмножества некоторого фиксированного множества из v элементов. И две вершины x и y будем считать i-связанными, если мощность пересечения соответствующих подмножеств равна (k – i). Получившаяся схема отношений будет иметь k классов.
