Дискретно-непрерывная математика (стр. 52 )

где и Тогда в каждой строке матрицы есть хотя бы один ненулевой элемент — вследствие того, что вершины образуют в Г (А) цепь и, следовательно, в графе из каждой вершины Pi какая-то дуга ведет в какую-то вершину Рj (возможно, это верно при В каждой строке в тоже существует по меньшей мере один ненулевой элемент — потому что для каждой вершины не входящей в рассмотренную выше цепь, в Г(А) должен найтись ориентированный путь длины не более п—s (число вершин, не входящих в цикл), ведущий в какую-то вер­шину этой цепи. Понятно, что с помощью достаточного числа дополнительных обходов цикла в графе Г(А) от любой вер­шины, не входящей в цикл, можно провести ориентированный путь в какую-то вершину этого цикла, и он будет иметь длину, в точности равную

Теперь запишем в блочном виде:

где Так как в графе Г (А) вершины

образуют цикл, в графе в каждой вершине

есть петля. Поскольку А примитивна, тоже при­митивна и, значит, неразложима. Каждая из вершин графа соединена с любой другой вершиной этого графа путем длины не более п — 1. Всегда можно построить такой путь, имеющий длину, в точности равную п — 1, — за счет до­бавления достаточного числа обходов по петле в начальной вер­шине. Это показывает, чтои

Чтобы завершить доказательство, запишем !

Вследствие того что в каждой строке блоков и есть хотя бы один ненулевой элемент и каждый из блоков и положи­тельный, последняя блочная матрица является положительной, т. е.

Одно из следствий теоремы 22.5.8 — это резуль­тат Виландта, устанавливающий точную верхнюю оценку ин­декса примитивности для произвольной примитивной матрицы.

22.5.9. Следствие. Если матрица неотрицательна, то А примитивна тогда и только тогда, когда

Доказательство. Если какая-то степень матрицы А положи­тельна, то А примитивна; поэтому интерес представляет лишьо братное утверждение. При п = 1 результат тривиален, так что будем считать, что п > 1. Вследствие своей примитивности мат­рица А неразложима и в графе Г (А) есть циклы. Если самый короткий цикл в Г (A) имеет длину п, то длина любого другого цикла делится на п, и, следовательно, по теореме 22.5.3 матрица А не может быть примитивной. Таким образом, длина самого короткого цикла в Г(А) меньше или равна п — 1, и, значит, в силу теоремы 22.5.8

Виландт привел пример (см. задачу 4 в конце этого пара­графа), показывающий невозможность улучшения оценки

для класса матриц, в которых все диаго­нальные элементы нулевые. Как мы знаем, если все элементы главной диагонали положительны, то А примитивна тогда и только тогда, когда Следующий результат Холидея и Варги использует те же идеи, которые уже применялись в до­казательстве теоремы 22.5.8, и устанавливает верхнюю оценку индекса примитивности в тех случаях, когда некоторые, но, воз­можно, не все элементы главной диагонали являются положи­тельными.

22.5.10. Теорема. Пусть матрица неотрицательна и не­разложима, и предположим, что она имеет d положительных элементов главной диагонали, где Тогда и, значит,

Доказательство. Согласно условиям теоремы, матрица А должна быть примитивной (eсли бы А не была примитивной, то, согласно следствию 22.4.8, она имела бы нулевую главную диагональ), а в Г (A) минимальная длина цик­лов равна 1. В действительности имеется d таких циклов. Вы­полнив, если нужно, перестановки, можно считать, что P1, ... ..., Pd — это вершины графа Г(А), имеющие петли. Рассмотрим и запишем

где и. Те же доводы, которые уже

использовались по отношению к соответствующим блокам в и при доказательстве теоремы 22.5.8, теперь показывают, что каждая строка блоков Х11 и Х21 содержит хотя бы один ненулевой элемент, а блоки Y11 и Y12 положительные. По той же причине, которая уже отмечалась в теореме 22.5.8, произве­дение будет положительным.

Упражнение, Установить примитивность матрицы Каковы ее собственные значения? Вычислить оценки для устанавливаемые следствием 22.5.9 и теоремой 22.5.10. Каково точ­ное значение индекса

Сделаем заключительные замечания. Проверку заданной не­отрицательной матрицы на примитивность можно проводить, выясняя неразложимость этой матрицы и выполнение условия Виландта (лемма 22.5.9). Матрицы, возникающие на практике, часто имеют специальную структуру, позволяющую довольно просто узнать, будет ли соответствующий ориентированный граф сильно связным. Далее, если хотя бы один диагональный эле­мент положителен, то матрица непременно примитивна. Однако, если матрица большая и не обладает какой-либо спецификой или симметрией, а также если все ее диагональные элементы нулевые, то может оказаться необходимым для проверки нераз­ложимости или примитивности использовать именно лемму 22.4.1 или следствие 22.5.9. В обоих случаях требуемое число матричных умножений значительно сокращается, если интересующая нас матрица последовательно возводится в квадрат, до тех пор пока не будет получена степень, превышающая критическое значение, соответственно равное п — s или Например, при п — 10 для проверки неразложимости достаточно вычислить

т. е. нужно выполнить 4 матричных умножения вместо 8 в случае прямого применения леммы 22.4.1. Аналогично, если А неотрицательна, то для про­верки ее примитивности достаточно вычислить

т. е. нужно выполнить 7 матричных умножений вместо 81. Заметим, что в этих рассмотрениях мы неявно ис­пользовали задачу 3.