Альпин Ю А_Неотрицательные матрицы. Неотрицательные матрицы
 Скачать 0.57 Mb.
|
|
Казанский федеральный университет Институт математики и механики им. НИ. Лобачевского Кафедра алгебры и математической логики Ю.А. Альпин НЕОТРИЦАТЕЛЬНЫЕ МАТРИЦЫ Учебное пособие Казань — 2015 УДК Рекомендовано на заседании кафедры алгебры и математической логики Протокол №8 от 24 апреля 2015 г. Рецензент: кандидат физико-математических наук, доцент кафедры алгебры и математической логики С.Н. Ильин Альпин Ю.А. Неотрицательные матрицы / Ю.А. Альпин — Казань Казан. унт. — 58 с. Учебное пособие предназначено для студентов Института математики и механики КФУ. Изложены основы теории неотрицательных матриц, включая описание примитивных матриц и их экспонентов, построение нормальной формы импримитивной и разложимой матрицы, комплекс теорем Перрона–Фробениуса о спектре и собственных векторах неотрицательных матриц, асимптотику степеней примитивной матрицы. Представлены элементы идемпотентной линейной алгебры. Приведено большое число теоретических и вычислительных задач Альпин Ю.А., 2015 c ° Казанский университет, 2015 Оглавление Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Глава 1. Комбинаторика неотрицательных матриц . . . . . . . . . . 6 § 1. Графы и портреты матриц . . . . . . . . . . . . . . . . . . . . . . . 6 § 2. Примитивные матрицы и графы . . . . . . . . . . . . . . . . . . . . 14 § 3. Форма Фробениуса импримитивной матрицы . . . . . . . . . . . . 17 § 4. Экспонент примитивной матрицы . . . . . . . . . . . . . . . . . . . 23 § 5. Нормальная форма разложимой матрицы . . . . . . . . . . . . . Глава 2. Теория Перрона – Фробениуса . . . . . . . . . . . . . . . . . 30 § 1. Теорема Перрона – Фробениуса . . . . . . . . . . . . . . . . . . . . 30 § 2. Асимптотика степеней примитивной матрицы . . . . . . . . . . . . 33 § 3. Неравенства для перроновых корней . . . . . . . . . . . . . . . . . 35 § 4. Спектр импримитивной неотрицательной матрицы . . . . . . . . . 36 § 5. Случай разложимой матрицы . . . . . . . . . . . . . . . . . . . . . 38 § 6. Критерий существования положительного собственного вектора Глава 3. Элементы идемпотентной линейной алгебры . . . . . . . . 43 § 1. Неотрицательные матрицы характеристики 1 . . . . . . . . . . . . 43 § 2. Матрицы произвольной характеристики. . . . . . . . . . . . . . . . 46 § 3. Элементы идемпотентной линейной алгебры . . . . . . . . . . . . Глава 4. Дополнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 § 1. Модуль комплексной матрицы. Лемма Виландта . . . . . . . . . . 51 § 2. Локализация спектра матрицы . . . . . . . . . . . . . . . . . . . . 52 § 3. Норма матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Введение Изучение матриц с неотрицательными элементами со времени появления вначале го века основополагающих работ Перрона и Фро- бениуса привело к возникновению стройной и красивой теории. Развитие теории неотрицательных матриц обеспечивается как внутренними мотивами, таки приложениями в теории случайных процессов и математической экономике. О неотрицательных матрицах написано значительное количество книг (например, [1], [2]). На русском языке c теорией неотрицательных матриц можно познакомиться, соединив соответствующие главы из книг [3], [4], прибавив к ним книгу [5], а также книгу [6], которую в большой мере можно считать книгой о неотрицательных матрицах. Современные университетские учебники по алгебре и геометрии всё чаще включают главы о неотрицательных матрицах ([7], Особенностью изложения теории неотрицательных матриц в данном пособии, в отличие от упомянутых выше источников, является систематическое использование в определениях и доказательствах языка графов. Граф неотрицательной матрицы отражаете комбинаторную структуру, то есть взаимное расположение в ней положительных и нулевых элементов. Именно комбинаторная структура неотрицательной матрицы отвечает за важнейшие особенности её спектра и собственных векторов. Пособие содержит многочисленные задачи разной степени трудности, дополняющие изложение теории. Некоторые несложные утверждения приведены без доказательства в расчёте на то, что читатель докажет их самостоятельно. В таких случаях формулировка результата заканчивается значком ¤. Глава Комбинаторика неотрицательных матриц 1. Графы и портреты матриц Ориентированные графы. Ориентированным графом (орграфом) называется пара (V, E), где V — непустое множество вершин, E ⊆ V × V — множество дуг. Таким образом, дуга — это упорядоченная пара вершин. Обычно будем считать, что вершины пронумерованы натуральными числами, то есть множеством вершин служит множество. В дальнейшем, говоря о графах, мы всегда будем иметь ввиду ориентированные графы. Дуги можно записывать различно или i → j. Вершина i называется началом, а вершина j концом дуги ij. Говорят, что дуга ij выходит из i и входит вили ведёт из вершины i в вершину j). Дуга ii называется петлёй. На рисунке графа дуги графа изображаются стрелками. Запись i → иногда заменяет выражение "существует дуга, ведущая изв j". Путём длины k в орграфе называется любая последовательность вершин. . . такая, что i m i m+1 — дуга, m = 1, . . . , k. Здесь i 1 — начало, конец пути. Выражение "(i, путь" означает путь с началом в вершине и концом в вершине j. Путь, у которого конец совпадает с началом, называется замкнутым путём или контуром. Длина пути равна количеству его дуг. Очевидно, длина незамкнутого пути равна числу вершин минус единица, длина контура равна числу вершин. Введём операцию произведения путей. Произведение путей p = i 1 . . . и q = j 1 . . . определено, если последняя вершина p совпадает с первой вершина q. В этом случае = i 1 . . . i k j 2 . . . j m = i 1 . . . i k−1 j 1 . . . Произведение путей ассоциативно в том смысле, что если произведение определено, то произведение p(qr) тоже определено и = p(qr). Из ассоциативности следует, что скобки в произведении любого числа путей можно опустить. Заметим, что для пути путь pr существует в точности тогда, когда q — контур. Незамкнутый путь называется простым, если все его вершины различны, Контур называется простым, если все его вершины различны, кроме первой и последней § 1. Графы и портреты матриц 7 Лемма 1. В графе с n вершинами) длина простого (i, пути при i 6= j не больше, чем n − 1; 2) длина простого контура не больше, чем n; 3) если существует (i, путь, то существует и простой (i, j)- путь. Д ока за тел ь ст во. Длина (i, пути при i 6= j равна числу вершин пути минус единица, а длина контура равна числу вершин в контуре. Отсюда и из определения простого пути следуют пункты и 2). Чтобы доказать 3), рассмотрим произвольно взятый (i, j)-путь. Если он непростой, то его можно разложить в произведение вида, где q — контур (множитель или могут и отсутствовать). Удалив контур q, получим более короткий (i, путь r 1 r 2 . Если ион непростой, то продолжим удаление контуров. Ясно, что на некотором шаге получится простой (i, путь. Говорят, что из вершины i достижима вершина j, если существует, путь. Граф называется сильно связным или неразложимым, если из любой вершины достижимы все вершины, то есть любые две вершины взаимодостижимы. Граф без дуг называется пустым. Заметим, что пустой одновершинный граф считается разложимым. Пусть даны два графа. Говорят, что первый из них — подграф второго, если каждая вершина и каждая дуга первого графа принадлежат второму графу. Любое множество S ⊆ N вершин графа порождает подграф, вершинами которого являются элементы S, а дугами — все дуги исходного графа, соединяющие вершины из S. Ради простоты письма множество вершин и порождённый им подграф будем обозначать одной буквой. Термин "подграф" мы по умолчанию относим именно к подграфам, порождённым подмножествами вершин. Множество S вершин (и порождённый им подграф) называется замкнутым, если не существует дуг, ведущих из вершин S в вершины, не лежащие в Лемма 2. Граф с n ≥ 2 вершинами разложим тогда и только тогда, когда он содержит собственный замкнутый подграф. Д ока за тел ь ст во. Если подграф S ⊂ N замкнут, то, очевидно, из вершин этого подграфа недостижимы вершины из N \ S. И наоборот, если граф разложим, то для некоторой вершины i достижимы не все вершины, а лишь некоторое собственное подмножество вершин S(i) ⊂ N . Легко убедиться, что множество S(i) замкнуто. ¤ Комбинаторика матриц Наряду с понятием подграфа существенно понятие факторгра- фа по разбиению множества вершин. Вершины факторграфа – это классы разбиения, из класса S в класс T ведет дуга, если в исходном графе существует дуга с началом в S и концом в T . Следующие утверждения почти очевидны. Пусть S ⊂ N — некоторое подмножество вершин графа. Рассмотрим разбиение множества N на классы, одним из которых является множество S, а остальные классы суть одноэлементные множества, i / ∈ S. О факторграфе поэтому разбиению будем говорить, что он соответствует подграфу, порождённому множеством Графы матриц. Графом матрицы A = (a ij ) порядка n называется орграф с множеством вершин N = {1, . . . , n}, в котором → j ⇐⇒ a ij 6= Если каждой дуге ij графа матрицы приписать число a ij , то получится наглядное изображение матрицы в виде нагруженного графа. И наоборот, всякий нагруженный граф очевидным образом определяет матрицу. Пусть S ⊂ N. Символом A[S] обозначают главную подматрицу матрицы A, расположенную в строках и столбцах с номерами из S. С другой стороны, подмножество S определяет подграф графа матрицы. Между главными подматрицами A и подграфами графа A имеется очевидное взаимно однозначное соответствие. Матрица A называется неразложимой, если её граф неразложим (сильно связен. В противном случае говорят, что матрица A разло- жима. Весом пути i 1 i 2 . . . в графе матрицы A называется произведение весов дуг пути, то есть число a i 1 i 2 · · · a i k i k+1 . Ясно, что · · a l k−1 j 6= 0 ⇐⇒ в графе A есть путь il 1 l 2 . . . Согласно правилу умножения матриц (i, элемент матрицы определяется формулой, . . . ,l k−1 a il 1 a l 1 l 2 . . . где суммирование ведётся по всевозможным последовательностям индексов, Используя понятия графа матрицы и веса пути, можно сказать, что a (k) ij = сумма весов всех (i, путей длины k. (4) § 1. Графы и портреты матриц 9 Матрица A называется неотрицательной пишется A ≥ 0), если её элементы — вещественные неотрицательные числа. Матрица с положительными элементами называется положительной пишется. Сумма и произведение неотрицательных (положительных) матриц являются, понятно, неотрицательными (положительными) матрицами. Графы матриц особенно эффективны при изучении неотрицательных матриц. Если A = (a ij ) — неотрицательная матрица, тов графе A есть путь il 1 l 2 . . . Отсюда и из формулы (3) следует лемма, являющаяся основой применения графов в теории неотрицательных матриц: Лемма 3. Пусть A = (a ij ) — неотрицательная матрица. Тогда 0 ⇐⇒ в графе A существует (i, путь длины Если существует (i, путь при i 6= j, то по лемме 1 существует, путь длины k ≤ n − 1. Проверить неразложимость неотрицательной матрицы можно с помощью следующей теоремы. Теорема 1. Матрица A ≥ 0 порядка n ≥ 2 неразложима тогда и только тогда, когда + A) n−1 > Доказательство. Из лемм 1 и 3 следует, что из вершины достижима вершина j 6= i тогда и только тогда, когда a (k) ij > 0 для некоторого k ≤ n − 1. То есть тогда и только тогда, когда+ a (2) ij + . . . + a (n−1) ij > Для неразложимости A необходимо и достаточно, чтобы условие (выполнялось для любых неравных i и j. Нетрудно проверить, что это требование эквивалентно неравенству (5). Матрица A ≥ 0 называется примитивной, если существует показатель, при котором A k > 0. Граф называется примитивным, если из любой вершины в любую другую можно перейти путём некоторой длины k. В силу леммы 3 матрица примитивна в точности тогда, когда примитивен её граф. В частности, A k > 0 ⇐⇒ в графе A любая вершина достижима из любой другой вершины Комбинаторика матриц Нетрудно видеть, что в сильно связном графе любая вершина принадлежит некоторому простому контуру. Вершина называется ациклической, если она не принадлежит никакому контуру (в частности, вокруг неё нет петли. Ациклическую вершину можно эквивалентно определить как вершину, не взаимодостижимую ни с какой вершиной. Ясно, что все вершины являются ациклическими лишь тогда, когда в графе нет контуров. Вершина, из которой не выходят дуги, называется тупиковой. Напомним, что матрица A называется нильпотентной, если 0 для некоторого показателя Предложение 1. Матрица A ≥ 0 нильпотентна ⇔ в графе нет контуров. Д ока за тел ь ст во. Если в графе матрицы есть контур, то, очевидно есть и путь любой длины. Согласно лемме 3 тогда A k 6= для всех k. Значит, в графе нильпотентной матрицы нет контуров. Теперь предположим, что в графе A нет контуров. Тогда нет и путей длины n, поскольку любой путь длины n содержит контур. Снова обращаясь клемме, получаем A n = 0. Задача 1. Сильно связный граф, в каждую вершину которого входит ровно одна дуга, является простым контуром. Задача 2. Сильно связный граф, из каждой вершины которого выходит ровно одна дуга, является простым контуром. Задача 3. Пусть A — неотрицательная матрица. Докажите, что 0 ⇐⇒ вершина i принадлежит контуру длины k. При этом, если (матрица, то число равно количеству контуров длины, проходящих через вершину Задача 4. Если матрица неразложима, то у неё нет нулевых строки столбцов. Задача 5. Неотрицательная нильпотентная матрица непременно содержит нулевую строку и нулевой столбец. Задача 6. Если неотрицательная матрица A = (a ij ) порядка содержит меньше n ненулевых элементов, то A разложима. Почему? Задача 7. Пусть неразложимая матрица A ≥ 0 порядка n содержит ровно n ненулевых элементов. Какой у неё граф? Задача 8. Если матрица A неразложима, или примитивна, или нильпотентна, тотем же свойством обладает матрица A T § 1. Графы и портреты матриц 11 Задача 9. Пусть степень минимального многочлена матрицы равна m. Тогда в лемме 1 и теореме 1 можно заменить n на Задача 10. Матрица b c d ¶ ≥ 0 неразложима ⇔ bc > Задача 11. Неразложимая матрица b c d ¶ ≥ 0 примитивна a + d > Задача 12. В сильно связном графе с n ≥ 2 вершинами всякая вершина (и любая дуга) принадлежит простому контуру длины ≥ Задача 13. Матрица A ≥ 0 порядка n ≥ 2 неразложима ⇔ матрица E + A примитивна. Задача 14. Для любого n ≥ 2 существует нильпотентная матрица порядка n, такая, что A n−1 6= Задача 15. Факторграф сильно связного графа всегда сильно связен. Подобие матриц и изоморфизм графов. Говорят, что матрица перестановочно подобна матрице B, если A получается из B перестановкой строк, соединённой с такой же перестановкой столбцов. Результат преобразования записывается в виде A = UBU T , где матрица содержит в каждой строке и каждом столбце ровно одну единицу, а остальные элементы равны нулю. Матрица этого типа называется матрицей перестановки или переставляющей матрицей. Легко проверить, что переставляющие матрицы одного порядка образуют группу относительно умножения. При этом для матрицы перестановки U обратной матрицей является транспонированная матрица Существует взаимно однозначное соответствие между переставляющими матрицами и перестановками (биекциями) на множестве. А именно, переставляющей матрице U = (соответствует перестановка σ : N → N , такая, что) = j ⇐⇒ u ij = Два графа с множеством вершин N называются изоморфными, если существует такая перестановка σ на N, что → j в первом графе ⇐⇒ σ(i) → σ(j) во втором графе. (8) Отображение σ в этом случае называется изоморфизмом графов. С содержательной точки зрения изоморфные графы отличаются лишь Комбинаторика матриц нумерацией вершин. Условие изоморфизма (8) можно понимать так: если в первом графе заменить номер i вершины на номер σ(i), то получим второй граф. Пусть U — матрица перестановки σ. Прямыми вычислениями проверяется, что = |