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

Обозначим через gi наибольший общий делитель для всех длин из Тогда матрица А примитивна в том и только в толь слу­чае, когда для всех

Доказательство. Заметим, что в силу неразложимости мат­рицы А ни одно из множеств не будет пустым; для каждого i и для всякогов Г (А) есть путь, соединяющий с так же как и путь, соединяющий с Если матрица прими­тивна, то по теореме 22.5.2 для некоторого имеем и, следовательно, для всех Но тогда для всех и поэтому для всех

Теперь предположим, что матрица не примитивна. Если А имеет ровно k > 1 собственных значений с максималь­ным модулем, то, согласно следствию 22.4.8, для всех и для всех т, не кратных k. Итак, и, следовательно, для всех

22.5.4. Замечание. Справедливо нечто большее по сравнению с тем, что утверждается в теореме 22.5.3; в действительности всегда и это общее значение величин gi в точности равно числу собственных значений матрицы А с макси­мальным модулем. Это теорема Романовского.

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

22.5.5. Лемма. Если матрица неотрицательна и не­разложима и все ее диагональные элементы положительны, то

Доказательство. Если и

то матрица В неотрицательна и неразложима (так как А не­разложима) и а стало быть,

но лемме 22.4.1.

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

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

22.5.6. Лемма. Пусть матрица неотрицательна и при­митивна. Тогда матрица неотрицательна, неразложима и примитивна для всех

Доказательство. Поскольку все достаточно большие степени матрицы А положительны, то же верно по отношению к Ak для любого k. Если матрица Ak разложима для какого-то k, то все степени матрицы Ak будут разложимыми, а значит, они не мо­гут быть положительными. Получаем противоречие с тем, что все достаточно большие степени матрицы А положительны. Зна­чит, никакая степень матрицы А не может быть разложимой.

Теорема 22.5.2 характеризует примитивность, но она — если ограничиться только тем, что в ней утверждается, —не может служить сколько-нибудь эффективным вычислительным тестом, потому что в ней не указывается никакой верхней оценки для степеней, требующих вычисления. Если найдено т, такое, что то А примитивна; однако когда следует остановиться, если положительная степень еще не получена? В следующей теореме устанавливается конечная оценка, отвечающая на этот вопрос.

22.5.7. Теорема. Пусть матрица неотрицательна. Если А примитивна, то для некоторого положительного целого

Доказательство. Вследствие неразложимости матрицы А су­ществует ориентированный путь, исходящий из вершины P1 в Г(А) и возвращающийся в вершину P1; пусть кратчайший та­кой путь имеет длину Следовательно, матрица в по­зиции (1,1) содержит положительный элемент, и он остается положительным для всех степеней матрицы Так как А при­митивна, должна быть неразложимой по лемме 22.5.6 и, значит, существует ориентированный путь, начинающийся в вер­шине Р2 графа и заканчивающийся также в вершине Р2; пусть кратчайший такой путь имеет длину Тогда в матрице будут положительными элементы в пози­циях (1,1) и (2,2). Этот процесс можно продолжить, просмат­ривая главную диагональ сверху вниз до тех пор, пока не бу­дет получена матрица которая является неразложимой и обладающей положительными диагональ­ными элементами. Поэтому в силу леммы 22.5.5 имеем и при этом

что и требовалось доказать.

Для любой заданной примитивной матрицы А наименьшее k, такое, что называется ее индексом примитивности и обычно обозначается через Мы уже знаем, что если А имеет положительную диагональ, и в общем случае. Последнюю оценку можно значи­тельно улучшить.

22.5.8. Теорема. Пусть —неотрицательная примитивная матрица, и предположим, что кратчайший простой ориенти­рованный цикл в имеет длину s. Тогда и, значит,

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

Запишем в блочном виде: