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

Для каждой п × п-матрицы положим

Ясно, чтообладает обычными свойствами нормы.

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

Доказательство. Пусть— i-я строка матрицы А и bi — i-й элемент вектор-столбца Am. Тогда

Следствие 22.8.2. Если А — стохастическая п×п-матрица и H—произвольная действительная п × п-матрица, то

|AH-H|≤||Н||.

Будем говорить, что п × п-матрица В принадлежит классу матриц W, если сумма элементов этой матрицы по строкам рав­на нулю, а сумма всех положительных элементов в каждой стро­ке пе больше единицы.

Лемма 22.8.5. Пусть А — произвольная действительная п×п-матрица, а В — п×п-матрица из класса W. Тогда справедливо неравенство |ВА| ≤||Н||.

Доказательство. Обозначим элементы матрицы ВА через Пусть Согласно определению произведения двух матриц имеем

(22.8.3)

ПоложимРассмотрим два случая.

Заменив в (22.8.3) в слагаемых с положительными коэффициентами сомножители на М и в слагаемых с непо-ложительными коэффициентами bkj те же сомножители на т, получаем неравенство

Отсюда в силу того, что матрица В является матрицей из класса W, имеем Так как то в этом случае

2) Пусть теперьПредставим выражение (22.8.3) в виде четырех групп слагаемых

где элементы — положительные (причем

коэффициенты — положительные, а коэффициенты

— отрицательные), а элементы — неположительные (причем коэффициенты — положительные, а коэффициенты — не-

положительные). Имеет место неравенство

Так как то согласно определению матриц из класса W получимО

Следствие 22.8.3. Если С и D — стохастические матрицы одинаковых порядков, такие, что произведения СА и DA, где А — произвольная матрица, определены, то

Доказательство. Матрица С — D является матрицей из класса W, а поэтому к произведению (C — D)A применима лем­ма 22.8.4.

Определение 22.8.1. Для всякой стохастической п×п-матрицы через обозначим матрицу из нулей и единиц, удовлетворяющую условиям

Матрица Q(A) называется булевским шаблоном стохастической матрицы А.

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

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

следует

Лемма 22.8.6. Соответствие является гомоморфизмом полугруппы G стохастических п×п-матрщ на полугруп­пу Q(G) булевских стохастических п×п-матриц-шаблонов.

Доказательство. Действительно, пусть элемент произведения С стохастических матриц и строго больше нуля:

Тогда это означает, что найдется значение индекса j такое, что а0 > 0 и Но в этом случае в соответствующих матрицах-шаблонах Q(A) и Q(B) имеем, чтои Но тогда элемент матрицы-шаблона для произведения Q(AB) будет равен единице:

Обратно, если элемент произведения АВ равен нулю, то, посколь­ку матрицы А и В имеют только неотрицательные элементы, то равенство

возможно лишь в том случае, когда все элементы и

(j= 1, . .., п) матриц А и В равны нулю. Однако в этом случае будет равен нулю и элемент матрицы-шаблона Q(AB):

Таким образом, мы получили тождество для любой пары матриц А и В из полугруппы G, что и означает наличие гомоморфизма.

Стохастическая матрица называется регулярной, если некоторая

ее конечная положительная степень состоит только из положительных элементов. Естественно называть регулярным и булевский шаблон регулярной матрицы. Свойство матрицы А быть регулярной инвариантно относительно отображения Q: Таким образом, булевская матрица регулярна, если некоторая ее конечная положительная степень состоит только из одних единиц.

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

Теорема 22.8.1. Пусть —конечная система

стохастических п×п-матриц. Следующие четыре условия эквивалентны.

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

III. Существует натуральное l2 такое, что для любой матрицы для выполняется соотношение