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

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

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

Поскольку в Мп имеется ровно п! различных матриц пере­становок, в силу теоремы Биркгофа любая двоякостохастическая матрица может быть выражена выпуклой комбинацией са­мое большеематриц перестановок. Более глубокий ана­лиз показывает, что этих матриц не потребуется больше, чем

22.8. Свойства семейств стохастических матриц

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

Пусть -матрица. Рассмотрим линейное преобразование линейного пространства на себя, описываемое соотно­шением

(22.8.1)

Лемма 22.8.1. Для того чтобы линейное преобразование (22.8.1) в k-мерном векторном пространстве Ek отображало в себя координатный симплекс

необходимо и достаточно, чтобы матрица А была стохастическая. Доказательство. Действительно, симплекс есть множество всех стохастических векторов с k координатами. Если А — стохастическая матрица, то она переводит стохастический вектор в стохастический. Обратно, если матрицу А записать в виде

то каждая вершина симплекса

переводится преобразованием (22.8.1) в векторы

следовательно,— стохастические векторы и A —

стохастическая матрица.

Исследуем отображение из леммы 22.8.1 более детально.

Замечание 22.8.1. Матрица преобразует вершины координатного симплексаи стохастические вектор-строки , где есть i-я строка s-й степени матрицы А.

Замечание 22.8.2. Пусть произвольная точка u гиперплос­кости, определяемой симплексом представлена в виде линейной комбинации вершин координатного симплекса в виде

Тогда образ точки u в отображении представляется

в виде

Обозначим через образ симплексав отображении А'(х). Аналогично, обозначим через образ симплекса в отображении, определяемом матрицей где и

Замечание 22.8.3. Симплекс является образом

симплекса в отображении, определяемом матрицей для любых слов р2 из свободной полугруппы X*.

На рис. 1 изображена картина преобразования симплекса ∆(3) для матриц А и А2.

Рис.1.

Введем в рассмотрение метрику в пространстве условием

(22.8.2)

Лемма 22.8.2. Если А — стохастическая k × k-матрица в мет­рическом пространстве E{k) с метрикой (22.8.2), то для любой пары векторов верно неравенство

Д о к а з а т е л ь с т в о. Имеем

Из доказательства леммы 22.8.2 видно, что она справедлива не только для стохастических матриц, но для любой матрицы, суммы элементов строк которой не превосходят единицы.

Пусть m — поствектор. Положим, по определению,

где максимум и минимум берутся по всем координатам поствек­тора. Заметим, чтоявляется полу­нормой, т. е. удовлетворяет всем свой­ствам нормы, но из не следует равенство нулю m.

Распространим это определение на матрицы. Если — некоторая матрица, то положим

Лемма 22.8.3. Если — стохастическая п×п-матрица, и m — поствектор, то

Доказательство. Пусть Без ограничения общности можно положить Тогда имеем

Аналогично, подставляя в суммудля b2 число m2 вместо т1, получаем

Таким образом, Но

и так как то 1—а12 — a21 ≤1-2δ.

Следствие 22.8.1. Если — система сто­хастических матриц, все элементы которых больше то для любых слов

Доказательство. Вектор-столбцы матриц А(х) удовлетворяют условию По лемме 22.8.2 столбцы произведения матриц А(х)А(у) удовлет­воряют условию Проводя индукцию по длине слова р, получаем требуемый результат.