[МУЗЫКА] [МУЗЫКА] Прежде чем перейти к обещанным алгебрам Боуза — Меснера, давайте вспомним несколько понятий из курса линейной алгебры. Матрица D называется диагональной, если она квадратная и все ее элементы вне главной диагонали равны нулю. В качестве примера можно взять единичную матрицу или, например, матрицу степеней произвольного графа. Квадратная матрица A называется диагонализируемой, если существует обратимая матрица P такая, что при умножении A на P справа и на P в −1-й слева мы получаем диагональную матрицу. Например, матрица A, представленная на экране, очевидно, не является диагональной, но если мы ее умножим на матрицу P справа, а затем слева на обратную к ней, то мы получим, как видно, диагональную матрицу. Таким образом, по определению, матрица A является диагонализируемой. Другим важным понятием является совместная диагонализация. Рассмотрим некоторое множество матриц Ai. Мы будем называть такое множество совместно диагонализируемым, если существует единственно обратимая матрица P такая, что какую бы матрицу Ai из нашего множества мы ни взяли и умножили описанным выше образом, мы всегда получим диагональную матрицу. Например, множество A с экрана совместно диагонализируемо с помощью представленной матрицы P. А множество B таким свойством не обладает. То есть мы не можем подобрать требуемую матрицу. Известно, что вещественные симметричные матрицы диагонализируемы при помощи ортогональных матриц. Напомню, что матрица ортогональная, если обратная к ней совпадает с транспонированной. Матрица E называется идемпотентной, если при умножении ее на саму себя мы получим в точности ту же самую матрицу E. То есть E, умноженное на E, равно E. Теперь давайте вспомним или узнаем, что такое алгебра. Речь, конечно же, пойдет не про ту алгебру, которая дисциплина в школьной программе, а про математический объект. Пусть A — это векторное пространство над некоторым полем F с операцией умножения, тогда A называется алгеброй над F, если для любых элементов x, y, z из A, а также коэффициентов αb, но уже из поля, выполняются следующие три условия. Примером алгебры, которая нам как раз таки потребуется в дальнейшем, будет множество всех квадратных матриц, элементы которой представлют собой вещественные числа. Данный пример, конечно, возник не случайно. Вспомним определение схемы отношений в матричной интерпретации. Пускай A0, A1, ..., Ad — это матрица смежности, соответствующей нашим отношениям в некоторой схеме отношений. Рассмотрим все линейные комбинации с коэффициентами из поля вещественных чисел, то есть следующее множество. Заметим, что это множество будет замкнуто относительно умножения матриц. То есть какие бы два элемента из этого множества мы ни взяли, при их умножении мы получим снова элемент из нашего множества. Также из условия, что при суммировании всех 01 матриц смежности мы получаем матрицу, j, состоящую из всех единиц следует, что матрицы Ai являются линейно независимыми. Если мы добавим к ним все остальные условия, которые у нас налагаются на матрицы, представляющие собой схему отношений, мы получим объект, который называют коммутативной алгеброй. Размерность ее будет d + 1. Также эта алгебра известна как алгебра Боуза — Меснера. Поскольку матрицы Ai коммутируют, они совместно диагонализируемы. Это гарантирует наличие второго базиса, состоящего уже из идемпотентных матриц, которые также удовлетворяют следующим условиям, представленным на экране. В качестве E0 возьмем матрицу из всех единиц, умноженную на единицу делить на n. Определим матрицы P и 1/n Q, связывающие наши два получившихся базиса алгебры. Результат вы видите на экране. Давайте посмотрим внимательно на это выражение. О чем оно нам говорит? Прежде всего, можно заметить, что элементы матрицы P, а именно, Pij — это собственные значения матрицы Aj. А столбцы матрицы Ei — это будут соответствующие собственные векторы. Таким образом, кратность mi собственного числа Pij будет равна рангу матрицы Ei при условии, конечно, что Pij не равно Pkj при k, не равном i. Тогда получаем, что m0 = 1. Сумма кратности, естественно, равна n. А mi будет равно следу матрицы Ei. Так как Ei в качестве собственных значений имеет лишь ноль и единицу, мы получаем, что ранг матрицы Ei равен в точности сумме собственных значений. То есть, как мы с вами знаем из второго модуля, следу матрицы. Справедлива следующая теорема, связывающая элементы матриц P и Q. Первые два набора соотношений не сложным образом получаются из определений и свойств наших базисов алгебры. Равенства, записанные в третьем пункте, носят название соотношения ортогональности. Рассмотрим случай схемы, соответствующей некоторому сильно регулярному графу с параметрами v, k, λ, μ и собственными числами k, соответственно, кратности единицы, r кратности f, и s кратности g. Тогда матрицы P и Q выписываются следующим образом, представленным на экране. Можем ли мы в произвольном случае сказать, как будут выглядеть матрицы P и Q? Оказывается, да. В этом нам поможет следующая важная теорема: при i от нуля до d собственными числами матрицы пересечений Lj являются Pij. С помощью этой теоремы довольно легко вычислить матрицу P, матрицу Q, которая является обратной к P с точностью до коэффициента, кратности mi, которые будут равны значению Q0i. И заметим, что требование на целочисленность mi, с одной стороны, кажется вроде бы довольно естественным, но, с другой стороны, оказывается, что это условие в совокупности с другими соотношениями на параметры схемы может приводить к довольно интересным результатам, касающихся различных объектов. В комбинаторике это, например, является мощным инструментом для получения верхних оценок на размер объектов или нижней оценки на их число. Кроме того, многие доказательства единственности существенно опираются на следствия, получающиеся в тех случаях, когда в неравенствах у нас достигается строгое равенство.