КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
імені ТАРАСА ШЕВЧЕНКА
Вотякова Леся Андріївна
УДК 512.53
НАПІВГРУПИ НАПІВСТОХАСТИЧНИХ МАТРИЦЬ
ТА ЇХ ЗАСТОСУВАННЯ
01.01.06 – алгебра і теорія чисел
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ – 2004
Дисертацією є рукопис.
Роботу виконано у Національному педагогічному університеті імені М.П.Драгоманова, Міністерство освіти і науки України.
Науковий керівник: доктор фізико-математичних наук, професор ПРАЦЬОВИТИЙ Микола Вікторович, Національний педагогічний університет імені М.П.Драгоманова, завідувач кафедри вищої математики, м.Київ.
Офіційні опоненти: доктор фізико-математичних наук НОВІКОВ Борис Володимирович, Харківський національний університет імені В.Н.Каразіна, м.Харків;
доктор фізико-математичних наук, професор УСЕНКО Віталій Михайлович, Луганський національний педагогічний університет імені Тараса Шевченка, м.Луганськ;
Провідна установа: Львівський національний університет імені Івана Франка, кафедра алгебри, Міністерство освіти і науки України.
Захист відбудеться “27” грудня 2004 року о 14 годині на засіданні спеціалізованої вченої ради Д 26.001.18 при Київському національному університеті імені Тараса Шевченка за адресою:
03027, м.Київ, проспект акад. Глушкова, 6, Київський національний університет імені Тараса Шевченка, механіко-математичний факультет.
З дисертацією можна ознайомитися у бібліотеці Київського національного університету імені Тараса Шевченка (вул. Володимирська, 58).
Автореферат розіслано “22”листопада 2004 року
Вчений секретар
спеціалізованої вченої ради Плахотник В.В.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми дослідження. Ще на початку XX ст. російський математик Марков А.А. в серії робіт (1907-1912р.р.) започаткував вивчення ймовірносних моделей (відомих тепер під назвою “ланцюги Маркова”), породжуючим елементом яких є стохастична матриця, тобто квадратна матриця з невід’ємними елементами, сума яких у кожному рядку дорівнює одиниці.
Стохастичні матриці та їх узагальнення (матриці з невід’ємними елементами) вивчалися як безпосередньо, наприклад, проблема власних значень в роботах Динкіна Є., Дмітрієва Н., Карпалєвича Ф., так і опосередковано, тобто як породжуючий елемент ланцюга Маркова.
Сформувався певний блок класичних результатів з теорії таких матриць, який увійшов в найбільш відомі енциклопедичні монографії Гантмахера Ф., Беллмана Р., Хорна Р. і Джонсона Ч. Щодо ланцюгів Маркова, то вже майже століття вони залишаються у полі зору провідних дослідників (у першу чергу імовірносників) і служать джерелом нових результатів. Зрозуміло, що постановка нових задач, урізноманітнення методів дослідження у теорії марковських ланцюгів приносили нову інформацію про стохастичні матриці. Так, для прикладу, алгебраїчні методи у поєднанні з імовірносними дозволили (Феллер В., Чжун Кай Лай, Кемені Д., Снелл Д., Карлін С.) класифікувати такі матриці за структурою, з’ясувати роль їх власних чисел і власних векторів.
Однак ймовірносний зміст, який пов’язувався із стохастичною матрицею, визначав і мету дослідження, і його методи. Глобальні властивості множини стохастичних матриць порядку n залишились в тіні, хоча відносно звичайної операції множення вона є напівгрупою з одиницею (моноїдом).
Знявши вимогу невід’ємності елементів матриці і залишивши вимогу рівності одиниці суми елементів кожного рядка (звідси термін “напівстохастична матриця”), ми отримаємо напівгрупу значно “багатшу” за своїми алгебраїчними властивостями і з новими можливостями щодо застосування. Якраз множина напівстохастичних матриць з елементами з поля і є об’єктом дослідження у дисертації. Більше того, якщо послабити ще й вимогу напівстохастичності, а вимагати рівності сум елементів кожного рядка між собою, то така множина замкнена і відносно додавання, і тому є алгеброю, яка служить поданням нових класів алгебр скінченного рангу.
Зв’язок роботи з науковими програмами, планами, темами. Тематика дисертаційної роботи відповідає планам науково-дослідних робіт кафедри математики Вінницького державного педагогічного університету ім. Михайла Коцюбинського. Робота виконана в рамках теми “Дослідження багатомісних функцій та відношень алгебраїчними методами” (номер державної реєстрації 0100U005526).
Мета і завдання дослідження. Метою дослідження є розробка основ теорії напівстохастичних матриць та застосування розроблених методів до вивчення функціоналів, визначених на графах, породжених такими матрицями.
Основними завданнями роботи є:
дослідження локальних та глобальних властивостей напівгруп напівстохастичних матриць;
побудова нових графоаналітичних характеристик матриць і встановлення зв’язку з класичними;
застосування графоаналітичного підходу до розв’язування класичних задач з теорії матриць;
дослідження топологічних властивостей напівгруп напівстохастичних матриць;
побудова основ теорії квазімарковських ланцюгів;
розширення базової множини, що з одного боку дає структуру алгебри, а з іншого – залишає спроможним інструментарій, розроблений для напівстохастичних матриць.
Методи дослідження. При дослідженні алгебраїчних властивостей напівгрупи напівстохастичних матриць використовувались методи загальної теорії напівгруп, зокрема, для побудови інверсних елементів – різні методи узагальненого обертання матриць. Методи теорії графів знайшли застосування через граф, породжений напівстохастичною матрицею, а прийом напівстохастичного розширення будь-якої квадратної матриці дозволяє використовувати графоаналітичні методи до розв’язування класичних задач теорії матриць. Методи теорії різницевих рівнянь були використані при з’ясуванні умов ергодичності і регулярності напівстохастичних матриць. І нарешті, методи теорії ланцюгів Маркова зі скінченною множиною станів були застосовані для побудови основ теорії квазімарковських ланцюгів.
Наукова новизна одержаних результатів. Всі результати, сформульовані і доведені в дисертації, є новими, строго обгрунтованими. В роботі вперше об’єктом дослідження стала алгебраїчна структура, базовою множиною якої є множина квадратних матриць з елементами з поля , сума елементів кожного рядка яких дорівнює одиниці, яка за рахунок того, що узагальнене обертання елементів цієї множини не виводить за її межі, є регулярною напівгрупою, а точніше напівгрупою Кліффорда. А введене поняття напівстохастичного розширення матриці (перехід від матриці порядку до матриці порядку , у якій блок збігається із заданою матрицею, а перші елементів останнього стовпця є числа, що забезпечують стохастичність перших рядків, в рядку на останньому місці стоїть 1, всі інші елементи нулі) дає можливість „занурити” напівгрупу у напівстохастичну напівгрупу. З допомогою графа, породженого напівстохастичною матрицею, введено нові числові характеристики матриці (індекс вершини цього графа, індекс матриці), через які подано лівий власний вектор заданої матриці, що відповідає власному числу 1. Таке подання покладено в основу нового методу розв’язування систем лінійних рівнянь і побудову нового методу їх укрупнення, тобто переходу до розв’язування систем меншої розмірності.
З’ясовано, за яких умов циклічні групи, породжені напівстохастичною матрицею, володіють невласними елементами, тобто за яких умов збігаються за Коші або за Чезаро послідовності, знайдено явне подання таких матриць.
Вперше об’єктом дослідження стала ще одна алгебраїчна структура, а саме алгебра рангу квадратних матриць із сталою сумою елементів рядків. Доведено, що коли функція визначена на спектрі матриці, причому диференційовна разів, де – кратність кореня мінімального многочлена цієї матриці, то, причому характеристика дорівнює значенню функції на характеристиці матриці.
З’ясовано, що матрична норма Гільберта-Шмідта породжується скалярним добутком, а тому є можливість будувати аналіз відображень алгебри в себе.
Напівстохастична матриця є породжуючим елементом ще одного нового об’єкту дослідження, а саме квазімарковського ланцюга як послідовності множин вершин графа, породженого такою матрицею, яких можна досягнути за певне число переходів. Відмінні від нуля елементи матриці є індексами відповідних орієнтованих дуг, а добуток індексів дуг, що складають певний шлях на графі, є індексом переходу з однієї в іншу вершину.
Узагальненням початкового розподілу ймовірностей є поняття напівстохастичного розподілу індексів (вектора, компоненти якого є комплексні числа, сума яких 1), а узагальненням поняття стаціонарного розподілу ймовірностей є поняття інваріантного відносно лінійного перетворення, що визначається основною матрицею, розподілу індексів. В роботі закладено основи теорії квазімарковських ланцюгів
Практичне значення одержаних результатів. Результати дослідження можуть бути використані при розв’язуванні лінійних систем рівнянь з погано обумовленою матрицею (діагональні елементи не беруть участі у формуванні розв’язку), а особливо перспективною є побудова нових алгебр скінченного рангу.
Особистий внесок здобувача. Всі результати дисертаційної роботи отримані автором самостійно або за його особистою участю. Результати спільної роботи [3], викладені в другому підрозділі першого розділу, отримані автором самостійно, постановка завдання – керівника.
Апробація результатів дисертації. Результати доповідались та обговорювались на таких наукових конференціях:
-міжвузівська регіональна наукова конференція (Кіровоград, 1999 р.);
-ІІ Міжнародна алгебраїчна конференція в Україні, присвячена пам’яті проф. Калужніна Л.А. (Київ- Вінниця, 1999 р.);
-ІІІ Міжнародна алгебраїчна конференція в Україні (Суми, 2001 р.);
-Шоста Міжнародна Наукова Конференція ім. акад. М.Кравчука (Київ, 1997 р.);
-Восьма Міжнародна Наукова Конференція ім. акад. М.Кравчука (Київ, 2000 р.);
-Дев’ята Міжнародна Наукова Конференція ім. акад. М.Кравчука (Київ, 2002р.);
-Десята Міжнародна Наукова Конференція ім. акад. М.Кравчука (Київ, 2004р.);
-науково-методичні звітні конференції викладачів Вінницького державного педагогічного університету ім.М.Коцюбинського (Вінниця, 1996-2004рр.), науково-практична конференція, присвячена пам’яті М.В.Остроградського (Вінниця, 2001 р.).
Доповідались на алгебраїчному семінарі у Вінницькому державному педуніверситеті ім. М.Коцюбинського (Вінниця, 2001, 2002р.);
були предметом доповіді на науковому семінарі в Національному педуніверситеті імені М.П.Драгоманова (Київ, 2003р.);
доповідалися на алгебраїчному семінарі в Київському національному університеті ім. Тараса Шевченка (Київ, 2004р.).
Публікації. Основні положення дисертації викладені у 6 статтях у збірниках наукових праць і в 12 – в тезах і матеріалах конференцій [1-18]. З них 5 надруковано у виданнях з переліку, затвердженого ВАК України, 6 - тези доповідей на міжнародних наукових конференціях.
Структура дисертації. Робота складається з вступу, трьох розділів (перший і третій розділи містять по три підрозділи, другий – два підрозділи), висновків та списку використаних джерел, що містить 43 найменування. Повний обсяг роботи – 146 сторінок, з яких 142 сторінки основного змісту і 4 сторінки використаних джерел.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтовується актуальність теми, формулюється мета роботи та основні задачі. Приводяться її основні результати.
Ми називаємо квадратну матрицю напівстохастичною, якщо її елементи з поля, і сума елементів у кожному рядку дорівнює 1. Якраз у першому підрозділі першого розділу вивчаються властивості алгебраїчної структури, базовою множиною якої є множина всіх напівстохастичних матриць порядку, а бінарною операцією є звичайне множення матриць. Оскільки ця операція не виводить за межі, то – напівгрупа з одиницею. Оскільки за умови, що – неособлива, , а якщо – особлива, то згідно з теоремою 1.1.2 для неї існує напівобернена напівстохастична матриця, а тому напівгрупа є регулярною, причому модифікований нами метод, описаний у Судакова Р.С. Судаков Р.С. Теория псевдополуобратных матриц и её применения к задачам оценки надёжности. – М.: Знание, 1981. – С.42–106., дозволяє будувати напівобернену матрицю для кожної матриці. Щоб уникнути неоднозначності було обрано варіант узагальненого обертання, запропонований Турбіним А.Ф.*** Турбин А.Ф. Формулы для вычисления полуобратной и псевдообратной матрицы // Журнал вычислительной математики и мат. физики. – 1974. – Т.14, 3. – С. 772–776.*, а саме, вважаючи, що матриця є поданням в заданому базисі певного лінійного оператора, а – матричне подання його власного проектора, за узагальнену обернену матрицю до матриці прийнято
.
Доведено у теоремі 1.1.3, що для будь-якої напівстохастичної матриці . Центральною у цьому параграфі є
Теорема .1.4 Кожен елемент напівгрупи, який має власний проектор, породжує циклічну групу, одиницею якої є матриця, а елементом, оберненим до елемента, є елемент.
Як ілюстрацію розглянуто напівгрупу. З’ясовано, що вона є напівгрупою Кліффорда і у ній існують різні циклічні групи зі спільними елементами, відмінними від одиничного (теореми 1.1.5, 1.1.6).
У цьому ж підрозділі введено поняття напівстохастичного розширення.
Означення .1.2 Нехай – довільна квадратна матриця -го порядку над полем . Матрицю (1.1.13)
називаємо напівстохастичним розширенням.
Множина матриць виду (1.1.13) відносно множення утворюють піднапівгрупу напівгрупи, причому ця напівгрупа ізоморфна напівгрупі квадратних матриць -го порядку, тобто можна говорити про занурення напівгрупи у напівгрупу. А щодо операцій напівстохастичного розширення і узагальненого обертання, то має місце
Теорема .1.10 Для будь-якої квадратної матриці над полем має місце рівність
.
А тому, якщо є узагальнено оберненою до матриці, то напівстохастичне розширення є узагальнено оберненою до матриці. І, навпаки, якщо матриця має вигляд (1.1.13), тобто, і узагальнена обернена до неї, то є матриця, яка одержується зняттям напівстохастичного розширення з. Таким чином, напівгрупа квадратних матриць порядку має таку ж алгебраїчну структуру, що і піднапівгрупа напівгрупи, і тому техніка розв’язування задач у напівгрупі може бути використана при розв’язуванні задач, що стосуються напівгрупи.
У другому підрозділі першого розділу вводяться графоаналітичні характеристики матриці порядку над полем .
Означення .2.2 Граф, де, , називаємо графом, породженим матрицею, або просто графом матриці. Матричний елемент назвемо вагою дуги графа.
Означення .2.3 Індексом (вагою) нижньої решітки, де
,
-ої вершини графа називаємо число .
Суму індексів всіх нижніх решіток -ої вершини графа називаємо індексом -ої вершини графа і позначатимемо, а суму індексів всіх вершин графа – індексом матриці і позначаємо.
Основним результатом цього підрозділу є
Теорема 1.2.2 Для кожної матриці виконуються рівності
. (1.2.1)
В теоремах 1.2.3, 1.2.4 встановлюються зв’язки для індексів різних вершин для матриць спеціальної структури. Зв’язок індексів вершин з класичними характеристиками квадратних матриць встановлює
Теорема .2.5 Для напівстохастичної матриці індекс -ої вершини дорівнює головному мінору -го порядку матриці, що одержується з останньої викресленням -го рядка і -го стовпця.
На підставі цього маємо, що індекс напівстохастичної матриці дорівнює сумі головних мінорів -го порядку матриці, а визначник матриці дорівнює індексу -ої вершини графа, породженого матрицею.
Теорема 1.2.6 Якщо для напівстохастичної матриці , то одиниця є її простим власним числом.
Якщо неособлива, то розв’язком матричного рівняння
(1.2.10)
є матриця.
Теорема 1.2.7 Розв’язок рівняння (1.2.10) подається у вигляді
,
де – напівстохастичне розширення матриці, а саме таке, що , , – довільні числа, відмінні від нуля, , – сума індексів нижніх решіток -ої вершини цього графа, а – сума індексів нижніх решіток -ої вершини, кожна з яких містить дугу.
На підставі теореми 1.2.6 пропонуємо новий метод обертання матриць, а саме для неособливої матриці
, .
У третьому підрозділі першого розділу побудоване явне подання лівого власного вектора напівстохастичної матриці, що відповідає власному числу 1, а саме в теоремі 1.3.1 (основній у цьому підрозділі) стверджується, що коли вектор ненульовий, то він є лівим власним вектором матриці, що відповідає власному числу 1. А якщо, то вектор єдиний напівстохастичний власний вектор матриці, що відповідає власному числу 1.
Якщо напівстохастичну матрицю розбити на блоки розмірності, , , такі, що матриці, оборотні, то матриці
,
,
напівстохастичні.
Теорема .3.4 Якщо лівий вектор, який відповідає власному числу 1, причому існує, то вектори, є лівими власними векторами, які відповідають власному числу 1, відповідно матриць і.
Якщо ж, навпаки, (), () – ліві власні вектори, які відповідають власному числу 1, відповідно матриць і, то вектор, взагалі кажучи, не є лівим власним вектором матриці. Однак, як доводиться у теоремі 1.3.5, якщо, то вектор, де
, , , ,
є лівим власним вектором, який відповідає власному числу 1, матриці.
Явне подання лівого власного вектора, що відповідає власному числу 1, напівстохастичної матриці покладено нами в основу нового методу розв’язування систем лінійних рівнянь, а теореми 1.3.4, 1.3.5 є теоретичною основою методу розв’язування систем меншої розмірності.
В другому розділі „Елементи аналізу у напівгрупах напівстохастичних матриць” розглянуто дві задачі: задача існування границі, де – напівстохастична матриця, і задача побудови елементарних функцій від матриць. Але оскільки значення функції на напівстохастичній матриці, взагалі кажучи, не є напівстохастична матриця, то довелось розширити клас досліджуваних матриць, а саме за базову множину було взято множину квадратних матриць з комплексними елементами зі сталою сумою елементів рядків кожної такої матриці.
Оскільки напівгрупа є регулярною, то для елементів, які породжують циклічні групи, необхідно з’ясувати, за яких умов такі групи володіють невласними елементами, тобто за яких умов існує
або ,
а можливо послідовність збігається за Чезаро.
Ми називаємо напівстохастичну матрицю регулярною, якщо існує і – ергодичною, якщо існує .
Якщо для напівстохастичної матриці , то матриця
ідемпотентна, , і для кожного натурального
(теореми 2.1.1, 2.1.2), причому
або
у випадку, коли вона відповідно регулярна або ергодична (теореми 2.1.3, 2.1.4).
Критерій регулярності дає
Теорема 2.1.5 Напівстохастична матриця, у якої, регулярна тоді і тільки тоді, коли існує таке, що, де, де – максимальне власне число матриці.
Виходячи з того, що рівність можна розглядати як систему різницевих рівнянь , , то з врахуванням структури розв’язку такої системи достатні умови регулярності матриці можна сформулювати у вигляді наступної теореми.
Теорема 2.1.6 Якщо одиниця просте власне число матриці, а всі інші власні числа за модулем менші за 1, то матриця регулярна.
Якщо матриця регулярна, то вона ергодична. А от у випадку, коли 1 – просте власне число матриці, – прості власні числа, які є коренями з одиниці степенів відповідно, а всі решта власних чисел за модулем менші за 1, то ця матриця ергодична, але не регулярна (теорема 2.1.9).
Якщо – невласний елемент групи, породженої напівстохастичною матрицею, то – неособлива, і тоді
,
причому, комутує з, має ті самі власні вектори, що відповідають власному числу 1, що й матриця, і виконується рівність (теореми 2.1.7, 2.1.8, 2.1.10, 2.1.11).
В другому підрозділі другого розділу досліджується ще один об’єкт, а саме розглядається множина, де, всіх квадратних матриць порядку над полем таких, що сума елементів кожного рядка дорівнює ( своє для кожної матриці). Число ми назвали характеристикою матриці і позначаємо. Очевидно, що відносно додавання матриць і множення матриці на комплексне число множина є лінійний простір розмірності над полем , ця множина також замкнена відносно природного множення, причому для будь-яких і з .
Таким чином, множина – алгебра рангу, для якої– підалгебра, а – напівгрупа напівстохастичних матриць.
Якщо матриця неособлива, то, причому, а коли – особлива і – її власний проектор, то, , причому, , якщо, і, , якщо (теореми 2.2.1, 2.2.2).
Основною у цьому підрозділі є
Теорема 2.2.3 Якщо функція визначена на спектрі матриці, причому диференційовна разів (), де – кратність кореня мінімального многочлена цієї матриці, то, причому .
Змістовні результати отримані для алгебри (теореми 2.2.4, 2.2.5, 2.2.6).
У третьому розділі поняття напівстохастичної матриці покладено в основу узагальнення ланцюга Маркова. У його першому підрозділі вводяться основні поняття.
Якщо - граф, породжений напівстохастичною матрицею А, то
Означення .1.1 Послідовність, де, () – множина вершин графа таких, що для кожного існує хоч один шлях на цьому графі довжини з -ої у -ту вершину, називатимемо квазімарковським ланцюгом на графі, породженим матрицею, з початком у вершині .
Скориставшись термінологією теорії графів і тим, що кожна орієнтована дуга наділена вагою, у стандартний спосіб введено поняття індекса шляху, а суму всіх шляхів довжиною t з i-ої у j-ту вершину називаємо індексом переходу квазімарковського ланцюга з вершини i у вершину j за t кроків. На квазімарковські ланцюги перенесено основні поняття ланцюгів Маркова. Зокрема, узагальненням початкового розподілу ймовірностей є поняття напівстохастичного розподілу індексів (вектора, компоненти якого є комплексні числа, сума яких дорівнює 1), а узагальненням поняття стаціонарного розподілу ймовірностей є поняття інваріантного відносно лінійного перетворення, що визначається основною матрицею, розподілу індексів. Виділено класи поглинаючих, регулярних та ергодичних ланцюгів.
У другому підрозділі третього розділу будується теорія поглинаючих ланцюгів.
Означення .2.1 Квазімарковський ланцюг, де для, з початковим розподілом індексів будемо називати поглинаючим, якщо існує підстановка така, що його породжуюча матриця зводиться до вигляду
, де – матриці розмірності і такі, що для кожної вершини з множини існує хоч один шлях, який починається у цій вершині і закінчується в одній з вершин множини, – одинична матриця розмірності, – нульова матриця розмірності. Множина є множиною тупикових вершин. Очевидно, що при піднесенні матриці до степеня маємо:
,
тобто на графі, породженому матрицею, вершини є тупиковими.
Теорема .2.1 Якщо або, або ,
або існує таке, що,
то матриця неособлива, причому ряд сумовний відповідно або за Коші, або за Чезаро, або за Ейлером і його сумою є матриця.
Визначальну роль останньої матриці пікреслює термін фундаментальна матриця і позначення.
Якщо стохастичне розширення матриці, причому у ньому для не дорівнюють нулю, то визначник матриці дорівнює індексу -ої вершини графа. А тому умова є необхідною і достатньою умовою існування фундаментальної матриці для поглинаючого квазімарковського ланцюга, а формула
є її явним поданням.
Фундаментальна матриця комутує з матрицею, причому, а матриця напівстохастична і кожен її ненульовий стовпець є правим власним вектором матриці А, що відповідає власному числу 1, тобто (теореми 3.2.2, 3.2.3).
Теорема .2.5 Матриця є розв’язком рівняння , а матриця є розв’язком рівняння .
Замінивши усереднення випадкових величин усередненням значень функцій певним розподілом чисел, нормованим одиницею, елементи матриць
,
де – матриця, елементами якої є квадрати елементів матриці, можна трактувати відповідно як квазісередні індексів переходів із незворотної вершини у тупикову, як індекси переходів із незворотної вершини у тупикову, як квазідисперсію індексів переходів із незворотної вершини у тупикову.
У третьому підрозділі третього розділу вивчаються регулярні та ергодичні ланцюги. Класифікація проводиться на підставі характеру породжуючої матриці.
Якщо породжуюча матриця є регулярною, то і сам ланцюг є регулярним, а у тому випадку, коли і , то сильно регулярним (якщо елементи матриці відмінні від нуля).
Для таких ланцюгів в основі дослідження є матриця .
Теорема .3.1 Матриця напівстохастична, комутує з, задовольняє рівність
і вектор
є її лівим власним вектором, що відповідає власному числу 1.
Теорема .3.3 Для регулярного квазімарковського ланцюга, породженого матрицею, всі елементи матриці якого відмінні від нуля, рівняння має єдиний розв’язок, де – діагональна матриця з діагональними елементами.
Теорема .3.5 Якщо для регулярного квазімарковського ланцюга, породженого матрицею, всі елементи матриці відмінні від нуля, то рівняння має єдиний розв’язок .
Враховуючи імовірнісний зміст розв’язків подібних рівнянь для регулярних ланцюгів Маркова, елементи матриці можна трактувати як квазісередні числа переходів із -ої вершини до першого попадання у -ту вершину (– квазісереднє числа переходів до першого повернення в -ту вершину), а елементи матриці, де – матриця, елементами якої є квадрати відповідних елементів матриці, можна трактувати як квазідисперсії числа переходів з -ої до першого попадання у -ту вершину.
ВИСНОВКИ
В даній дисертаційній роботі розглядаються квадратні матриці над полем, сума елементів кожного рядка яких дорівнює 1. Множина таких матриць відносно природньої операції множення є регулярна напівгрупа. При дослідженні властивостей елементів виявились досить ефективними введені нові характеристики: індекси вершин графа, породженого напівстохастичною матрицею, та індекс матриці. Якраз через ці характеристики в явному вигляді подається лівий власний вектор, що відповідає власному числу 1, напівстохастичної матриці. А введена операція напівстохастичного розширення дала можливість “занурити” напівгрупу у напівгрупу.
Графоаналітичний метод спроможний розв’язувати класичні задачі: обчислення визначника, обертання матриці. Він є основою нового підходу до розв’язування лінійних систем.
Оскільки кожен елемент напівгрупи породжує циклічну групу, то в роботі з’ясовано, за яких умов вони володіють невласними елементами, тобто за яких умов збігається за Коші або за Чезаро послідовність. І знайдено явне подання такого елемента через індекси вершин графа, породженого матрицею.
Якщо умову рівності 1 суми кожного рядка замінити вимогою сталості сум рядків, то напівгрупа розширюється до алгебри рангу. Більше того, для кожної функції, визначеної на спектрі матриці є, є. А оскільки алгебра нормується, причому обрана норма породжується скалярним добутком, то отримані результати є відправною точкою для побудови аналізу відображень алгебри в себе.
Отримані результати дали можливість через напівстохастичну матрицю і граф, породжений нею, ввести новий об’єкт – квазімарковський ланцюг, основними характеристиками якого є функціонали (індекси переходів) на його реалізаціях. Виділено два класи таких ланцюгів: поглинаючих за наявністю тупикових вершин на графі, регулярних і ергодичних за наявністю стійкості індексів переходів при зростанні їх числа. Важливою характеристикою таких ланцюгів є фундаментальна матриця, для якої знайдено явне подання, що у свою чергу дозволило знайти квазісереднє і квазідисперсію числа переходів на графі з i-тої вершини до першого попадання у j-ту вершину.
Автор висловлює щиру подяку своєму науковому керівникові доктору фізико-математичних наук, професору Працьовитому М.В. за допомогу та постійну увагу до роботи.
ПУБЛІКАЦІЇ АВТОРА ЗА ТЕМОЮ ДИСЕРТАЦІЇ
Вотякова Л.А. О некоторых свойствах полугруппы полустохастических матриц// Известия Гомельского Государственного университета им. Ф.Скорины.- 2001.- №3(6).-Вопросы алгебры-17.-С.58-67.
Вотякова Л.А. Графо-аналітичні характеристики напівстохастичних матриць та їх застосування//Наукові записки ВДПУ ім.М.Коцюбинського. Сер. Фізика і математика.-Вінниця, 2002.-№1.-С.242-257.
Працьовитий М.В., Вотякова Л.А. Графо-аналітичні характеристики напівстохастичних матриць та їх застосування//Наукові записки НПУ імені М.П.Драгоманова. Фізико-математичні науки.-Київ,2002.-№3.-С.197-215.
Вотякова Л.А. Поглинаючі квазімарковські ланцюги// Вісник Киівського університету.Серія: фіз.-мат. науки.-Київ,2003.-№1.-С.9-15.
Вотякова Л.А. Регулярні квазімарковські ланцюги// Вісник Киівського університету.Серія: фіз.-мат. науки.-Київ,2003.-№3.-С.33-39.
Вотякова Л.А. Матрична алгебра // Наукові записки НПУ імені М.П.Драгоманова. Фізико-математичні науки. –– К.: НПУ імені М.П.Драгоманова. –– 2003, № 4. –– С. 14-17.
Томусяк А.А., Вотякова Л.А. Регулярні квазімарковські ланцюги// Тези доповідей звітної наукової конференції викладачів та студентів за 1994 рік.- Вінниця.- 1995.- С.7-8.
Вотякова Л.А. Зменшення розмірності лінійних систем рівнянь шляхом розбиття на блоки// Звітна наукова конференція викладачів за 1995 рік.-Вінниця.- 1996.- С.8.
Вотякова Л.А. Напівстохастичні матриці, властивості і застосування// Шоста Міжнародна наукова конференція ім. акад. М.Кравчука. Матеріали конференції.-Київ.- 1997.- С.95.
Панков О.А., Вотякова Л.А. Напівстохастичні оператори у скінченновимірному просторі// Звітна наукова конференція викладачів за 1997 рік. Тези доповідей .-Вінниця.- 1998.-С.26-27.
Вотякова Л.А. Напівгрупа напівстохастичних матриць, її структура// Звітна наукова конференція викладачів за 1998 рік.-Вінниця.- 1999.- С.13-15.
Votiakova L.A., Tomusiak A.A. On some Clifford’s semigroups// Друга Міжнародна алгебраїчна конференція в Україні, присвячена пам’яті проф. Калужніна Л.А.- Київ- Вінниця.-1999.- С.50.
Вотякова Л.А., Томусяк А.А. Графо-аналітичний метод розв’язування лінійних систем рівнянь// Матеріали міжвузівської регіональної наукової конференції.- Кіровоград.- 1999.- С.21-23.
Вотякова Л.А. Пониження розмірності лінійних систем рівнянь шляхом розбиття на блоки// 8 Міжнародна наукова конференція ім. акад. М.Кравчука. Матеріали конференції.-Київ.- 2000.- С.424.
Вотякова Л.А. Ергодичні квазімарковські ланцюги// Матеріали науково-практичної конференції, присвяченої пам’яті М.В.Остроградського.- Вінниця.- 2001.- С.26-32.
Вотякова Л.А. Регулярні групи кліффордової напівгрупи // 3 Міжнародна алгебраїчна конференція в Україні.- Суми.-2001.- С.148-149.
Вотякова Л.А. Регулярні та ергодичні квазімарковські ланцюги // 9 Міжнародна наукова конференція ім. акад. М.Кравчука. Матеріали конференції.-Київ.- 2002.- С.416.
Вотякова Л.А. Про один метод побудови алгебр гіперкомплексних чисел// 10 Міжнародна наукова конференція ім. акад. М.Кравчука. Матеріали конференції.-Київ.- 2004.- С.334.
АНОТАЦІЯ
Вотякова Л.А. Напівгрупи напівстохастичних матриць та їх застосування.- Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.06 – алгебра і теорія чисел. – Київський національний університет імені Тараса Шевченка, Київ, 2004.
Робота присвячена вивченню напівгруп напівстохастичних матриць. Доведено, що такі напівгрупи регулярні і за наявності власного проектора кожен елемент породжує циклічну групу. З’ясовано умови існування невласного елемента у такої групи, причому для явного подання цього елемента істотно використовувались характеристики графа, породженого напівстохастичною матрицею. Графоаналітичні характеристики дають явне подання лівого власного вектора напівстохастичної матриці, який відповідає власному значенню 1, що покладено в основу нового методу розв’язування лінійних систем рівнянь.
Оскільки функції від напівстохастичних матриць, взагалі кажучи, не є напівстохастичними, то їх напівгрупи розширюються до алгебр скінченного рангу, в яких побудовано основи аналізу.
Безпосереднім застосуванням напівстохастичних матриць є їх використання як породжуючих елементів квазімарковських ланцюгів. В залежності від типу породжуючої напівстохастичної матриці виділені і вивчаються основні класи таких ланцюгів.
Ключові слова: напівгрупа напівстохастичних матриць, напівстохастичне розширення, граф, індекс вершини графа, індекс матриці, регулярна напівстохастична матриця, ергодична напівстохастична матриця, алгебра скінченного рангу, квазімарковський ланцюг.
АННОТАЦИЯ
Вотякова Л.А. Полугруппы полустохастических матриц и их применения.- Рукопись.
Диссертация на соискание учёной степени кандидата физико-математических наук по специальности 01.01.06 – алгебра и теория чисел. – Киевский национальний университет имени Тараса Шевченко, Киев, 2004.
Работа посвящена изучению полугрупп полустохастических матриц. Доказано, что такие полугруппы регулярны и при наличии собственного проектора каждый элемент порождает циклическую группу. Введённая операция полустохастического расширения позволяет полугруппу квадратных матриц порядка n “погрузить” в полугруппу специальных полустохастических матриц порядка n+1. Получены условия существования несобственного элемента в циклической группе, причём для явного представления такого элемента существенно использованы характеристики графа, порождённого полустохастической матрицей, такие как индекс нижней решётки графа, индекс вершины графа и индекс матрицы. Эти характеристики дают явное представление левого собственного вектора, который соответствует собственному числу 1, полустохастической матрицы. А отличие от нуля индекса матрицы является гарантом того, что 1 - простое собственное число. Показано, что индексы вершин графа, порождённого полустохастической матрицей, есть миноры её характеристической матрицы при, а определитель порождающей полустохастической матрицы равен индексу n+1-ой вершины графа, порождённого полустохастическим расширением вышеупомянутой характеристической матрицы. Операция полустохастического расширения позволяет применить графоаналитический метод и для вычисления определителя, и для обращения произвольной квадратной матрицы. Графоаналитические характеристики заложены также в основу нового метода решения линейных систем уравнений, и более того, появляется возможность укрупнения систем и перехода к решению систем низшей размерности.
Полугруппа полустохастических матриц расширена путём снятия условия равенства 1 суммы по строкам и наложения условия постоянства суммы элементов каждой строки матрицы. Такое множество относительно сложения и умножения матриц есть алгебра ранга. Значение функции на матрице из этой алгебры есть матрица из этой же алгебры. Нормировав её матричной нормой Гильберта-Шмидта и убедившись, что эта норма порождается скалярным произведением, мы заложили основы построения отображений таких алгебр в себя.
Непосредственным применением полустохастических матриц является их использование как порождающих матриц квазимарковских цепей. В зависимости от типа порождающей полустохастической матрицы выделяем следующие классы квазимарковских цепей: поглощающие, регулярные и эргодические. Строим так называемую фундаментальную матрицу, свою для каждого класса цепей, и с её помощью получаем явные представления основных характеристик квазимарковских цепей, которые являются обобщением известных характеристик цепей Маркова.
Ключевые слова: полугруппа полустохастических матриц, полустохастическое расширение, граф, индекс вершины графа, индекс матрицы, регулярная полустохастическая матрица, эргодическая полустохастическая матрица, алгебра конечного ранга, квазимарковская цепь.
ABSTRACT
Votiakova L.A. Semigroups of semistochastic matrices with applications. – Manuscript.
Thesis for a Candidate’s degree in speciality 01.01.06 – algebra and number theory. – Kyiv National Taras Shevchenko University, Kyiv, 2004.
Thesis is devoted to study semigroups of semistochastic matrices. It is proved that such semigroups are regular and in the presence of proper projector each element generats the cycle group. We find conditions of existence in such group improper element. We use characteristices of the graph making by semistochastic matrix (index of the graph peak, index of matrix) to introduce the left proper vector corresponding to proper value 1. They are used in new method of solving linear systems.
Function from semistochastic matrix is not semistochastic in general. So we widen semigroup to algebra of finite rang. And in this algebra bases of analisys are constructed.
One of applications of semistochastic matrices is generalizing Markov chains by help semistochastic matrix. It is introduced classes almost Markov chains and investigated thier characteristices.
Key words: semigroup of semistochastic matrices, semistochastic broaden, graph, index of the graph peak, index of matrix, regular semistochastic matrix, ergodic semistochastic matrix, algebra of finite rang, almost Markov chain.
