Альпин Ю А_Неотрицательные матрицы. Неотрицательные матрицы
 Скачать 0.57 Mb.
|
|
H = A (d) 11 . Путь в графе матрицы приводит из класса снова в в точности тогда, когда его длина кратна d. Поскольку граф сильно связен, то для любых i, j ∈ существует показатель ld, для которого a (ld) ij = h (l) ij > 0. Следовательно, матрица H = (h ij ) неразложима. Далее, по определению отношения совместимости для любых i, j ∈ найдутся пути одинаковой длины в общую вершину. Эти пути можно продолжить общим путём какой угодно длины, поэтому при достаточном большом l из любых, j ∈ синхронно достижима некоторая общая вершина p ∈ На языке матрицы H это значит h (l) ip > 0 и h (l) jp > 0, то есть любые две вершины i, j в графе матрицы H совместимы. Следовательно, по теореме 2 (с) матрица H = примитивна. ¤ Назовём контурным индексом сильно связного графа число, равное наибольшему общему делителю длин контуров графа. Под кон § 3. Форма Фробениуса импримитивной матрицы 21 турным индексом неразложимой матрицы будем понимать контурный индексе графа. Теорема 2. Индекс совместимости неразложимой матрицы равен её контурному индексу. Д ока за тел ь ст во. Длина любого контура делится на индекс совместимости d. При d = 1 это очевидно, а при d > 1 вытекает из циклического свойства разбиения на классы совместимости. При = 1 матрица A примитивна, а при d > 1 примитивна матрица A (d) 11 (см. доказательство теоремы 1). В любом случае при достаточно большом r имеем a (dr) 11 > 0 и a (d(r+1)) 11 > 0. Это значит, что через вершину 1 проходят контуры длины dr и d(r +1). Наибольший общий делитель этих чисел и, следовательно, множества длин всех контуров графа, равен d. Замечание 1. Вместо выражения "контурный индекс" применительно к неразложимой матрице и сильно связному графу часто употребляется термин "индекс импримитивности". Этот термин объясняется теоремой 1, согласно которой неразложимая матрица либо примитивна, либо приводится к виду (2), причем индекс импримитив- ности d можно считать мерой отклонения от примитивности (мерой импримитивности). Из теорем 2 си вытекает Следствие 1. Неразложимая матрица A ≥ 0 примитивна в точности тогда, когда контурный индекс A равен единице. Как строить форму Фробениуса. Пусть дана неразложимая матрица A и её граф. Нетрудно видеть, что длина всякого непростого контура равна сумме длин некоторых простых контуров. Поэтому контурный индекс сильно связного графа равен наибольшему общему делителю длин только простых контуров графа. Если их количество невелико, то контурный индекс легко вычисляется непосредственно по графу. Предположим, что контурный индекс d известен. Если d = 1, то, как доказано, матрица примитивна и уже имеет форму Фробениуса. Если d > 1, то выберем любую вершину, например, вершину 1, и зачислим её в класс C 1 . Вершины, в которые ведут дуги из вершины, зачислим в класс C 2 . В класс попадут вершины, в которые ведут дуги из вершин, включенных в класс C 2 . Итак далее. Вершины, в которые ведут дуги из вершин, зачисленных в класс C d , включим Комбинаторика матриц в и продолжим процесс. Процесс заканчивается, когда на некотором шаге в очередной класс нельзя зачислить новых вершин. Это значит, что все вершины распределились по классам совместимости. (Подумайте, почему это действительно так.) Затем перенумеруем вершины соответственно их разбиению на классы. Пусть Q = (q ij ) — переставляющая матрица, соответствующая перенумерации σ, то есть q ij = 1 ⇔ σ(i) = j. Тогда форма Фробениуса матрицы Задача 1. Любые две вершины сильно связного графа несовместимы в точности тогда, когда граф представляет собой простой контур. Задача 2. Предположим, что граф матрицы A представляет собой простой контур 1 → 2 → . . . → n → 1, дополненный дугой p → 1. Чему равен контурный индекс A? Опишите классы совместимости и форму Фробениуса матрицы A если) n = 6, и всех p, 1 ≤ p ≤ 5; 2) n = 12 и всех p, 1 ≤ p ≤ Задача 3. Пусть матрица A ≥ 0 порядка n содержит ровно ненулевых элементов. В каком случае она примитивна? Задача 4. Докажите, что контурный индекс симметричной матрицы равен 1 или Задача 5. Если импримитивная матрица порядка n с индексом импримитивности d невырожденна, тов форме Фробениуса этой матрицы все блоки — квадратные и одного порядка (то есть d делит n). Задача 6. Если в сильно связном графе есть "треугольник → k, k → j, i → то граф примитивен. Более общее утверждение если существуют два, пути длины m и n, то контурный индекс графа делит разность − Задача 7. Докажите, что контурный индекс неразложимой матрицы всегда не больше, чем её ранг. Задача 8. Пусть матрица A разбита на квадратные блоки = µ 0 P E 0 ¶ . Докажите, что) A неразложима в точности тогда, когда P неразложима; § 4. Экспонент примитивной матрицы 2) контурный индекс A равен удвоенному контурному индексу P Задача 9. Докажите, что все темпоральные подматрицы имеют один и тот же ненулевой спектр. Задача 10. Предположим, что некоторый подграф графа и соответствующий ему факторграф являются сильно связными графами. Докажите, что в этом случае граф сильно связен. Задача 11. Предположим, что некоторый подграф графа примитивен, а соответствующий ему факторграф сильно связен. Докажите, что в этом случае граф примитивен. Приведите матричную формулировку этого утверждения 4. Экспонент примитивной матрицы Если матрица A ≥ 0 полупримитивна, то по предложению 1 (с.15) фокусы графа A порождают примитивный подграф. Следовательно, граф содержит контуры, все вершины которых — фокусы. Пусть s длина самого короткого из таких контуров. Теорема 1. Если матрица A порядка n полупримитивна, то матрица содержит положительный столбец. Другими словами, в полупримитивном графе некоторый фокус достижим из любой вершины за (n − 2)s + 1 шагов. Д ока за тел ь ст во. Обозначим через V k (j) множество вершин, из которых можно попасть в вершину j путём длины k. Рассмотрим кратчайший контур θ фокусов и заметим, что для некоторой вершины j этого контура |V 1 (j)| ≥ 2. В противном случае оказалось бы, что все фокусы лежат на простом контуре θ, что противоречит примитивности подграфа фокусов. Имеют место вложения) ⊆ V 1+(k+1)s (j), k = 0, 1, 2, . . Действительно, если существует (i, путь длины 1 + ks, то, добавив к нему обход контура θ, получим (i, путь длины 1 + (k + 1)s. При некотором k наступит равенство) = Тогда V 1+ks (j) = N, то есть вершина j достижима из всех вершин путями длины 1 + ks. Предположим противное множество вершин, не принадлежащих V 1+ks (j), непусто. Равенство (2) тогда означает, что это множество вершин (собственное подмножество N) замкнуто в графе матрицы A s . Но это противоречит тому, что j — фокус. Для Комбинаторика матриц окончания доказательства осталось заметить, что строгих неравенств в цепочке ≤ |V 1 (j)| ≤ |V 1+s (j)| ≤ |V 1+2s (j)| . . может быть не больше, чем n − 2, то есть при k = n − 2 равенство) должно выполняться. Показатель степени в выражении (n − 2)s + 1 является возрастающей функцией от s. Причём максимальное значение параметра для полупримитивной матрицы равно n − 1 (почему не n?). Учитывая это, получаем следующую оценку, зависящую только от порядка матрицы. Следствие 1. Если матрица A порядка n полупримитивна, то матрица содержит положительный столбец. Докажем, что оценка следствия 1 (как функция от порядка матрицы точная, её нельзя уменьшить. Рассмотрим так называемую матрицу Виландта W = 0 1 0 . . . 0 0 0 1 . . . 0 · · · · · 0 0 0 . . . 1 1 1 0 . . . Граф матрицы W сильно связный и имеет два простых контура, длины и n − 1. Значит, контурный индекс графа равен 1 и матрица примитивна последствию нас. Докажем, что матрица содержит нуль в каждом столбце. Для этого достаточно доказать, что в графе W не существует пути длины 3n + 2 = (n − 1) 2 − (n − изв вершину 1, из вершины i в вершину i + 1 (i = 1, . . . , n − а также изв. Действительно, любой из таких путей имеет длину + 1 + (n − 1)y, где x, y — неотрицательные целые числа. Допустим, что nx + 1 + (n − 1)y = (n − 1) 2 − (n − 1). Последнее равенство равносильно равенству n(x + 1) + (n − 1)y = (n − 1) 2 . Тогда x + делится на n − 1, следовательно, nq + y = n − 1, но это невозможно. Если матрица A ≥ 0 примитивна, то наименьший показатель при котором A k > 0, называется экспонентом A. Из теоремы 1 легко выводится следующая оценка для экспонента: Теорема 2. Если матрица A ≥ 0 порядка n примитивна, то 0, (4) § 4. Экспонент примитивной матрицы 25 где s — длина самого короткого контура в графе матрицы A. Доказательство. Согласно теореме 1 существуют пути длины (n − 2)s + 1 из всех вершин в некоторую вершину j. Из этой вершины есть путь в любую другую вершину длины не большей, чем n − 1. Следовательно, каждая вершина графа достижима из всех вершин путями одной и той же длины, не большей, чем − 2)s + 1 + n − 1 = (n − 2)s + n. Следствие 2. Для любой примитивной матрицы A порядка n A n 2 −2n+2 > Докажем, что и эта оценка точная матрица содержит нуль в позиции (1,1), то есть в графе W не существует пути длины изв. Действительно, любой (путь имеет длину nx + (n − 1)y, где x > 0, y ≥ 0 — целые числа. Допустим, что nx + (n − 1)y = n 2 − 2n + 1. Тогда x = (n − 1)q, q ≥ и nq + y = n − 1, но это невозможно. Замечательно то, что матрица W — по существу единственная примитивная матрица порядка n с экспонентом n 2 − 2n + 2. Точнее, имеет место Теорема 3. Пусть A — примитивная матрица порядка n, экспонент которой равен n 2 − 2n + 2. Тогда графы матриц A и W изоморфны. Д ока за тел ь ст во. Есть три сильно связных неизоморфных графа с n вершинами и s = n − граф G матрицы W граф G 0 , получающийся из G добавлением дуги 1 → граф G 00 , получающийся из удалением дуги 1 → Граф исключим из рассмотрения как непримитивный: его контурный индекс равен n − 1. Остаются графы G и G 0 . Граф G содержит два простых контура 1 → 2 → · · · → n → 1, и C 2 : n → 2 → · · · → Граф G 0 , кроме и C 2 , имеет ещё контур 1 → 3 → · · · → n → Докажем, что в графе для любых вершин i, j существует (i, j)- путь длины n 2 − 2n + 1. Этим, очевидно, теорема будет доказана. При = j такой путь существует, поскольку каждая вершина i принадлежит контуру длины n − 1. В противном случае пусть m — длина Комбинаторика матриц кратчайшего (i, пути p. Тогда в качестве искомого (i, пути можно взять путь, проходящий n − m − 1 раз по контуру C 1 , затем по пути p, затем m−1 раз по любому из контуров или C 3 , на котором лежит вершина j. Задача 1. Любой фокус полупримитивного, ноне примитивного, графа с n вершинами достижим из любой вершины i путём длины 4n + Другими словами, если A — полупримитивная, ноне примитивная матрица, то столбцы матрицы A n 2 −4n+6 , отвечающие фокусам, поло- жительны. Решение. Пусть имеется l ≤ n − 1 фокусов. Они порождают примитивный подграф данного графа. Существует путь длины n − l изв какой-нибудь фокуса из него — путь длины l 2 − 2l + 2 в фокус. Соединяя эти пути, получим (i, путь длины n + l 2 − 3l + Учитывая лемму 1 (с, заменим параметр l на его максимально возможное значение l = n − 1 и получим оценку (5). Задача 2. Докажите, что экспонент симметричной неотрицательной примитивной матрицы порядка n не больше, чем 3n − Задача 3. Докажите, что для матрицы Виландта W имеет место равенство W n = E + W Задача 4. Рассмотрим матрицу = µ W E E где W имеет порядок n. Докажите, что A — примитивная матрица и вычислите её экспонент. Задача 5. Рассмотрим матрицу = 0 E 0 . . . 0 0 0 E . . . 0 · · · · · 0 0 0 . . . E W 0 0 . . . Докажите, что A — неразложимая матрица в форме Фробениуса. При каком наименьшем показателе k ненулевые блоки в матрице положительны. Нормальная форма разложимой матрицы 5. Нормальная форма разложимой матрицы Согласно лемме 2 (с) матрица A = (a ij ) порядка n ≥ 2 разложи- ма, если для некоторого множества вершин S ⊂ N графа матрицы ∈ S, j / ∈ S =⇒ a ij = Более известным определением разложимой матрицы является следующее матрица A порядка n ≥ 2 разложима, если существует такая матрица перестановки U, что где A 1 , A 2 — квадратные матрицы. Что касается матриц порядка один, то нулевая матрица по определению относится к разложимым, а ненулевая — к неразложимым матрицам. Это определение разложимости эквивалентно предыдущему. Действительно, если матрица приводится к виду (2), то её граф разложим, поскольку он изоморфен разложимому графу матрицы (2). Последний разложим, так как из вершин 1, . . . , k нельзя перейти в вершины порядок A 1 ). Наоборот, пусть граф разложим и i 1 , . . . , i k (k < n) — вершины, образующие замкнутое множество. Тогда, переставив с помощью подходящей матрицы U строки i 1 , . . . , а также столбцы с этими номерами, на первые позиции, получим матрицу формы (Теорема Если матрица A разложима, то она перестано- вочно подобна блочно треугольной матрице 0 . . . 0 A 21 A 2 . . . 0 ·· ·· ·· ·· A s1 A s2 . . . A s где каждый диагональный блок — неразложимая матрица или нулевая матрица первого порядка. Д ока за тел ь ст во. При n = 2 утверждение следует прямо из определения приводимости. Предположим, что оно верно для матриц порядка не выше n (n ≥ 2). Рассмотрим разложимую матрицу A порядка n + 1 и перестановочную матрицу U, такую, что матрица U −1 AU имеет форму (2). Для матриц и утверждение теоремы верно по предположению индукции. Если A 1 разложима, то положим, что U 1 — переставляющая матрица, преобразующая к Комбинаторика матриц виду, описанному в теореме. Если A 1 неразложима, то U 1 — единичная матрица. Аналогично определяется матрица U 2 . Теперь нетрудно проверить, что переставляющая матрица U = µ U 1 0 0 приводит матрицу A к желаемому виду. Матрица (3) называется нормальной формой разложимой неотрицательной матрицы. Из теоремы 1 вытекает следующая классификация вершин разложимого графа. Теорема 2. Множество вершин разложимого графа можно разбить на классы со следующими свойствами) каждый класс либо состоит из взаимодостижимых вершин, либо содержит единственную, ипритом ациклическую, вершину) существует нумерация классов, V 2 , . . . , такая, что если начало дуги лежит в V p , то её конец — в некотором классе V q , где p > q. Другими словами, если класс не замкнут, то из него возможно выйти лишь в класс с меньшим номером. Если перенумеровать вершины графа матрицы A так, чтобы первые номера получили вершины из V 1 , затем нумеровались вершины из итак далее, то после соответствующей перестановки рядов матрица получит форму (Конденсацией графа называется факторграф по описанному выше разбиению. Задача 1. Матрица A ≥ 0 нильпотентна ⇐⇒ в форме (3) матрицы все диагональные блоки — нулевые матрицы порядка 1. Сравните этот критерий нильпотентности с предложением 1 (с.10). Задача 2. Для матрицы A ≥ 0 форма (3) является треугольной матрицей ⇐⇒ в графе A нет простых контуров кроме, может быть, петель. Указание. Полезно вначале решить задачу 12 (с.11). Задача 3. Если в графе A нет простых контуров кроме, может быть, петель, то диагональные элементы матрицы A составляют её спектр. Задача 4. Докажите, что для симметричной матрицы в форме) все недиагональные блоки — нулевые. Другими словами, симметричная матрица является прямой суммой неразложимых (симметричных) матриц § 5. Нормальная форма разложимой матрицы 29 Задача 5. Конденсация не содержит контуров, кроме, может быть, петель Глава Теория Перрона – Фробениуса § 1. Теорема Перрона – Фробениуса Теорией Перрона – Фробениуса называют совокупность теорем о собственных значениях и собственных векторах неотрицательных матриц. Главный результат теории (первоначально доказанный Перроном для положительных матриц) состоит в том, что для неразложимой матрицы A ≥ 0 её спектральный радиус ρ(A) является положительным собственным значением, которому соответствует положительный собственный вектор. Ключевую роль в доказательстве этого факта играет следующая лемма, представляющая и самостоятельный интерес. Лемма 1. Пусть A ≥ 0 — неразложимая матрица порядка и ρ(A) = 1. Предположим, что для столбца y 0 выполняется неравенство Ay ≥ y. Тогда) Ay = y, 2) y > Доказательство. Предположим, что равенство 1) не выполняется, значит Ay − y 0. Поскольку (A + E) n−1 > 0 (теорема, сто+ Столбец z = (A + E) n−1 y положителен. Итак, имеем Az > z, z > Если число α > 0 достаточно мало, то и для матрицы B = (1 − верно неравенство Bz > z. Отсюда следует, что B k z > z для любого. Но этого не может быть, поскольку ρ(B) < 1 ⇒ B k → 0 при → ∞ теорема 1, с. Доказали, что Ay = y. Отсюда следует, что + E) n−1 y = В этом равенстве слева — положительный вектор, значит и y — положительный вектор. Теорема 1. Спектральный радиус ρ(A) неразложимой матрицы A ≥ 0 является её положительным собственным значением, которому соответствует положительный собственный вектор § 1. Теорема Перрона – Фробениуса 31 Д ока за тел ь ст во. Пусть Ax = λx, |λ| = ρ(A). Неразложимая матрица не нильпотентна, поэтому ρ(A) > 0. Без уменьшения общности можно считать ρ(A) = 1. Обозначим через |x| столбец, составленный из модулей элементов x. Имеют место соотношения = |x| = |Ax| ≤ По лемме 1 отсюда следует, что A|x| = |x|, |x| > 0. Итак, по теореме 1 любая неотрицательная неразложимая матрица имеет положительное собственное значение ρ, такое, что ρ ≥ для любого другого собственного значения λ. Число ρ(A) называют перроновым корнем матрицы Замечание 1. Из доказательства теоремы 1 видно, что собственный вектор, отвечающий собственному значению λ, |λ| = не может иметь нулевых компонент. Теорема 2. Если A ≥ 0 — неразложимая матрица, то размерность собственного подпространства, отвечающего собственному значению ρ(A), равна единице. Другими словами, любые собственные векторы x и y, отвечающих ρ(A), линейно зависимы. Д ока за тел ь ст во. По-прежнему будем считать, что ρ(A) = Пусть Ax = x и Ay = y для векторов x = (x i ) и y = (y i ). Согласно замечанию 1, x 1 6= 0, y 1 6= 0. Линейная комбинация z = x 1 y − удовлетворяет равенству Az = z, ноне может быть собственным вектором поскольку содержит нулевую компоненту (первую. Следовательно. Теорема 3. Спектральный радиус ρ(A) неразложимой матрицы A ≥ 0 является простым корнем характеристического многочлена матрицы Доказательство. Будем считать, что ρ(A) = 1 и пусть для вектора x > 0 выполняется Ax = x. Тогда A k x = x при любом показателе k. Отсюда нетрудно вывести, что для всех k ||A k || ≤ Теперь предположим, что кратность ρ(A) как корня характеристического многочлена A больше единицы. Приведём матрицу A к треугольному виду так, чтобы собственные значения, равные 1, занимали на главной диагонали первые позиции = B = 1 b 12 . . . b 1n 0 1 . . . b 2n · · · · · · 0 0 . . . b n−1,n 0 0 . . Заметим, что b 12 6= 0, иначе вышло бы, что первые два столбца матрицы D — линейно независимые собственные векторы, отвечающие. Но это противоречит теореме 2. Легко вычислить, что kb 12 . В силу этого ||B k || → ∞ при k → ∞. Но тогда и → ∞, что противоречит (1). Собственное значение матрицы называется доминирующим, если оно является простым корнем характеристического многочлена, превосходящим по модулю остальные корни. Теорема 4. Если матрица A ≥ 0 примитивна, то ρ(A) — доминирующий корень характеристического многочлена Доказательство. Пусть Ax = λx, |λ| = ρ(A). Докажем, что тогда λ = ρ(A). Этим, очевидно, теорема будет доказана. Будем считать, что ρ(A) = 1. Пусть A m > 0. Тогда A m x = λ m x. Из доказательства теоремы 1 видно, что |x| > 0 и |A m x| = A m |x|. В частности, равны первые элементы этих столбцов Модуль суммы ненулевых комплексных чисел равен сумме их модулей лишь если эти числа, как векторы на комплексной плоскости, лежат на одном луче. Применяя это соображение к равенству (заключаем, что числа x j /|x j | (j = 1, . . . , n) равны одному числу, которое мы обозначим через ε. Следовательно, x = ε|x|. Из доказательства теоремы 3 видно, что собственный вектор x = ε|x| соответствует собственному значению ρ(A). Значит, λ = ρ(A). Строка называется левым собственным вектором матрицы отвечающим собственному значению λ, если y T A = λy T . Собственные векторы-столбцы, чтобы отличить их от левых, называют правыми. Приведём "левый" вариант теоремы Следствие 1. Для любой неразложимой матрицы A ≥ 0 существует строка y T > 0, такая, что = ρ(A)y T . (4) § 2. Асимптотика степеней примитивной матрицы 33 Любые два левых собственных вектора, соответствующих отличаются лишь скалярным множителем. Действительно, если A неразложима, то неразложима и матрица. Характеристические многочлены матриц A и совпадают, значит. Для по теореме 1 существует вектор-столбец y > 0, такой, что A T y = ρ(A)y. Транспонируя обе части этого равенства, получим (4). Cвойство единственности, очевидно, сохраняется и для левых векторов. Теорема 5. Если для матрицы A ≥ 0 существует положительный собственный вектор, то он принадлежит собственному значению Доказательство. Пусть Ax = λx, x > 0. Умножим это равенство на левый собственный вектор y T > 0, отвечающий Получим = ρ(A)y T x = λy T x ⇒ ρ(A) = λ. ¤ § 2. Асимптотика степеней примитивной матрицы Рассмотрим последовательность степеней матрицы A ≥ 0 A, A 2 , . . . , A k , . . Как ведут себя элементы матрицы при k → ∞? Поведение при k → ∞ зависит от спектрального радиуса ρ. Например, согласно теореме 1 (c.55) A k → 0 ⇐⇒ ρ(A) < При ρ > 1 элементы по крайней мере, в некоторых позициях) при k → ∞ могут стать сколь угодно большими. В общем случае полезно привести матрицу к нормальной форме (3) (с. Ясно, что асимптотика последовательности в большой степени определяется поведением диагональных блоков A k t , но общая картина представляется довольно сложной. Пусть A ≥ 0 — неразложимая матрица. Назовём строку π > 0, πA = ρ(A)π, левым перроновым вектором, если сумма элементов равна 1. Столбец η > 0, Aη = ρ(A)η, назовём правым перроновым вектором, если πη = 1. Ясно, что левый и правый перроновы векторы определены однозначно. Теорема 1. Пусть A ≥ 0 — примитивная матрица и ρ(A) = Тогда ηπ. (2) Доказательство. Вещественные столбцы y со свойством = 0 образуют в пространстве подпространство размерности, инвариантное относительно матрицы A. Пусть t 2 , . . . , t n — базис этого подпространства. Тогда матрица T = (η, t 2 , . . . , t n ) невырожде- на, причём первая строка матрицы равна π. Нетрудно вычислить, что T −1 AT = µ 1 0 0 Поэтому T µ 1 0 0 Из теоремы 4 (с) следует, что ρ(A 1 ) < 1, а по теореме 1 (с 0. Отсюда легко следует (2). Замечание 1. Теорема 1 обратима если последовательность (неотрицательных матриц сходится к некоторой положительной матрице, то легко видеть, что матрица A примитивна и ρ(A) = В математической экономике матрицу A ≥ 0 называют устойчивой, если она неразложима и предел существует. Согласно теореме 1, если матрица A примитивна, то сходимость имеет место. Если же матрица A импримитивна, то она имеет нетривиальную форму Фробениуса и предела, очевидно, не существует. Итак, устойчивость неразложимой матрицы A ≥ 0 равносильна её примитивности. Задача 1. Если характеристический многочлен неразложимой матрицы A ≥ 0 порядка n равен λ n−1 (λ − 1), то A — примитивная матрица и lim k→∞ A k = Задача 2. Докажите, что для матрицы = 0 1 0 . . . 0 0 0 1 . . . 0 · · · · · 0 0 0 . . . 1 1/2 1/2 0 . . . порядка n существует предел и вычислите его § 3. Неравенства для перроновых корней 3. Неравенства для перроновых корней Вначале отметим очевидное Предложение 1. Если все строчные суммы матрицы A ≥ равны s, то ρ(A) = Теорема 1. Пусть A = (a ij ) — неразложимая неотрицательная матрица, s — минимальная, S — максимальная строчная сумма матрицы A. Если s < S, то < ρ(A) < Доказательство. Пусть y T = (y 1 , . . . , y n ) — левый перронов вектор для A, s i — сумма элементов й строки A. Символом обозначим столбец из единиц. Тогда = ρ(A) Отсюда и из определения левого перронова вектора легко следуют строгие неравенства (1). Докажем свойство монотонности перронова корня. Теорема 2. Пусть A и B — неотрицательные неразложимые матрицы. Если A ≤ B и A 6= B, то ρ(A) < Доказательство. Пусть x, y T — положительные векторы, такие, что Bx = ρ(B)x, y T A = ρ(A)y T . Тогда < y T (B−A)x = y T Bx−y T Ax = ρ(B)y T x−ρ(A)y T x ⇒ ρ(A) < ρ(B). Бывает полезным Предложение 2. Если для матрицы A ≥ 0 и вектора x > выполняется неравенство Ax ≤ x, то ρ(A) ≤ 1. Если же Ax < то ρ(A) < 1. Задача 1. Докажите, что утверждение, аналогичное теореме имеет место для столбцовых сумм матрицы Задача 2. Докажите, что теорема 2 останется верной, если неразложима лишь одна из матриц A, Задача 3. Теорему 2 можно вывести из теоремы 1. Докажите это 36 § 4. Спектр импримитивной неотрицательной матрицы Напомним, что под спектром комплексной, в частности, неотрицательной, матрицы понимают совокупность всех её собственных значений с учётом их кратностей. Граничным спектром будем называть совокупность собственных значений, имеющих максимальный модуль. Наконец, ненулевой спектр есть совокупность ненулевых собственных значений. В силу теоремы 4 (с) спектральный радиус — единственная точка граничного спектра примитивной матрицы. Используем это свойство для описания граничного спектра импримитивной матрицы. Пусть матрица A имеет контурный индекс d > 1 и находится в форме Фробениуса: A = 0 A 12 0 ... 0 0 0 A 23 ... 0 .. .. .. .. .. 0 0 0 0 A d−1,d A d1 0 0 Лемма 1. Если матрица A имеет блочную форму (1), то спектр A инвариантен относительно поворота на угол 2π d . Д ока за тел ь ст во. Пусть n 1 , ..., n d — порядки диагональных блоков в (1). Составим диагональную матрицу = diag(E n 1 , εE n 2 , . . . , где ε = cos 2π d + i sin 2π d . Непосредственно проверяется, что = Утверждение леммы следует из подобия матриц A и εA. Теорема 1. Граничный спектр неразложимой матрицы A ≥ с контурным индексом d и спектральным радиусом ρ состоит из чисел ρ, ρε, . . . , Доказательство. Если d = 1, то A — примитивная матрица (теорема 1, си наше утверждение вытекает из теоремы 4 (с.32). Теперь пусть d > 1. Достаточно ограничиться случаем ρ(A) = Согласно лемме 1 спектр A вместе с единицей содержит d − 1 точек, получающихся из неё поворотами на угол. То есть граничный спектр A содержит все корни из единицы степени d. Далее, в матрице § 4. Спектр импримитивной неотрицательной матрицы diag(G 1 , . . . , G d ) диагональные блоки примитивны. Это значит, что в спектр матрицы единица входит с кратностью d, а остальные собственные значения по модулю меньше единицы. Следовательно, в граничном спектре A нет собственных значений, помимо чисел (2). Замечание 1. По теореме 1 кратность каждой точки граничного спектра неразложимой матрицы A ≥ 0 равна единице, поэтому соответствующие им собственные подпространства одномерны. Согласно замечанию 1 (с) собственные векторы, отвечающие точкам граничного спектра, не содержат нулевых компонент. Модуль каждого из этих векторов принадлежат одномерному собственному подпространству, соответствующему Из теорем 4 си вытекает спектральный критерий прими- тивности: Следствие 1. Неразложимая матрица A ≥ 0 примитивна тогда и только тогда, когда ρ(A) — доминирующее собственное значение A. Задача 1. Что можно сказать о спектре матрицы (1), если её ранг равен Задача 2. Что можно сказать о спектре блочной матрицы (если все блоки имеют порядок Задача 3. Опишите неразложимые неотрицательные матрицы, спектр которых совпадает с множеством корней из единицы степени d. Задача 4. Что можно сказать о спектре матрицы (1), если её ранг равен 2d − Задача 5. Матрица A ≥ 0 неразложима ⇐⇒ матрица 2 (E + примитивна. Как связаны спектры этих матриц? Задача 6. Если для матрицы A ≥ 0 существует неотрицательный собственный вектор x ≥ 0, содержащий нулевые элементы, то A разложима, то есть граф A не является сильно связным. Докажите, не пользуясь теоремой 1 (с.30). Решение. Пусть S = {i|x i = 0} ⊂ N. Тогда ∈ S =⇒ n X j=1 a ij x j = n X j / ∈S a ij x j = 0 =⇒ a ij = 0 для всех j / ∈ то есть в графе A нет дуг, ведущих из вершин множества S в вершины, не принадлежащие S. 38 § 5. Случай разложимой матрицы Для разложимой матрицы A ≥ 0 имеет место ослабленный вариант теоремы 1 (с) Теорема 1. Для разложимой матрицы A ≥ 0 спектральный радиус ρ(A) является собственным значением. Существует неотрицательный собственный вектор (как левый, таки правый, отвечающий собственному значению Доказательство. Если A = 0, то доказывать нечего. Если A 6= 0, но матрица A нильпотентна, тов качестве собственного вектора, отвечающего ρ(A) = 0, можно взять ненулевой столбец матрицы A k 6= 0, для которой AA k = 0. Теперь пусть ρ(A) > Без уменьшения общности будем считать, что ρ(A) = 1. Применим индукцию по порядку матрицы. При n = 1 утверждение теоремы тривиально. Предположив, что оно верно для матриц порядка ≤ докажем его для матриц порядка n + 1. Пусть матрица имеет вид = µ B 0 C D ¶ . Тогда ρ(A) = max(ρ(B), ρ(D)). Будем искать неотрицательный собственный вектор для A в виде x = µ y z ¶ . Для него должны выполняться равенства 0 C D ¶ µ y z ¶ = µ By Cy + Возможны два случая. ρ(D) = 1 ≥ ρ(B). Вектор z 0, Dz = ρz, существует по предположению индукции. Удлинив его подходящим количеством нулей, получим собственный вектор x матрицы A. 2. ρ(B) = 1 > ρ(D). Вектор y 0, By = y существует по предположению индукции. Уравнение Cy + Dz = z имеет неотрицательное решение z = (E − D) −1 Cy см. лемму 3 нас. Тогда x искомый собственный вектор для Существование левого неотрицательного собственного вектора доказывается аналогично. Задача 1. Докажите существование левого неотрицательного собственного вектора для произвольной матрицы A ≥ 0. § 6. Критерий существования положительного собственного вектора 39 Задача 2. Для каких разложимых матриц A ≥ 0 существует положительный собственный вектор 6. Критерий существования положительного собственного вектора Существенной частью теории Перрона – Фробениуса является доказательство существования положительного собственного вектора для неразложимой неотрицательной матрицы. Теперь установим критерий существования положительного собственного вектора для разложимой матрицы. Для матрицы с нулевой строкой не может быть положительного правого вектора. Поэтому будем считать в этом параграфе, что матрица A не содержит нулевых строк. Это свойство эквивалентно отсутствию в графе A тупиковых вершин. Орграфы без тупиковых вершин, то есть такие, что из каждой вершины выходит хотя бы одна дуга, называются беступиковыми. Графы этого типа имеют особенности, которые следует отметить. Вершина i графа называется возвратной, если она достижима из любой вершины, достижимой из Предложение 1. В любом беступиковом графе есть возвратные вершины. Д ока за тел ь ст во. Назовём простой путь максимальным, если любое продолжение этого путине является простым. Нетрудно видеть, что конечная вершина простого максимального пути является возвратной вершиной. Предложение 2. Множество возвратных вершин замкнуто. Из предложений 1 и 2 вытекает Следствие 1. Пусть i — невозвратная вершина. Для любого ≥ n − 1 существует путь длины k изв множество возвратных вершин. Нетрудно проверить, что бинарное отношение достижимости, заданное на множестве возвратных вершин беступикового графа является отношением эквивалентности. Каждый класс достижимости порождает неразложимый замкнутый подграф. Этот подграф (и порождающий его класс) будем называть финальной компонентой графа. Из вышеприведённых результатов видно, что структура беступикового графа такова множество его возвратных вершин либо неразложимо, либо распадается на несколько несвязанных между собой неразложимых подмножеств — финальных компонент. Из невозвратных вершин (если таковые имеются) есть пути в финальные компоненты. Пусть граф матрицы A, содержит l финальных компонент и некоторое количество невозвратных вершин. Перенумеруем вершины так, чтобы первые номера получили вершины одной из финальных компонент, следующие номера — вершины другой финальной компоненты итак далее. Затем нумеруем невозвратные вершины. Переставляя строки и столбцы матрицы A соответственно новой нумерации, получим следующую нормальную форму разложимой матрицы без нулевых строк = A 1 A l C 1 . . . C l D Здесь A 1 , . . . , A l — неразложимые матрицы, они соответствуют финальным компонентам, блочная строка C 1 , . . . , C l задаёт переходы из невозвратных вершин в финальные компоненты, матрица D описывает переходы в классе невозвратных вершин. Теорема 1. Матрица A, заданная равенством (1), имеет положительный собственный вектор тогда и только тогда, когда) ρ(A 1 ) = . . . = ρ(A l ) = ρ(A), 2) ρ(D) < Без уменьшения общности будем считать, что ρ(A) = Вначале докажем теорему 1 для частного случая, когда в форме) нижняя блочная строка отсутствует. Лемма 1. Для неотрицательной матрицы = diag(A 1 , . . . , где A 1 , . . . , A l — неразложимые матрицы, положительный собственный вектор существует тогда и только тогда, когда) = ρ(A 1 ) = . . . = Доказательство. Пусть Ax = x, x > 0. Разобьём вектор на части так, что высота равна порядку A k . Тогда равенство = x разобьётся на равенства x k , k = 1, . . . , l. (3) § 6. Критерий существования положительного собственного вектора 41 Следовательно, ρ(A k ) = 1, k = 1, . . . , l. Наоборот, пусть спектральные радиусы матриц A 1 , ..., равны 1. Тогда согласно теореме с) для некоторых положительных векторов выполняются равенства. Из этих векторов и составляется искомый положительный собственный вектор для матрицы (2). Докажем ещё один вспомогательный результат. Положим = diag(A 1 , . . . , A l ), C = (C 1 , . . . , C l ) и запишем форму (1) в виде = µ B 0 C Последствию из любой невозвратной вершины существует путь длины n − 1 в возвратную вершину. Отсюда следует Лемма 2. В матрице 0 C n−1 D n−1 ¶ (5) подматрица не имеет нулевых строк. Д ока за тел ь ст во теоремы 1 в общей ситуации. Необходимость. Пусть Ax = x, x > 0. Разобъём столбец x на части y итак, чтобы равенство Ax = x разбилось на равенства By = y и + Dz = z. Из первого равенства видим, что y > 0 — собственный вектор для B. По лемме 1 имеем) = . . . = ρ(A l ) = Рассмотрим второе равенство, точнее, (легко заметить, тоже верное) равенство C n−1 y + D n−1 z = В матрице по лемме 2 нет нулевых строк, следовательно > 0 ⇒ D n−1 z < z ⇒ ρ(D n−1 ) < 1 ⇒ ρ(D) < Здесь использовано предложение 2 (с.35). Достаточность. По лемме 1 для матрицы B = diag(A 1 , . . . , A l ) существует вектор y > 0, By = y. Положим z = (E − D) −1 Cy. Прямым вычислением проверяется, что вектор x = µ y z ¶ — собственный для. Докажем, что z > 0. Поскольку вектор x собственный и для то + D n−1 z = z. Согласно лемме 5 в матрице все строки ненулевые, следовательно. Значит, z > 0, отсюда и x > 0. Теперь рассудим, в каком случае существует не только правый, но и левый положительный собственный вектор. Теорема 2. Матрица A имеет положительный правый и положительный левый собственные векторы в томи только том случае, когда A имеет нормальную форму Доказательство. Если условие теоремы выполнено, то правый и левый положительные векторы составляются из таковых векторов для диагональных блоков. Для доказательства обратного утверждения покажем, что в рассматриваемом случае нижняя блочная строка в форме (1) отсутствует. Предположим противное пусть строка (p, q) есть левый положительный собственный вектор матрицы, причём длина подстроки q равна порядку D. Тогда qD = где q > 0, чего не может быть поскольку ρ(D) < 1. ¤ Глава Элементы идемпотентной линейной алгебры Идемпотентной линейной алгебре и, вообще, идемпотентной математике, в последние десятилетия посвящено огромное число публикаций. Это объясняется, с одной стороны, её эстетической привлекательностью и прозрачностью базовых принципов, ас другой большим количеством приложений. Здесь укажем лишь на книги, [12], в которых можно найти дальнейшие ссылки по этой теме. В этой главе рассматривается лишь проблема собственных векторов и собственных значений в идемпотентной линейной алгебре. Интересно отметить сходство излагаемых результатов с теорией Перрона– Фробениуса ив тоже время, существенные отличия от неё. Два следующих параграфа не содержат идемпотентной математики и принадлежат традиционной теории неотрицательных матриц. Однако доказанные в них теоремы играют в заключительном параграфе решающую роль в решении основной задачи этой главы 1. Неотрицательные матрицы характеристики Напомним, что вес пути p = i 1 . . . в графе матрицы A = (a ij ) ≥ 0 равен w(p) = a i 1 i 2 · · · a i k i k+1 . Средним весом пути p = i 1 . . . i k i k+1 назовём среднее геометрическое весов дуг) = (a i 1 i 2 · · · Контурной характеристикой σ(A) матрицы A и её графа называется наибольший из средних весов простых контуров (прилагательное "контурной" иногда будем опускать. Контур, средний вес которого равен характеристике, называется экстремальным. Вершины и дуги, принадлежащие экстремальным контурам, называются экстремальными. Подграф, порождённый экстремальными дугами, называется экстремальным. Поскольку w(p) ≤ 1 ⇔ e w(p) ≤ 1, причём w(p) = 1 ⇔ e w(p) = то граф характеристики 1 — это графу которого максимальный вес контура равен единице. Поэтому, занимаясь случаем σ(A) = 1, будем говорить просто о весах путей Лемма 1. Пусть σ(A) = 1. Если вершина j достижима из вершины i, то существует (i, путь максимального веса и его можно найти среди простых (i, j)-путей. Д ока за тел ь ст во. Если (i, путь w непростой, то представим его в виде w = pqr, где q — простой контур. Удалив его из пути p, получим (i, путь pr, вес которого не больше веса p. Продолжая подобные удаления, придём к простому (i, пути, вес которого не больше веса p. Доказали, что вес непростого (i, путине больше веса некоторого простого (i, пути. Отсюда и следует утверждение леммы. Следствие 1. В графе характеристики 1 наибольший из весов всевозможных (не только простых) контуров равен единице. Матрица называется унистрочной, если максимальный элемент каждой её строки равен 1. Вес любого пути в графе унистрочной матрицы не больше 1. Отправляясь из любой вершины, можно строить сколь угодно длинный путь веса 1. Если длина такого пути ≥ n, то он содержит контур веса 1. Отсюда следует Лемма 2. Если A — унистрочная матрица, то σ(A) = Будем говорить, что матрица A = (a ij ) диагонально подобна матрице) порядка n, если существует обратимая диагональная матрица D = diag(d 1 , . . . , d n ), такая, что D −1 AD = B, то есть для любых i, Матрица типа D = diag(d 1 , . . . , d n ), d 1 > 0, . . . , d n > 0, называется положительной диагональной матрицей. Отметим два простых свойства диагонального подобия Предложение 1. Бинарное отношение диагонального подобия является отношением эквивалентности. Предложение 2. Если матрицы A и B диагонально подобны то 1) графы A и B совпадают) если в графе A есть контуры, то веси вес любого контура i 1 i 2 . . . равны. . . a i k i 1 = b i 1 i 2 b i 2 i 3 . . . b i k i 1 . Отношение диагонального подобия разбивает множество матриц на классы диагонально подобных матриц. Естественно попытаться найти в каждом классе наиболее простого представителя § 1. Неотрицательные матрицы характеристики Теорема 1. Для неразложимой матрицы A ≥ 0 следующие свойства эквивалентны) σ(A) = 1; 2) существуют такие положительные числа d 1 , . . . , d n , что d i , i = 1, . . . , n; (3) 3) матрица A ≥ 0 диагонально подобна унистрочной матрице. Д ока за тел ь ст во. Пусть j 0 — какая-нибудь из экстремальных вершин. Обозначим через наибольший из весов, путей. При любом i = 1, . . . , n имеет место неравенство max 1≤j≤n a ij d j ≤ поскольку произведение при любом j является весом некоторого, пути (или равно 0 при a ij = 0). Докажем, что на самом деле это нестрогое неравенство является равенством. Существует путь . . . веса d i . Тогда путь lm . . . имеет максимальный вес в противном случае его можно было бы заменить (l, j 0 )-путём большего веса. Это значит, что max 1≤j≤n a ij d j = На первый взгляд, в приведённом рассуждении не учтено, что путь веса может быть длины 1, то есть быть просто дугой ij 0 . Но если так, то максимальный вес имеет и путь ij 0 m . . . j 0 , где j 0 m . . . j 0 — контур максимально возможного веса 1. Значит, ив этом случае равенство (3) остаётся верным ⇒ 3. Пусть D = diag(d 1 , . . . , d n ) и рассмотрим матрицу A = D −1 AD c элементами ¯a ij = d −1 i a ij d j . Из равенств (3) следует, что max 1≤j≤n ¯a ij = max 1≤j≤n d −1 i a ij d j = 1, i = 1, . . . , Значит, A — унистрочная матрица ⇒ 1 вытекает из леммы 2 итого, что диагонально подобные матрицы имеют один и тот же граф с одинаковыми весами контуров. Следствие 2. Контурная характеристика неразложимой матрицы равна 1 тогда и только тогда, когда она диагонально подобна унистрочной матрице. ¤ 46 § 2. Матрицы произвольной характеристики. Согласно предложению 2 (су диагонально подобных матриц и B один и тот же граф, причём веси вес любого контура равны. Следовательно, σ(A) = В следующей лемме описывается, как изменяются свойства матрицы приумножении её на положительное число Лемма 1. Пусть r — положительное число, A — неотрицательная матрица. Тогда) графы матриц A и rA совпадают) при переходе от A к rA средний вес пути i 1 i 2 . . . умножается на r: e w rA (i 1 i 2 . . . i k i k+1 ) = r e w A (i 1 i 2 . . . i k i k+1 ); 3) σ(rA) = rσ(A); 4) одни и те же контуры являются экстремальными для A и Доказательство. Первое утверждение леммы очевидно. Доказательство второго утверждения немедленно следует из определения среднего веса пути. Третье и четвёртое утверждения вытекают из второго. Обозначим через max(A) максимальный элемент матрицы A ≥ Матрицу A назовём уравновешенной, если число max(A) присутствует в каждой строке Согласно лемме 1, если поделить матрицу A на её характеристику, то получим матрицу σ −1 A характеристики 1 стем же графом и теми же экстремальными контурами, что у матрицы Теорема 1. Любая неразложимая матрица A ≥ 0 диагонально подобна уравновешенной матрице. Д ока за тел ь ст во. Пусть σ — характеристика A и для матрицы характеристики 1 вычислены числа d 1 , . . . , из теоремы (с. Согласно п. 2) этой теоремы max 1≤j≤n (σ −1 a ij )d j = d i ⇒ max 1≤j≤n d −1 i a ij d j = σ (i = 1, . . . , Это значит, что при D = diag(d 1 , . . . , d n ) матрица D −1 AD уравновешенная. ¤ § 3. Элементы идемпотентной линейной алгебры 47 Лемма 2. Для любой неотрицательной матрицы A справедливо неравенство) ≤ Если A — уравновешенная матрица, то) = max(A). Из теоремы 1 следует, что функция max(A) в классе диагонально подобных матриц достигает минимума на уравновешенных матрицах и этот минимум равен контурной характеристике σ(A). Точнее, имеет место Теорема 2. Для неразложимой неотрицательной матрицы A σ(A) = где G пробегает множество положительных диагональных мат- риц. Д ока за тел ь ст во. Для любой положительной диагональной матрицы G σ(A) = σ(G −1 AG) ≤ Эти соотношения следуют из того, что преобразование диагонального подобия не изменяет характеристики матрицы, и из леммы 2. С другой стороны, согласно теореме 1 существует положительная диагональная матрица D ≥ 0, такая, что D −1 AD — уравновешенная матрица. Следовательно, снова по лемме 2, σ(A) = откуда и следует утверждение теоремы. ¤ Приведём ещё один вариант теоремы Теорема 3. Неразложимая неотрицательная матрица A представима в виде = где D — положительная диагональная матрица, A — унистрочная матрица, σ — характеристика матрицы A. § 3. Элементы идемпотентной линейной алгебры Непустое множество S, на котором введены бинарные операции сложения ⊕ и умножения ⊗, называется полукольцом, если 48 1) hS, ⊕i — коммутативная полугруппа с нейтральным элементом 0; 2) hS, ⊗i — полугруппа с нейтральным элементом 1; 3) выполняются законы дистрибутивности для любых a, b, c ∈ S a ⊗ (b ⊕ c) = a ⊗ b ⊕ a × c, (b ⊕ c) ⊗ a = b ⊗ a ⊕ c ⊗ a; 4) a ⊗ 0 = 0 ⊗ a = 0 для любого a ∈ Полукольцо называется коммутативным, если умножение в нём коммутативно. Коммутативное кольцо называется полуполем, если ненулевые элементы относительно умножения образуют группу. Ясно, что каждое кольцо есть полукольцо, каждое поле — полуполе. Множество S 0 ⊆ S называется подполукольцом полукольца S, если оно содержит нуль и единицу полукольца и замкнуто относительно относительно операций сложения и умножения (то есть, вместе с любыми элементами из содержит их сумму и произведение. Под- полукольцо, разумеется, само является полукольцом. Матрицы с элементами из полукольца (матрицы над полукольцом) складывают и перемножают по обычным правилам. При этом остаются справедливыми свойства, относящиеся к сложению и умножению матрица также к умножению матриц на элементы полукольца. Сохраняются и доказательства этих свойств. Множество M n (S) всевозможных матриц порядка n над полукольцом образует полукольцо, в котором нулевая матрица 0 и единичная матрица E определяются очевидным образом. Они служат, соответственно, нулём и единицей полукольца M n (S). Полукольцо) при n ≥ 2 всегда некоммутативно. Интересный класс полуколец составляют идемпотентные полукольца, в которых a ⊕ a = a для любого элемента a. Идемпотентным является, например, полукольцо B с элементами 0 и 1, операции в котором отличаются от обычных "школьных" лишь тем, что 1 ⊕ 1 = Множество столбцов высоты n над S с операциями сложения и умножения (слева) на элементы из S образует аналог линейного пространства. Элементы будем называть векторами. Матрица ∈ M n (S) определяет оператор на по правилу 7→ A ⊗ с очевидными свойствами линейности. Вектор x 6= 0 называется собственным вектором, а элемент λ ∈ S — соответствующим ему собственным значением оператора A, если ⊗ x = λ ⊗ x. § 3. Элементы идемпотентной линейной алгебры 49 Основным для нашей темы примером полукольца является множество вещественных неотрицательных чисел с обычным умножением, нов роли сложения выступает идемпотентная операция взятия максимума. Нетрудно проверить, что эта алгебраическая система, обозначим её R, действительно является полукольцом и даже полу- полем. Символ "+" в этом параграфе закрепим за операцией взятия максимума a + b = max(a, b). Этот же символ обозначает сложение матриц над R. Знак умножения обычно будем опускать. В задаче о собственных значениях и собственных векторах для матриц над R имеется любопытная аналогия с теорией Перрона– Фробениуса. Теорема 1. Для любой неразложимой матрицы A ∈ число σ(A) является собственным значением, которому соответствует положительный собственный вектор. Д ока за тел ь ст во. Согласно теореме 3 (с) матрицу можно представить в виде = где D — положительная диагональная матрица, A — унистрочная матрица, σ — характеристика матрицы A. Умножив равенство (1) на столбец d = D1, получим Ad = σd. Теорема 2. Если x = (x j ) — положительный собственный вектор для матрицы A ∈ M n (R), то Ax = σ(A)x. Другими словами, характеристика матрицы — единственное собственное значение, отвечающее положительному собственному вектору. Д ока за тел ь ст во. Положим = diag(x 1 , . . . , x n ), тогда из предыдущего равенства следует = X1 ⇒ X −1 (λ −1 A)X1 = Последнее равенство означает, что матрица X −1 (λ −1 A)X — уни- строчная и её характеристика равна 1. Значит, и σ(λ −1 A) = 1, а поскольку, то σ(A) = λ. Теорема 3. Пусть матрица A ∈ M n (R) неразложима и) = 1. Тогда столбец матрицы (E + A) n−1 , отвечающий экстремальной вершине j, неподвижен относительно Указание. При доказательстве нужно учесть, что длина незамкнутого простого путине больше, чем n − 1, поэтому недиагональные элементы матриц + A 2 + . . . + A n = A(E + и (E + A) n−1 совпадают. Диагональные же элементы в позиции (j, j) равны (т.е. оба равны 1) в точности тогда, когда вершина j экстремальна. Задача 1. Докажите, что σ(A) = 1 ⇔ tr(A + . . . + A n ) = 1. (A неразложима.) Задача 2. Найдите контурную характеристику и отвечающие ей собственные векторы матрицы 0 a −1 0 b 0 0 b −1 0 c 0 0 c −1 Как обобщить эту задачу и её решение? Задача 3. Если A неразложима и A 2 = A, то σ(A) = Задача 4. Докажите, что единственным собственным значением нильпотентной матрицы является 0. Как вычислить (хотя бы один) |