Альпин Ю А_Неотрицательные матрицы. Неотрицательные матрицы
 Скачать 0.57 Mb.
|
|
UBU T ⇐⇒ a ij = b σ(i)σ(j) ∀ i, Равенства в правой части (9) означают, что) σ — изоморфизм графа A на граф B ( a ij 6= 0 ⇐⇒ b σ(i)σ(j) 6= откуда следует условие (8)) 2) изоморфизм σ сохраняет веса дуг, то есть вес дуги i → j в графе A равен весу дуги σ(i) → σ(j) в графе И наоборот, свойства 1) и 2) биекции σ кратко записываются в виде равенств a ij = для любых i, j. Таким образом, из (9) следует Теорема 2. Матрицы A и B перестановочно подобны тогда и только тогда, когда существует изоморфизм графа A на граф сохраняющий веса дуг. Замечание 1. Как было сказано выше, матрицы можно рассматривать как нагруженные графы. Изоморфизм нагруженных графов естественно определить как перестановку σ : N → N, сохраняющую веса дуг. Такие перестановки как рази описываются равенствами. Если принять это определение, то теорему 2 можно сформулировать так матрицы A и B перестановочно подобны соответствующие им нагруженные графы изоморфны. Задача 16. Переставляющие матрицы это в точности неотрицательные ортогональные матрицы. То есть ≥ 0 и UU T = E ⇐⇒ U— переставляющая матрица. Задача 17. Отношение перестановочного подобия рефлексив- но, симметрично и транзитивно, то есть является отношением эквивалентности. Следовательно, оно разбивает множество всех матриц порядка n на классы перестановочного подобия. Каждый класс содержит конечное множество матриц. Сколько матриц в классах матриц, E, E ij , A = diag(1, 2, . . . , n) Портреты матриц. Портретом неотрицательной матрицы A = § 1. Графы и портреты матриц) называется матрица B = (b ij ) с элементами, если a ij > 0, 0, если a ij = Матрицей смежности графа с вершинами 1, 2, . . . , n называется матрица B = (b ij ) порядка n, в которой, если i → j, 0 в противном случае. Таким образом, всякому графу сопоставлена (матрица. И наоборот, любая квадратная (матрица очевидным образом определяет граф. Ясно, что портрет матрицы A есть матрица смежности графа матрицы Граф и портрет неотрицательной матрицы, будучи более простыми объектами, отражают её важные свойства и дают удобный языки вычислительное средство для теории неотрицательных матриц. Символы 0 ив портрете матрицы мы будем считать ненатуральными числами, а элементами булевой алгебры, в которой сложение и умножение задаются следующими таблицами 0 1 0 0 1 1 1 1 , ¯ 0 1 0 0 0 1 0 Нетрудно проверить, что операции в этой алгебре обладают привычными свойствами ассоциативности, коммутативности, а также дистрибутивности умножения относительно сложения (но вычитание не определено). Будем называть (матрицу булевой, если се элементами мы намерены обращаться по правилам булевой алгебры. Для упрощения записи вместо a⊕b и a¯b будем писать a+b итак как из контекста будет видно, когда действие происходит в булевой алгебре. Матрицы над булевой алгеброй складывают и умножают по обычным правилам, при этом сохраняются известные свойства операций с матрицами (с теми же доказательствами). Обозначим портрет матрицы A символом Sg(A). Следующее простое утверждение является основой применения булевых матриц в теории неотрицательных матриц. Лемма 4. Если A, B — неотрицательные матрицы, то) Sg(A + B) = Sg(A) + Sg(B), Комбинаторика матриц) Sg(AB) = Таким образом, если мы желаем знать, как расположены ненулевые элементы в сумме (произведении) неотрицательных матриц, то для этого достаточно вычислить сумму (произведение) их портретов. Пусть A = (a ij ) — квадратная неотрицательная матрица и булева матрица B = (b ij ) — её портрет. Из второго утверждения леммы следует, что) = B k , k = 1, 2, . . Или, на языке элементов 0 ⇐⇒ b (k) ij = Задача 18. Докажите, что графы изоморфны тогда и только тогда, когда их матрицы смежности перестановочно подобны. Задача 19. Пусть B — булева матрица смежности графа с вершинами. Докажите, что) (E + B) m = E + B + . . . + B m , m = 1, 2, . . . ; 2) вершина j достижима из вершины i ⇔ (B+B 2 +. . .+B n ) ij = 1; 3) граф сильно связен ⇔ все элементы (E + равны Здесь E — булева матрица, диагональные элементы которой равны, а прочие равны 0. § 2. Примитивные матрицы и графы Напомним, что матрица A ≥ 0 называется примитивной, если 0 при некотором показателе k. Граф называется примитивным, если существует такое число k, что из любой вершины в любую другую можно перейти путём длины k. Ясно, что матрица примитивна в точности тогда, когда примитивен её граф. Назовём матрицу ≥ 0 полупримитивной, если при некотором показателе k матрица A k содержит положительный столбец. Это значит, что в графе A есть вершина, достижимая из любой вершины заодно и тоже число шагов. Назовём такую вершину фокусом, аграф, содержащий фокусы полупримитивным. В полупримитивном графе нет висячих вершин. Следовательно, из каждой вершины выходит путь какой угодно длины. Это значит, что любая степень полупримитивной матрицы не содержит нулевых строк. Лемма 1. Если й столбец положителен в матрице A k , то он положителен в при всех l > k. Другими словами, если фокус § 2. Примитивные матрицы и графы достижим из всех вершин путями длины k, то он достижим и путями длины l > Действительной столбец матрицы равен произведению положительного го столбца на матрицу без нулевых строк. Очевидно, что это произведение является положительным столбцом. Следствие 1. Если A k > 0, то A l > 0 при всех l > Лемма 2. Из фокуса достижимы лишь фокусы. Д ока за тел ь ст во. Пусть фокус i достижим из всех вершин за k шагов. Если i → j, то вершина j достижима из всех вершин за + 1 шагов и тоже является фокусом. Из леммы 1 вытекает, что при любом достаточно большом показателе столбцы матрицы A k , отвечающие фокусам, положительны. В частности, матрица A примитивна, если все вершины её графа фокусы. В общем случае согласно лемме 2 имеет место Предложение 1. Фокусы полупримитивного графа порождают замкнутый примитивный подграф. Отсюда моментально следует Теорема 1. Если матрица A полупримитивна и неразложима, то она примитивна. Будем говорить, что вершины и совместимы, если из этих вершин синхронно, то есть путями одинаковой длины, достижима некоторая общая вершина. Предложение 2. Для полупримитивности графа необходимо и достаточно, чтобы любые две его вершины были совместимы. Д ока за тел ь ст во. Необходимость условия очевидна. Докажем достаточность. Пусть из вершин 1 и 2 синхронно достижима вершина j, из вершины 3 за шагов достижима вершина l, из вершин и l синхронно достижима вершина m. Тогда, очевидно, из вершин 1, 2, 3 вершина m достижима за (k 1 + k 2 ) шагов. Продолжая аналогично, получим, что из вершин 1, 2, . . . , n есть пути длины+ k 2 + . . . + в некоторую вершину p, являющуюся фокусом. Из следствия 1 и предложения 2 автоматически получается Теорема 2. Матрица A ≥ 0 примитивна тогда и только тогда, когда она неразложима и любые две вершины в графе A совместимы Комбинаторика матриц Задача 1. Пусть в графе матрицы A ≥ 0 вокруг фокуса j есть петля. Тогда й столбец матрицы положителен. Другими словами, из любой вершины в фокус j можно попасть за n − 1 шагов. Задача 2. Покажите на примере, что матрица AB может быть не примитивной притом, что A ≥ 0 и B ≥ 0 — примитивные матри- цы. Задача 3. Пусть A и B — неотрицательные матрицы без нулевых строки столбцов. Если AB — примитивная матрица, то и BA примитивная матрица. Задача 4. Пусть A и B — неотрицательные матрицы. Докажите, что 1) если A неразложима, то и A + B неразложима; 2) если A примитивна, то и A + B примитивна. Задача 5. Пусть матрица A ≥ 0 такова, что AA T > 0. Докажите, что A полупримитивна. Задача 6. Пусть матрица A неразложима и имеет положительный элемент на диагонали. Докажите, что A примитивна, причём A 2n−2 > 0. Другими словами, в графе A из любой вершины в любую другую можно попасть за 2n − 2 шагов. Проверьте, что матрица = 1 1 0 . . . 0 0 0 1 0 0 · · · · · 0 0 0 . . . 1 1 0 0 . . . удовлетворяет условию задачи и докажите, что матрица A 2n−3 ещё содержит нули. Этот пример показывает, что показатель 2n − 2 в утверждении задачи нельзя уменьшить. Задача 7. Если вершина i является фокусом в графах матриц и A T , то матрица A примитивна. Задача 8. Докажите, что матрица A ≥ 0 неразложима тогда и только тогда, когда матрица E + A примитивна. Задача 9. Назовём контурным индексом графа наибольший общий делитель длин контуров графа. Контурным индексом матрицы будем называть контурный индексе графа. Докажите, что контурный индекс полупримитивной матрицы равен единице. Задача 10. Пусть матрица A порядка n имеет вид A = µ 0 B C 0 ¶ , причём B и C — положительные матрицы, нулевые блоки § 3. Форма Фробениуса импримитивной матрицы 17 не обязательно квадратные. Докажите, что матрица A неразложима. Пусть левый верхний блок имеет l строки столбцов. При каких и m матрица A примитивна Если примитивна, то как зависит от l и минимальный показатель k, при котором A k > 0? § 3. Форма Фробениуса импримитивной матрицы В этом параграфе мы установим комбинаторную структуру неразложимой, ноне примитивной, матрицы. Такие матрицы называются импримитивными. Разбиение множества вершин графа называется циклическим, если факторграф поэтому разбиению есть простой контур. Существует нумерация классов циклического разбиения, C 2 , . . . , при которой все дуги с началом в классе ведут в класс C 2 , дуги с началом введут в итак далее наконец, дуги изведут в C 1 Назовём описанную нумерацию классов правильной. Будем говорить, что класс следует за классом при t ≤ d − 1, класс следует за Пусть для графа матрицы циклическое разбиение существует и правильная нумерация (1) классов получена. Далее перенумеруем вершины графа вначале вершины класса C 1 , потоми т.д. Про- изведём перестановку строки столбцов матрицы соответственно новой нумерации вершин и разобъём полученную матрицу на блоки, соответствующие классам. В результате получим матрицу = 0 A 12 0 ... 0 0 0 A 23 ... 0 .. .. .. .. .. 0 0 0 0 A d−1,d A d1 0 0 Матрицу типа (2) будем называть блочно-циклической. У такой матрицы нулевые диагональные блоки — квадратные, единственный ненулевой блок блочной строки является правым соседом диагонального блока, в нижней блочной строке единственный ненулевой блок занимает левый нижний угол. Количество блочных строки столбцов) называется блочным порядком матрицы. Как видим, циклическое разбиение множества вершин приводит к блочно-циклической форме матрицы Комбинаторика матриц И наоборот, всякой блочно-циклической матрице формы (2) естественным образом соответствует циклическое разбиение множества вершине графа. А именно, если n 1 , n 2 , . . . , n d — порядки диагональных блоков, той класс разбиения состоит из первых n 1 вершин, 2-й класс — из следующих вершин, итак далее. Граф допускает, вообще говоря, различные циклические разбиения, соответственно, матрица может быть приведена к различным блочно-циклическим формам. Если граф допускает циклическое разбиение на d классов, топе- реход из вершины в вершину того же класса возможен, очевидно, лишь за число шагов, кратное d. Определим понятие темпорального подграфа. Множеством вершин темпорального подграфа является класс циклического разбиения, дуга ij в темпоральном подграфе существует, если в графе существует (i, путь длины При возведении блочно-циклической матрицы (2) в степень d получается блочно диагональная матрица A d = A (d) 11 A (d) 22 A (d) dd . (3) Назовём диагональные блоки матрицы (3) темпоральными под- матрицами матрицы (2) (отвечающими данному циклическому раз- биению). Предложение 1. Если темпоральные подматрицы матрицы типа (2) примитивны, то она неразложима. Д ока за тел ь ст во. Пусть число l так велико, что в матрице A ld диагональные блоки положительны. Тогда матрица имеет блочную структуру вида × 0 ... 0 0 0 × ... 0 .. .. .. .. .. 0 0 0 0 × × 0 0 0 0 , (4) причём блоки, отмеченные крестиками, положительны. Это значит, что из любой вершины любого класса циклического разбиения Ω, за + 1 шагов можно перейти в любую вершину следующего класса. Отсюда, конечно, следует, что A неразложима. ¤ § 3. Форма Фробениуса импримитивной матрицы 19 Неотрицательная блочно-циклическая матрица (2) называется формой Фробениуса если её темпоральные подматрицы примитивны. Основная цель этого параграфа – доказать, что всякая неразложимая неотрицательная матрица либо примитивна, либо приводится к форме Фробениуса. Удобнее рассуждать в графовых терминах. Вернёмся к отношению совместимости вершин и докажем, что для сильно связного графа это отношение является эквивалентностью, причём разбиение на классы совместимости циклично. Вначале нам потребуется Лемма 1. Если из вершины i сильно связного графа синхронно достижимы вершины j и k, то из вершин j и k синхронно достижима вершина Доказательство. Пусть вершины j и k достижимы из вершины i путями длины l. Поскольку граф сильно связен, то существует путь изв некоторой длины p, а также путь изв некоторой длины q. Тогда существует контур длины l + p i → · · · → j → · · · → а также контур длины l + q i → · · · → k → · · · → Проходя по первому контуру l + q раза по второму контуру l + p раз, получим два контура одинаковой длины (l+p)(l+q) с началом i. Удалив из этих контуров начальные отрезки длины l, получим искомые пути из j ив одинаковой длины (l + p)(l + q) − l. Лемма 2. Бинарное отношение совместимости на множестве вершин сильно связного графа является отношением эквивалентно- сти. Д ока за тел ь ст во. В сильно связном графе нет тупиковых вершин, это обеспечивает рефлексивность. Симметричность видна непосредственно из определения совместимости. Докажем транзитивность. Пусть из вершин и достижима вершина j 1 , а из вершин i 2 и достижима вершина j 2 . Можно считать, что k 1 = k 2 = Действительно, если, например, k 1 < k 2 , то пути из ив можно продолжить общим путём длины k 2 −k 1 . По лемме 1 существуют пути некоторой длины m из ив. Следовательно, существуют пути длины k + m из вершин ив общую вершину i 2 , что и доказывает транзитивность. ¤ Комбинаторика матриц Лемма 3. Разбиение множества вершин сильно связного графа на классы совместимости является циклическим. Д ока за тел ь ст во. Пусть дан какой-нибудь класс T . Вершины, дуги из которых ведут в T , совместимы, следовательно, лежат в некотором одном классе S. Следовательно, факторграф нашего графа характеризуется тем, что в каждую его вершину входит ровно одна дуга. Кроме того, он связен, как факторграф связного графа (задача 15, с. Используя задачу 1 (с, заключаем, что рассматриваемый факторграф является простым контуром. Это доказывает лемму. Определим индекс совместимости сильно связного графа как количество классов совместимости. Другими словами, индекс совместимости равен максимальному числу попарно несовместимых вершин. Индекс совместимости неразложимой матрицы по определению равен индексу совместимости графа этой матрицы. Теорема 1. Пусть A ≥ 0 — неразложимая матрица с индексом совместимости d. Если d = 1, то матрица A примитивна. Если > 1, то матрица A некоторой перестановкой рядов приводится к форме Фробениуса. Д ока за тел ь ст во. Если d = 1, то любые две вершины совместимы и матрица A примитивна по теореме 2 (с. Пусть > 1. Согласно леммами имеется циклическое разбиение множества вершин графа матрицы A на классы совместимости. Пусть правильная нумерация C 1 , C 2 , . . . , классов уже призведена и соответствующая блочно циклическая матрица (2) построена. Докажем, что темпоральные подматрицы матрицы (2) примитивны. Достаточно доказать это для подматрицы |