Содержание к диссертации
Введение
Глава 1. Матрицы бинарных отношений 10
1.1. Понятие бинарного отношения. Матрица бинарного отношения . 10
1.2. Множество квадратных матриц из нулей и единиц 12
1.3. Операции над отношениями, основные определения 14
1.4. Определение цепи, пути. Ацикличное бинарное отношение и его свойства 19
1.5. Построение матрицы ацикличного отношения 21
Глава 2. Разложимые и неразложимые матрицы 28
2.1. Используемые определения 28
2.2. Теорема о разложимости и неразложимости в терминах матриц бинарных отношений 29
2.3. Алгоритм, позволяющий исследовать матрицы на разложимость и приводящий разложимую матрицу к каноническому виду . 34
2.4. Алгоритм исследования неразложимой матрицы и приведения импримитивной матрицы к канонической форме 38
Глава 3. Перестановочное подобие матриц 42
3.1. Р-иодобие матриц 42
3.2. Необходимое условие Р-подобия матриц и достаточное условие Р-подобия для отдельного вида матриц 45
3.3. Автоморфизмы матриц перестановок 4G
Глава 4. Матричный метод проверки изоморфизма графов 48
4.1. Изоморфизм графов, матричная интерпретация 48
4.2. Матричные инварианты преобразования Р-подобия 51
4.3. Общий алгоритм решения задачи Р-подобия 54
4.4. Матрицы смежностей обыкновенных графов 59
4.4.1. Алгоритм проверки Р-иодобия матриц 60
4.4.2. Необходимые и достаточные условия Р-подобия G3
Заключение 6G
Литература
- Множество квадратных матриц из нулей и единиц
- Теорема о разложимости и неразложимости в терминах матриц бинарных отношений
- Необходимое условие Р-подобия матриц и достаточное условие Р-подобия для отдельного вида матриц
- Общий алгоритм решения задачи Р-подобия
Введение к работе
Данная работа посвящена изучению матриц бинарных отношений, то есть квадратных (ОД)-матриц, в контексте исследования графов, бинарных отношений и теории подстановок. Такой матричный подход, основанный на использовании (ОД)-матриц, достаточно удобен и логически оправдан но следующим причинам. Во-первых, потому что существует взаимно однозначное соответствие между матрицами и графами, матрицами и бинарными отношениями, матрицами и подстановками. Во-вторых, на данный момент существует достаточно мощный математический пакет Mat-lab, основным элементом данных которого является массив, что позволяет решать задачи, в которых используются матрицы и вектора, в несколько раз быстрее, чем при использовании скалярных языков программирования (СИ, Фортран). В-третьих, обычно выше перечисленные объекты (графы, бинарные отношения, подстановки) изучают как изолированные области, матрицы же позволяют рассматривать их как совокупность взаимно связанных объектов.
В работе нас будут интересовать в первую очередь квадратные (0,1)-матрицы, так как именно использование оных при изучении графов дает больше полезной информации, нежели при рассмотрении прямоугольных матриц. Использование матриц смежиостей позволяет привлекать к изучению матриц графов свойства характеристических многочленов этих матриц и их спектров. Также плюсом является то, что квадратные матрицы с отличным от нуля определителем образуют группу относительно операции умножения. В этой группе матрицы, у которых det = 1 или det = —1, образуют подгруппу, включающую в себя группу ортогональных матриц.
В этой подгруппе матрицы перестановок будут также образовывать свою подгруппу. Таким образом, можно изучать группу (ОД)-матриц используя ранее наработанный обширный научный материал по каждой из перечисленных выше групп.
В главе 1 рассматриваются основные понятия теории бинарных отношений в терминах квадратных (ОД)-матриц. Показана эффективность матричного подхода на примере изучения отдельных классов бинарных отношений, например ациклического бинарного отношения (см. теоремы (1.5..1), (1.5..2)).
Вторая глава посвящена применению квадратных (0,1)- матриц в изучении таких матричных свойств как разложимость (неразложимость), примитивность (импримитивность). Изложение доказательства теоремы о необходимых и достаточных условиях разложимости матрицы в терминах матриц бинарных отношений (см. [15, с. 432, теорема 6.2.23]) позволило извлечь из него конструктивный алгоритм приведения разложимой матрицы к специальному виду, через который, собственно, и дается определение разложимой матрицы. То есть разложимую матрицу А можно представить в следующем виде:
В
/
,
A = PAP' =
где В[ - квадратные неразложимые блоки, D - либо неразложимый
блок, либо верхнє треугольная матрица с нулевой диагональю. Данный канонический вид уточняет канонический вид предложенный в книге [5, с.373].
На основе полученных результатов был дополнительно разработан и алгоритм исследования неразложимых матриц и приведения импримитивной матрицы к следующей канонической форме:
Аг = PAP' =
/
О 0 ...
А21 О і А32 О
О Аіт
\
\
/
О ... О Лв(а_і) На диагонали стоят квадратные нулевые матрицы.
Необходимо заметить, что достоинство предложенных алгоритмов заключается не только в получении указанных канонических видов, но в нахождении матриц перестановок Р, осуществляющих переход от исходных матриц к их каноническим формам.
К тому же предложенные алгоритмы были унешно реализованы в качестве самостоятельной программы исследования выше указанных матричных свойств.
В третьей главе рассматривается понятие перестановочного подобия матриц. То есть преобразования при котором переход от первой матрицы ко второй совершается с помощью умножения первой матрицы слева на некоторую матрицу перестановки Р ([15, с. 39, с. 430]), а справа на матрицу
P' - транспонированную к Р (см. опр. (3.1..2)). Матрицу Р так же называют и матрицей подстановки ([13, с. 19]). Такое преобразование называется перестановкой рядов ([5, с. 352], то есть перестановка строк и точно такая же перестановка столбцов. Очевидно, что Р' = Р~1, а значит ([5, с. 80, опр. 10]) вышеуказанный переход является преобразованием подобия с матрицей перестановки. Такое преобразование называется преобразованием Р-подобия (перестановочного подобия, см. [15, с.183]).
Вводятся необходимые условие Р-подобия матриц и достаточное условие Р-подобия для отдельного вида матриц.
Далее рассматривается автоморфизмы матриц бинарных отношений, то есть класс матриц G,i = {Р PAP' = А}, Р - матрица перестановки, А -матрица бинарных отношений.
В четвертой главе рассматривается матричная интерпретация изоморфизма графов, устанавливается взаимноодонозиачнос соответствие между изоморфизмом графов и перестановочным подобием соответствующим графам матриц смежностей.
В рассматриваемых нами терминах графы будут изоморфными, если их матрицы смежностей Р-подобны. Другими словами, чтобы установить, изоморфны два графа или нет, необходимо установить, можно ли с помощью преобразования Р-подобия от матрицы первого графа перейти к матрице второго графа. Если такой переход возможен, то мы не только устанавливаем изоморфизм графов, но и указываем соответствующую нумерацию вершин первого графа, то есть переход, задаваемый матрицей , от первоначальной нумерации к искомой нумерации, в которой обе матрицы графов будут одинаковыми.
Понятно, что поиск необходимой матрицы Р равносилен перебору (число матриц перестановок n-ого порядка равно п\). Однако мы резко сократим число подлежащих испытанию матриц Р, если будехМ рассматривать матричные инварианты преобразования Р-подобия. Несовпадение инвариантов ведет к отрицательному ответу на вопрос об изоморфизме рассматриваемых графов.
Помимо рассмотрения набора матричных инвариантов вводится и следующее определение:
Определение. Назовем разнообразием матприцы А число всех различных строк в матрице А. Строки называются различными, если они отличаются друг от друга хотя бы одним элементом, располооїсениьім на одинаковых местах в строке.
На основе введенного опрделения составляется общий алгоритм проверки Р-подобия матриц.
Далее рассматривается класс матриц смежностей обыкновенных графов, алгоритм проверки Р-подобия таких матриц и построения матриц перехода Р, а так же формулируются следующие две теоремы о необходимых и достаточных условиях Р-подобия:
Теорема. Для того, чтобы две симметричные матрицы А и В размерности [п,п], SpA = SpB = О, были Р-подобпыми необходимо и достаточно, чтобы существовала такая матрица Р, что главные миноры второго порядка матриц В и РАР' совпадали.
Теорема. Для того, чтобы две симметричные матрицы А и В
»
»
размерности [п,п], SpA = SpB = 1, были Р-подобными иеобходимо и достаточно, чтобы существовала такая матргща Р, что диагональный ненулевой элементы переводился бы в аналогичный диагональный элемент и что главные миноры второго порядка матриц В и РАР' совпадали.
Множество квадратных матриц из нулей и единиц
Обозначим через Мп множество квадратных матриц из нулей и единиц. Введем на этом множестве матриц следующие операции:
1. Сложение +, = С = Л-\- В, Qj = iij -f %, где сложение элементов матриц происходит по правилу Булевой арифметики: 1+1=1, 0+1=1, 1+0=1, 0+0=0. Очевидно, что эта операция сложения замкнута на множестве Мп, что она ассоциативна, коммутативна и имеет нулевой элемент - введенную выше нулевую матрицу О.
2. Произведение , = С = А В, c,-jt = (an bit) 4- 4- (а,-„ bnk), і ДС -обыкновенное произведение для 0 и 1. Произведение g будет замкнуто на множестве Мп, ассоциативно, в общем случае не коммутативно. Единичным элементом будет обычная единичная матрица Е, которая, очевидно, принадлежит М„. 3. Адамарово произведение о, == С = А о В, Cjj = а btj. Адамарово произведение матриц замкнуто на множестве Мп, ассоциативно и коммутативно. Единичным элементом относительно Адамарова произведения, очевидно, будет матрица /, состоящая из одних единиц. Очевидно также, что Адамарово произведение матриц идемпотентпо, то есть А о А = А.
4. Операция дополнения. Введенную выше матрицу А мы будем называть дополнением к матрице А, а операцию сопоставляющую матрице А матрицу А операцией дополнения. Очевидно, что операция дополнения замкнута на множестве Мп и А-\-А = I, АоА = 0,1 = 0, 0 = 1.
Определение 1.2..1 Совокуппос7ПЬ матриц па мпооїсестве Мп будем называть линейно-независимой, если Адамарово произведение этих матриц равняется нулевой матріще.
Замечание 1.2..1 Нетрудно видеть, что ортогональные матрицы из нулей и єдиний,, так называемые матрицы перестановок, припадлеоісат мпооїсеству Мп и образуют группу относительно операции .
Замечание 1.2..2 Выше мы рассматривали отобраоїсепие, сопоставляющее каоїсдому бинарному отношению R матрицу бинарных отношений А, связанную с конкретным выбором нумерации элементов множества . Если обозначим через Р матрицу перестановок ([15, с. 39, с. 4$0])) определяющую переход от старой нумерации элементов мнооїсества к повой, то тому Dice самому бинарному отношению R yoice будет соответствовать матрица РАР , представляющая обычное произведение трех матриц (Р - означает транспонированную матрицу к матрице Р). Отсюда следует, что каоїсдому бинарному отношению соответствует целый класс матриц вида PAP , состоящий из п\ матриц. Иногда, чтобы подчеркнуть, что матрица А соответствует определенному бинарному отношению R мы будем писать A(R).
Замечание 1.2..3 Поскольку PAP = P g A g P ,ue дальнейшем мы будем рассматривать только введенные операции слооїсения и умнооїсения матриц из Мп, то, для упрощения записи (в пределах текущей главы), мы вместо " + " будем писать просто " + "; а вместо " 0 " использовать обычную запись умнооїсения, в том числе обычную запись степени матрицы относительно этого умнооїсения.
Замечание 1.2..4 Мпоэюество матриц Мп, с введенными выше операхщями 4-,) А образует булеву алгебру В. Нулевой элемент -матрица из нулей, единичный элемент - матриг а из едингщ. Всякая булева алгебра есть булево кольцо с единицей. Операции над отношениями, основные определения Операциям над отношениями из ХхХ сопосташім операции над матрицами из М„:
1. Пересечением отношений Лі и R2 (обозначается Ri П R2) называется отношение, определяемое пересечением соответствующих подмножеств из ХхХ. Пересечению R\ П . соответствует матрица A(R\ П RQ) = A(R\) о A(R2) , где о - Адамарово произведение.
2. Объединением отношений R\ и Ro (обозначается Ri U Ro) называется отношение, определяемое объединением соответствующих подмножеств из ХхХ. Объединению Ri U / соответствует матрица A{RiUR2) = A(Rl) + A(R2) . 3. Назовем произведением R\ и R2 отношение, определяемое следующим образом: x(RyR2)y, если существует z Є X, для которого xR\z и zRiy, где R\ R2- символ произведения отношений. Произведению Лі R2 соответствует матрица A(R\ R2) = -А(Яі) Л(Лг) 4. Обратным к отношению Я называется отношение R l, определяемое условием xR ly =3 yRx. В терминах матриц это запишется в виде A(R l) — A (R). Это очевидно так как: в одну сторону
Теорема о разложимости и неразложимости в терминах матриц бинарных отношений
Определение 2.1..1 (11, с. 145) Матрица А Є Мп (Мп - множество квадратных матриц) называется разлооїсимой, если существует собственное подмпоэ/сество J С {1,2, ..,п} такое, что а = 0, когда ІЗ J, j Є J. Определение 2.1..2 (15, с. 431) Матрица называется разлооїсимой, если либо А) п = 1 и А = 0, либо В) п 2 и существует матрица перестановки Р Є Мп и некоторое , (вс\ целое число г — 1, п — 1, такие что РАР — , пулевой блок \ D) имеет размерность п — гхг. Здесь не требуется, чтобы блоки В, С, D имели ненулевые элементы.
Определение 2.1..3 (11, с. 145) Нсразлооїсимой называется матргща А Є Мп, которая не является разлооїсимой и не является пулевой матрш ей порядка 1.
Определение 2.1..4 (11, с. 150) Пусть задана матрица А Є Мп. Тогда і-й элемент связан с j-м элементом, если существует цепочка элементов {ko,ki,..,kv}, связывающая ко = г с kv = j, то есть такая цепочка, что любые два последовательно идущих элемента ks и к3±\ непосредственно связаны в том смысле, что ад.д-8+1 = 1. Как известно, имеют место две леммы: Лемма 2.1..1 (11, с. 150) Матрица А Є Мп тогда и только тогда нсразлооїсима, когда элементы i,j связаны для всех і ф j. Лемма 2.1..2 (11, с. 151) Индексы i,j связаны тогда и только тогда, когда существует целое полооїситсльпос число к, что о& = 1 (элемент матрицы Ак).
Определение 2.1..5 (15, с. 429) Для матрицы А Є Мп запись А О (А 0) означает, что все элементы а неотрицательны (полоэюителыш). Теорема 2.2..1 (см. такоісе [15, с. 432]) Матрица А Є Мп разлооїсима тогда и только тогда, когда матргща (Е + А)п 1 имеет пулевые элементы. Доказательство. В доказательстве теоремы используется булево сложение и умножение матриц, несмотря на обычную запись операции умножения и сложения. 1. Пусть матрица А Є Мп разложима. Тогда существует такая матрица , в с\ , Р, что А = Р \Р = РАР . А значит: О D ) ( Еі + В С (Е + А) = Р(Е + А)Р = Р Р , У О Е2 + D где Е\,Е2 - единичные матрицы размерности, как у матриц В и D соответственно. Получаем зо (Е + A)n l = Р(Е + А)п 1Р = Р\ № + В)П І Р\ \ О (Е2 + D)n l то єсть (Е + А)п 1 содержит нулевые элементы. w 2. В обратную сторону. Пусть А = Е + А и пусть для некоторых г и 3 ( Ф 3) if1 — О (Щ[1 элемент матрицы Ап 1). В этих обозначениях а"- = a2j = 0) «?,- Х = 1 + ctjj = 1, поскольку ufl-1 \ Л \ Л и aij — / j / j агтпіатіі гп\ mn-2 im2 " amn-ij — 2_ i "-/ aimiamim2 am\mk-\amk-ij\ajj) + . . . — 2 - + . . . — 0, mi mk-\ Так как все слагаемые, как входящие в af так и неотмеченные равны либо і к нулю, либо единице, то из последнего соотношения следует, что Щ = 0 для всех А; = 1,п — 1. Очевидно, что a - - at-j, откуда следует, что все af- = 0 kjj flfj, откуда следует, что все a-j Таким образом, из Щ 1 — 0 мы получили, что из і в j нет никакого пути (эти индексы не связны).
Рассмотрим j-и столбец матрицы Ап . Обозначим через Si множество индексов Si = {plcipj1 = 1}, а через 52 = 01-1 = 0}. Другими словами, если матрица Л"-1 соответствует графу G и {хі, ...,} множество его вершин, то мы можем выделить два разбиения: V\ = {хр\хр — Xj или существует путь из Хр в Xj) и V L = {xi, ...,xn}\Vi соответственно. Ясно, что S iUS 2 = {1,2, ..,7i}, SiflS2 = 0, Si ф {1,2,..,n} и все индексы из множества S2 обладают тем же свойством, что и индекс і. Нетрудно видеть, что ни для одного элемента из V2 не существует пути ни в один элемент из Vi (или никакой индекс из S2 не связан ни с каким индексом из Si). Если бы это было не так, то есть существовал бы путі) из какого-то элемента xq Є V2 в какой-то хг Є V\, а значит существовал бы путь из хг в Xj. Это означает, что из xq существует путь в Xj, что противоречит построению множества V2 (ИЗ Xq ИСТ ІіуТИ В Xj). Si и 5 мы можем рассматривать как вектор-столбцы с элементами 21,.., И 4+1,.., СООТВеТСТВеННО (Zi,..,2jfc,ifc+i,..,2n Є {1,2,.., п}), то есть S[ = (г і,.., ik), S2 = (4-+1) hi), 4,--,in- перестановка элементов {1,2,..,n}. Пусть J = (1,2,.., n) и пусть PJ = I I, тогда S РЛР = A = An An 0 A22
Если Л(Л) - матрица рефлексивного бинарного отношения, то тогда Е-\-А = А и формулировку теоремы (2.2..1) можно записать в следующем виде: Теорема 2.2..2 Матрица рефлексивного бинарного отношения А Є Мп разлооїсима тогда и только тогда, когда матрица Ап 1 имеет нулевые элементы. Доказательство очевидно. То есть, мы можем выделять класс разложимых матриц рефлексивного бинарного отношения из всего множества квадратных (0,1)-матриц, используя предыдущую теорему.
Необходимое условие Р-подобия матриц и достаточное условие Р-подобия для отдельного вида матриц
Рассмотрим класс матриц G = {Р : РАР = Л}, Р - матрица перестановки, А - произвольная матрица.
Определение 3.3..1 Под автоморфизмом будем понимать отобраоїсенис матрицы самой на себя посредством преобразования Р-подобия.
Очевидно, что класс GA будет образовывать группу, которую в дальнейшем будем называть группой автоморфизмов. Действительно, 1. Пусть Рі,Р2Є GA, тогда Р{Р2 Є G/b так как P2PYAP[P 2 = А. 2. Ассоциативность же выполняется из-за ассоциативности произведения матриц. 3. Единичный элемент Е Є GA, так как ЕАЕ = А. 4. Если Р Є GA, ТО РАР = Л, откуда следует, что Р АР = Л, то есть Р Є GA. Не трудно видеть, что GA представляет собой класс перестановочных с А матриц.
Утверждение 3.3.Л Класс матриц GA отличен от тривиальной подгруппы, совпадающей с единичной матрицей Е, тогда и только тогда, когда Р-подобие матриц А и В (А ф В) не единственно, то есть существуют матрицы Р\ и Р2 такие, что Pi ф Р2 и Р\АР{ — Ви Р2АР = В.
Доказательство. Необходимость. Пусть PiAP[ = В и PiAP 2 = В, тогда Р2АР 2 = РіАР ї обозначив P-J-PL = Р, получаем, что PAP = Д то есть PeGAuP Е.
Достаточность. Пусть Р Є Gy\, Р Ф Е и пусть существует матрица Q такая, что QAQ = Б, следовательно QPAP Q = Р, то есть Р-подобие матриц А и В не единствешю.И
Возьмем две матрицы А, В и пусть существует Q Р, Р - класс перестановочных матриц, такая, что QAQ = В. Тогда A = Q BQ. Пусть Р Є С?д, следовательно РВР = В =
Q PBP Q = Q BQ=A=Q P{QQ )B(QQ )P Q=(Q PQ)(Q BQ)(QP Q ) = {Q PQ)A(QP Q )=A = РЛР = Л, где Р = Q PQ, и ясно, что Р Є GA. Поскольку Р Є GB бралось произвольно, то из Р Є GA следует, что Q GBQ С GA- Аналогично показывается, что QGAQ С GB- ИЗ последних двух включений следует QGAQ = GB-B
На основе вышеизложенного можно сформулировать утверждение-Утверждение 3.3..2 Если две матрицы Р-подобны, то их группы автоморфизмов сопряжены посредством матриц, осуществляющих преобразование Р-подобия.
Напомним еще раз определение самого бинарного отношения: Определение 4.1..1 (9, с. 15) Бинарным отношением R па мио жестве X называется подмпоэюество R миооїсества X х X, то есть RQ X х X. Будем пользоваться следующим определением графа.
Определение 4.1..2 (14, с. 89) Конечным графом G = (X,R) называется пара (X,R), где X - конечное мпооїсество вершин, a R - бинарное отношение па X.
Из данного определения следует, что как только вершины графа G = (X, R) перенумерованы, так бинарному отношению R однозначно сопоставляется матрица Л, которую в дальнейшем будем называть матрицей графа. Все сказанное выше относительно матриц бинарных отношений, очевидно, переносится на матрицы графа. Иногда введенную выше матрицу бинарных отношений (следовательно, и матрицу графа) называют матрицей смежностей или матрицей смежности.
Определение 4.1..3 (6, с. 35) Два графа G — (X,R) и Н = (Y,Q) называются изоморфными, если существует биекция ip : X — Y, такая, что для всех х,у Є X и z,t Є Y, для которых р(х) = z, (р(у) = t, из того, что xRy в G следует, что zQt в Н. Это определение можно переписать в следующем виде:
Определение 4.1..4 Два графа G = (X,R) и Н = (Y,Q) называются изоморфными, если существует нумерация элементов мпооїсеств X — {хі,Х2,...,хп} и Y = {уі,У2,—,Уп}, определяющая функцию р(хі) — уі такую, что (xi,Xj) Є R тогда и только тогда, когда (yi,yj) Є Q. Определение (4.1..4) эквивалентно следующим определениям: Определение 4.1..5 Два графа G = (X, R) и Н = (У, Q) будем называть изоморфными, если существует такая нумерация элементов множеств X и Y, при которой им будет соответствовать одна и та эюе матрица смеоісности.
Определение 4.1..G Два графа G = (X, R) и Н = (У, Q) будем называть изоморфными, если их матрицы графов Р-подобны меоіеду собой.
Определение (4.1..G) указывает путь поиска решения проблемы изоморфизма графов. Пусть при произвольной нумерации вершин графа G ему соответствует матрица А, графу Н в его собственной нумерации вершин - матрица В, таким образом проблема изоморфизма графов сводится к проблеме Р-подобия соответствующих им матриц смежности Л и В. Другими словами, проблема сводится к отысканию такой матрицы Р, что РАР = В. Если такая матрица существует, то графы G и Н изоморфны, если не существует, то графы не изоморфны.
Таким образом для ответа на вопрос об изоморфизме графов, необходимо получить ответ на вопрос о Р-иодобии их матриц смежности. Из замечания (4.1.1) следует, что данное определение позволяет использовать свойства Р-подобия матриц для изучения изоморфизма графов и следить за перенумерациями, производимыми с помощью матриц Р.
Общий алгоритм решения задачи Р-подобия
Алгоритм проверки Р-подобия матриц. Пусть у нас выполнены все необходимые условия Р-подобия для матриц смежиостей Л и В размерности [п,п] обыкновенных графов.
Рассматриваем матрицу Л. Если количество пулей у этой матрицы меньше, чем (n - 1)п/2, то строим дополнительную матрицу А такую, что А + (4.4) V / і і Тогда К = РКР = Р{А + А)Р = PAP + РАР = В + В,?о есть задачу проверки Р-подобия матриц А и В мы можем заменить эквивалентной задачей проверки Р-нодобия матриц А и В на основании теоремы (4.4..2).
Теперь начинаем работать с матрицами Л и В. У матрицы А число нулей больше, чем п(п — 1)/2. Если эта матрица разложима, то приводим ее к каноническому виду (методом из статьи [4]). И рассматриваем далее диагональные неразложимые блоки. Так как наши матрицы симметричные, то при применении алгоритма разбиения на неразложимые блоки, она становится квазидиагоналыюй. Параллельно проводим аналогичные действия и с матрицей В. Если надо, то для каждой неразложимой матрицы из диагональных блоков опять строим дополнительную, приводящую ее к виду (4.4), до тех пор пока не получим неразложимую матрицу с числом нулей большим, чем п(п — 1)/2.
Неразложимость матрицы гарантирует нам достижимость всех вершин, в соответствующем матрице графе. Добавление же одной петли в графе увеличивает разнообразие путей через данную вершину. А добавление единичного элемента в примитивной матрице приводит к понижению индекса примитивности, в импримитивной - к изменению вида матрицы на примитивный.
Далее строим вектор строчных сумм и ставим нашу единицу в блок с наименьшим числом различных элементов, то есть на диагональ, так чтобы она сказалась при учете строчных сумм указанного блока. Во второй матрице тоже ставим единицу на аналогичное место. И начинаем возводить матрицы в степень. Если же в процессе возведения в степень мы получаем различные составы у создаваемых матриц RlA и RlD, для некоторого /, то ставим единицу у второй исходной матрицы на второе соответствующее место в рассматриваемом подозрительном на подобие блоке и начинаем заново возводить в степень.
Если получаем полное разнообразие и одинаковые составы всех элементов в векторах строчных сумм, то сравниваем две матрицы и делаем выводы о Р-подобии или не Р-подобии оных. Если при одинаковом составе разнообразие не полное, то можно прибегнуть к методам, вытекающим из ниже приведенных теорем, или к уже сокращенной процедуре перебора.
Как было отмечено на примере рассмотрения матриц пятого порядка, начиная с некоторой степени разнообразие столбцовой суммы может оставаться постоянным, в то время как разнообразие элементов в столбцах растет. Тогда мы можем использовать это разнообразие для принятия решения о построении матрицы перехода - о том какие именно строки/столбцы мы должны переставлять местами.
Если же вне зависимости от расстановки единицы в подозрительном блоке второй матрицы у нас Р-иодобие не осуществляется, то значит исходные матрицы не Р-подобны.
Для того, чтобы две симметричные (0,1)-матрицы А и В размерности [п,п], SpA = SpB = О, были Р-подобпыми необходимо и достаточно, чтобы существовала такая матрица Р, что главные миноры второго порядка матриц В и РАР совпадали.
Доказательство. Необходимость. Пусть А и В Р-подобны. Тогда существует такая матрица Р, что В = РАР и для этой Р главные миноры второго порядка матриц В и РАР совпадают.
Достаточность. Пусть существует такая матрица Р, что главные миноры матриц В и С = РАР совпадают. Следовательно, —bf, = —с?- для всех г, j = 1,п, то есть bij = Cjj, а значит В = РАР или же матрицы В и /1 Р-подобны.
Теорема АЛ.Л Для того, чтобы две симметричные (0,1)-матрицы А и В размерности [п,п], SpA = SpB = 1, были Р-подобиыми необходимо и достаточно, чтобы существовала такая матрица Р, что диагональный ненулевой элементы переводился бы в аналогичный диагональный элемент и что главные миноры второго порядка матриц В и РАР совпадали. Доказательство. Необходимость. Доказательство необходимости полностью совпадает с доказательством необходимости предыдущей теоремы.
