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

22.6. Общая предельная теорема

Для произвольно взятой неотрицательной и даже неразло­жимой матрицы А ее нормированные степени могут и не иметь никакого предела — это показывает с очевидностью пример матрицы

Тем не менее, в некотором вполне точном смысле в среднем этот предел существует.

22.6.1. Теорема. Пусть матрица неотрицательна и не­разложима и Тогда

Более того, для некоторой положительной постоянной С = С (А) для всех выполняется неравенство

Доказательство. Положими возьмем векторы у и х — соответственно левый и правый перроновы векторы матрицы А. Тогда условия (1)—(5) леммы 22.2.7 выполнены и, следова­тельно, матрица

будет обратима. Используя утверждение (е) леммы 22.2.7 и ра­венство из задачи 1 в конце этого параграфа, находим

В последнем выражении рассмотрим второе слагаемое. В его составе зависят от N только множитель и член

но в последней матрице все элементы равномерно ограничены при в силу следствия 22.1.33. Таким образом, второе слагаемое при имеет порядок и поэтому равномерно стремится к нулю.

Анализ предположений, используемых леммой 22.2.7 и след­ствием 22.1.33, показывает, что совершенно такие же аргументы приводят к более общему (но уступающему в краткости форму­лировки) результату.

22.6.2. Теорема. Пусть матрица неотрицательна, и пусть х и у — неотрицательные векторы, такие, что и Предположим, что выполнены следующие условия:

(c) матрица обратима;

(d) матрицаравномерно ограничена при

Тогда

Более того, для некоторой положительной постоянной С = С (А) при всех

22.7. Стохастические и двоякостохастические матрицы

Неотрицательная матрица в которой все строчные суммы равны +1, называется (строчной) стохастической ма­трицей — по той причине, что каждую строку можно рассматри­вать как распределение вероятностей на дискретном вероятностном пространстве из п событий. Столбцовая стохастическая матрица — это транспонированная к строчной стохастической матрице. Такие матрицы возникли естественным образом в мо­дели междугородней миграции населения, обсужденной в § 22.0. Стохастические матрицы возникают также при изучении цепей Маркова и в самых различных проблемах, связанных с модели­рованием в таких областях, как экономика и исследование опе­раций.

Множество стохастических матриц в Мп — это компактное выпуклое множество с одним простым, но важным свойством. Обозначим через вектор со всеми координатами, равными +1; тогда неотрицательная матрица будет стохастической в том и только в том случае, когда Таким бразом, стохастические матрицы образуют в Мп легко распо­знаваемое семейство матриц, имеющих некоторый общий поло­жительный собственный вектор. Неотрицательные матрицы с по­ложительным собственным вектором обладают многими спе­циальными свойствами (см. разд. 22.1.30, 22.1.31 и 22.1.33), кото­рые присущи всем стохастическим матрицам.

Стохастическая матрица для которой АТ тоже стохастическая, называется двоякостохастической; для нее все строчные и столбцовые суммы равны +1. Множество двоякосто-хастических матриц также, является компактным выпуклым мно­жеством в Мп, и неотрицательная матрица двоякостохастическая тогда и только тогда, когда и Один тип двоякостохастических матриц нам уже встре­чался в теореме 20.3.5 — это ортостохастическая матрица

отвечающая унитарной матрице

Строчные и столбцовые суммы для А равны +1 вследствие того факта, что строки и столбцы в U представляют векторы единич­ной евклидовой длины.

Другой пример двоякостохастических матриц — это множе­ство (группа) матриц перестановок. В действительности матри­цы перестановок являются фундаментальными прототипами двоякостохастических матриц — в силу теоремы Биркгофа лю­бая двоякостохастическая матрица есть выпуклая комбинация конечного числа матриц перестановок. Излагаемое ниже дока­зательство теоремы Биркгофа основывается на том факте, что всякая точка выпуклого компактного мно­жества S является выпуклой комбинацией его крайних точек. Мы покажем, что крайние точки множества двоякостохастиче­ских матриц — это не что иное, как матрицы перестановок.

22.7.1. Теорема (Биркгоф). Матрица является двояко-

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

и

Доказательство. Достаточность очевидна, поэтому требуется установить именно необходимость. Пусть задана двоякостоха-стическая матрица Если А — матрица перестановки, то в каждой ее строке и в каждом столбце в точности один элемент равен +1, а остальные элементы нулевые. Если бы можно было записать где

и В, С — двоякостохастические матрицы, то эле­менты в В и С, отвечающие нулю в А (т. е. элементу должны были бы удовлетворять соотношению откуда так как числа оба отличны от нуля, а неотрицательны. Поскольку матрицы В и С

двоякостохастические, их строчные суммы равны +1 и, следова­тельно, ненулевые элементы должны быть равны +1 и занимать те же позиции, что и ненули в А. Итак, А = В = С. Это дока­зывает, что любая матрица перестановки является крайней точ­кой множества двоякостохастических матриц.

С другой стороны, если А не является матрицей переста­новки, то по меньшей мере одна ее строка, скажем -я, содер­жит по меньшей мере два ненулевых элемента. В этой строке возьмем ненулевой элемент Должны выполняться неравенства так как в -й строке не меньше двух ненулевых элементов и сумма всех ее (неотрицательных) элементов равна +1. Поскольку и сумма всех (неотрицательных) элементов столбца с номером i2 равна +1, в этом же столбце должен найтись еще один ненулевой элемент для которого По той же причине в одной строке с элементом имеется другой ненулевой элемент и для него Пусть этот процесс продолжается, и последовательно выбираемые элементы как-то поме­чаются. Тогда после какого-то конечного числа шагов обяза­тельно возникнет ситуация, когда мы выберем элемент, который ранее уже выбирался. Последовательность элементов от первого до второго появления элемента (включаем первое, но не вто­рое появление) — это конечная упорядоченная последователь­ность элементов матрицы А, в которой любая пара соседних элементов находится попеременно то в одном столбце, то в од­ной строке; пусть обозначает наименьший (положитель­ный) элемент в этой последовательности. Построим матрицу в которой в позиции, соответствующей первому эле­менту рассмотренной последовательности, поставим +1, в по­зиции второго элемента поставим —1, в позиции третьего эле­мента— вновь +1 и т. д., с поочередным выбором ±1. Все остальные элементы в В положим равными нулю.