Вступ

Кваліфікаційну роботу присвячено дослідженню зв’язків між теорією графів та структурною теорією кілець. Один із аспектів теорії кілець є вивчення властивостей кілець за допомогою теорії графів. Важливим етапом у розвитку теорії скінченновимірних алгебр над полем та їх зображень була робота швейцарського математика Габріеля, в якій було введено поняття сагайдака скінченновимірної алгебри.

Поняття сагайдака скінченновимірної алгебри було перенесено В.В. Кириченком на випадок нетерових напівдосконалих кілець у 1975 році як правої схеми кільця. Багато властивостей кілець можна охарактеризувати властивостями їх сагайдаків. Перші важливі результати в цьому напрямі належать визначним українським алгебраїстам В.В. Кириченко та Ю.А. Дрозду.

Один із важливих класів, що виникає в різних питаннях теорії кілець та теорії цілочисельних зображень, – клас черепичних порядків. З точки зору абстрактної теорії кілець черепичний порядок є первинним нетеровим напівдосконалим та напівдистрибутивним кільцем з ненульовим радикалом Джекобсона. Черепичні порядки (tiled orders) вивчалися Ятегаонкаром В.А., Тарсі Р.Б. та іншими математиками, починаючи з 70-их років минулого століття. Паралельно такі кільця вивчалися у Радянському Союзі Завадським О.Г. і Кириченком В.В. під назвою напівмаксимальні кільця.

Особливо великий внесок у розвиток теорії черепичних порядків зробили Сімсон Д., Рогенкамп К.В., Дрозд Ю.А., Завадський О.Г. та Кириченко В.В.

Кожний черепичний порядок повністю визначається своєю матрицею показників і дискретно нормованим кільцем. Багато властивостей таких кілець повністю визначаються їх матрицями показників, зокрема, сагайдаки таких кілець. Порівняно недавно матриці показників стали окремим об’єктом вивчення. Сагайдак матриці показників співпадає з сагайдаком черепичного порядку з даною матрицею показників. Для дослідження матриць показників та їх сагайдаків використовуються також комбінаторні та геометричні методи.

Матриці показників та черепичні порядки притягують увагу багато алгебраїстів. Цим питанням присвячена монографія Сімсона “Linear Representations of Partially Ordered Sets and Vector Space Categories” та розділи першого та другого томів монографії М. Хазевінкеля, Н. Губарені, В.В. Кириченка “Alebras, Rings and Modules”.

Японські математики Фуджита, Сакай виявили зв’язки між черепичними порядками та скінченновимірними алгебрами над полем.

У кваліфікаційній роботі вивчаються властивості матриць показників та сагайдаків матриць показників.

1. Невід’ємні матриці та сагайдаки.

Наведемо основні означення, що використовуються в теорії скінченних орієнтованих графів.

Означення 1.1. Нехай VQ – скінченна непорожня множина, VQ²–декартовий квадрат. Орієнтований граф – це пара (VQ, AQ), де AQ VQ². Елементи множини VQ називаються вершинами орієнтованого графа Q=(VQ, AQ), а елементи множини AQ – його стрілками. Стрілки зображаються у вигляді упорядкованої пари (v, w) вершин, v називається початком, а w — кінцем стрілки (v,w).

B дисертації, в основному, ми будемо розглядати сагайдаки, тобто скінченні орієнтовані графи. Стрілка  і вершина v (а також  і w) називаються інцидентними, якщо стрілка =(v,w).

Нехай Q₁=(VQ₁, AQ₁) і Q₂=(VQ₂, AQ₂) – сагайдаки та f : VQ₁ VQ₂ – бієкція. Якщо для довільних вершин u і v сагайдака Q₁ їх образи f(u) та f(v) суміжні в Q₂ тоді і тільки тоді, коли u та v суміжні в Q₁, то ця бієкція називається ізоморфізмом сагайдака Q₁ на сагайдак Q₂. У такому випадку говорять, що сагайдаки ізоморфні.

Шляхом в сагайдаку називаємо послідовність стрілок вигляду (v₁, v₂), (v₂, v₃), ..., (v_m-1, v_m). Кажуть, що цей шлях йде з v₁ у v_m і має довжину m-1. Часто такий шлях зображають послідовністю v₁, v₂, ..., v_m вершин, що лежать на ньому.

Шлях називається простим, якщо всі ребра і всі вершини у ньому різні. Шлях замкнений, якщо v₀=v_n.

Замкнений шлях називається циклом. Простий цикл – це замкнений простий шлях довжини не менше 1. Відстань між двома вершинами – це довжина найкоротшого шляху, що з’єднує їх.

Цикл, що має довжину 1, називається одноточковим циклом або просто петлею.

Скінченний сагайдак називається сильно зв'язним, якщо для будь-якої пари вершин існує шлях, що з'єднує їх. Для зручності сагайдак, який складається з однієї вершини і не має жодної петлі вважається сильно зв'язним.

Підсагайдаком сагайдака Q₁=(VQ₁, AQ₁) називається сагайдак Q₂=(VQ₂, AQ₂), де VQ₂ належить VQ₁ і AQ₂ належить AQ₁, такий що разом із усякою парою вершин u та v містить і стрілку (u, v), якщо вона є в сагадаку Q₁.

Означення 1.2. Сагайдак без кратних петель і кратних стрілок називається простим сагайдаком.

Означення 1.3. Сагайдак називається повним, якщо для довільних двох різних вершин v та w сагайдак має стрілку (v, w).

Позначимо через 1, 2, …, s вершини сагайдака Q і припустимо, що q_ij – кількість стрілок, які виходять з вершини і і закінчуються в вершині j. Якщо стрілок нема, то q_ij=0.

Матриця

називається матрицею суміжності сагайдака Q і позначається [Q].

Означення 1.4. Прямокутну матрицю A=(a_ik) c дійсними елементами ми будемо називати невід’ємною (позначення: А≥0) або додатньою (позначення: А>0), якщо всі елементи матриці A невід’ємні (відповідно додатні): a_ik ≥0 (відповідно a_ik >0).

Відмітимо, що будь-яка матриця суміжності є невід’ємною матрицею. Крім того, всі елементи матриці суміжності простого сагайдака дорівнюють 0 або 1. В цьому випадку матриця [Q] є (0, 1) – матрицею. Навпаки, якщо матриця суміжності [Q] є (0, 1) – матриця, то сагайдак Q є простим.

Теорія невід’ємних матриць широко використовуються в теорії сагайдаків.

Позначимо через М_п() множину дійсних квадратних матриць порядку п. Нехай  — перестановка чисел 1, 2, …, п і нехай — відповідна матриця підстановки, де е_ij — матричні одиниці. Очевидно, що добуток є одиничною матрицею кільця матриць М_п(), де знак Т– транспонування.

Означення 1.5. Будемо казати, що матриця A₁ M_n() перестановочно еквівалентна матриці A₂, якщо існує матриця підстановки P_ така, що

A₁₌ A₂ P_ .

Означення 1.6. Матриця ВМ_п() називається перестановочно звідною, якщо існує переставна матриця Р_ така, що

(1.1)

де В₁ і В₂ — квадратні матриці порядку менше за п. У іншому разі матриця називається перестановочно незвідною.

Розглянемо матрицю ВМ_п(). Якщо вона перестановочно звідна, то існує перестановочна матриця Р₁ така, що:

,

де С і D — квадратні матриці порядку менше п.

Якщо одна з матриць С або D перестановочно звідна, то її можна звести до вигляду, як у формулі (1.1). Тому можна вважати, що матриця В може бути зведена перестановочною матрицею Р₂ до вигляду:

Якщо принаймні одна з матриць K, H, F перестановочно звідна, то процес можна продовжити. В результаті матриця В трансформується за допомогою деякої переставної матриці Р до наступного вигляду:

(1.2)

де квадратні матриці В₁, В₂, ... , В_t є перестановочно незвідними.

Таким чином, ми довели наступне твердження.

Твердження 1.7. Нехай В М_п(). Тоді існує перестановочна матриця Р, така, що P^TBP має вигляд (1.2).

Означення 1.8. Сагайдаком матриці A=(a_ij) М_п() називається сагайдак, у якому із “i” в “j” іде стрілка тоді і тільки тоді, коли a_ij0.

Твердження 1.9. Матриця BM_n() перестановочно незвідна тоді і тільки тоді, коли сагайдак Q(B) сильно зв’язний.

Доведення. Нехай сагайдак Q(B) сильно зв’язний. Тоді, якщо матриця В перестановочно звідна, існує переставна матриця P_{ ,} така що де B₁M_р(), B₂M_q(); p<n; q<n i p+q=n. Ми можемо перенумерувати вершини Q(B) так, що не будуть існувати стрілки, які зв’язують вершину з множини {p+1, …, n} з вершинами множини {1, …, p}. Тоді сагайдак Q(B) не є сильно зв’язним.

Навпаки, нехай матриця В перестановочно незвідна. Якщо сагайдак Q(B) не сильно зв’язний, тоді існують такі вершини k і l (k  l), що не існує шляху, який зв’язує вершини k і l. Позначимо через VQ(k) множину всіх вершин сагайдака Q, які є кінцевими всіх шляхів з початковою вершиною k. Очевидно lVQ(k). Позначимо X=VQ(k), Y=VQ\VQ(k). Оскільки X, Y, XY=VQ, XY=, і не існує стрілок : x y, де xX, yY; то матриця В перестановочно звідна. Отримане протиріччя доводить твердження.

Наслідок 1.10. Сагайдак Q сильно зв’язний тоді і тільки тоді, коли матриця [Q] перестановочно незвідна.

Зауважимо, що перенумерація вершин сагайдака Q, перетворює матрицю [Q] в матрицю . З твердження 1.7 отримали твердження.

Твердження 1.11. Нехай Q — сагайдак з матрицею суміжності [Q]. Тоді існує перестановочна матриця Р, така що:

(1.3)

де матриці В₁, В₂, ..., В_t — переставновочно незвідні.

Означення 1.12. Нумерацію вершин сагайдака Q будемо називати стандартною, якщо матриця суміжності [Q] має вигляд як у твердженні 1.11.

Означення 1.13. Максимальний відносно включення сильно зв’язний підсагайдак сагайдака Q називається сильно зв’язною компонентою.

Означення 1.14. Розбиття множини вершин VQ сагайдака Q на підмножини, які попарно не перетинаються і такі, що підсагайдаки, відповідні цим підмножинам, є сильно зв’язними компонентами сагайдака Q, називається розбиттям сагайдака Q в сильно зв’язні компоненти Q₁, Q₂, …, Q_m і позначається P(Q, Q₁, Q₂, …, Q_m).

Існування розбиття сагайдака випливає безпосередньо з твердження 1.11. Покажемо, що це розбиття єдине з точністю до перенумерації вершин. Для того щоб показати єдиність такого розбиття введемо бінарне відношення на множині VS(Q)={v₁, v₂, …, v_n} всіх вершин сагайдака Q. Покладемо v_i v_j, якщо існує шлях з вершини v_i у вершину v_j та існує шлях з вершини v_j у вершину v_i. Таке відношення рефлексивне, симетричне і транзитивне — це відношення еквівалентності.

Нехай Е₁, Е₂, …, Е_т – класи еквівалентності VS(Q). Тоді і для ij. Крім того, еквівалентні класи є сильно зв’язними компонентами сагайдака Q. Тепер єдність розбиття сагайдака Q витікає з єдиності розбиття множини VS(Q) на класи еквівалентності : Е₁, Е₂, …, Е_т. Таким чином, ми довели таке твердження.

Теорема 1.15. Сагайдак Q має єдине з точністю до перенумерації вершин розбиття P(Q, Q₁, Q₂, … , Q_m) в сильно зв’язні компоненти Q₁, Q₂,…,Q_m. Тобто якщо P(Q, Q₁, Q₂, … , Q_m) і P(Q, G₁, G₂, …, G_t) –– два таких розбиття, то m= t і існує підстановка  множини {1, 2, …, m} така, що Q_i=G_(i) для i=1, 2, …,m.

Означення 1.16. Нехай Р(Q, Q₁, … ,Q_т) — розбиття сагайдака Q в сильно зв’язні компоненти Р(Q, Q₁, …, Q_т). Конденсацією Q* сагайдака Q є сагайдак, вершинами якого є точки q₁, …, q_т, які відповідають сильно зв’язаним компонентам Q₁, …, Q_т, і, крім того, стрілка з початковою вершиною q_і і кінцевою вершиною q_j існує тоді і тільки тоді, коли в Q є стрілка, початкова вершина якої належить VQ_i, а кінцева вершина належить VQ_j ( ij; і, j=1, …, m).

Означення 1.17. Сагайдак без орієнтованих циклів називається ациклічним сагайдаком. Наступне твердження очевидне.

Твердження 1.18. Сильно зв’язний ациклічний сагайдак є точкою.

Твердження 1.19. Конденсацією довільного сагайдака є ациклічний простий сагайдак.

Означення 1.20. Вершина сагайдака називається джерелом, якщо немає стрілок з кінцем в цій вершині. Вершина сагайдака називається стоком, якщо немає стрілок з початком в цій вершині.

Твердження 1.21. Довільний ациклічний сагайдак має джерело і сток.

Доведення. Згідно твердження 1.11 матриця суміжності [Q] сагайдака Q може бути подана у вигляді (1.3). Враховуючи, що сагайдак Q не має циклів, будь-яка діагональна матриця В_і в такому розкладі має порядок 1. Оскільки Q не має петель, всі ці матриці є нульовими. Отже, існує переставна матриця Р, така що:

(1.4)

Звідси сагайдак з матрицею суміжності має джерело у вершині 1 та сток у вершині n. Тому сагайдак Q ­ також має джерело і сток.

З вигляду (1.4) матриці суміжності [Q] ациклічного сагайдака Q ми отримуємо безпосередньо наступний наслідок.

Наслідок 1.22. Нехай множина вершин ациклічного сагайдака складається з t елементів. Тоді можна занумерувати ці вершини числами 1, 2, …, t таким чином, що з існування стрілки з вершини і до вершини j слідує i<j.

Означення 1.23. Нехай на множині S задано бінарне відношення ” ”, для якого виконуються наступні умови:

1. a a для довільного a S;

2. якщо a b і b a, то a=b для всіх a, b S;

3. якщо a b і b c, то a c для всіх a, b, c S.

Множина S, на якій задано бінарне відношення ”≤”, називається частково впорядкованою множиною. Якщо a b і a b, то будемо писати a<b. Елемент x називається максимальним елементом частково впорядкованої множини, якщо з x≤y слідує, що x=y. Елемент x називається мінімальним елементом частково впорядкованої множини, якщо з y≤x слідує, що y=x.

Означення 1.24. Нехай — скінченна частково впорядкована множина з відношенням порядку “”. Діаграмою S є сагайдак Q(S) з множиною вершин VQ(S)={1, …, n} і множиною стрілок AQ(S), таких що в AQ(S) є стрілка тоді і тільки тоді, коли виконуються наступні дві умови:

1. _i<_j;

2. Якщо _i _k _j , то або  _k=_i, або _k =_j .

Стрілка ациклічного сагайдака Q називається зайвою, якщо існує шлях з і до j довжини більшої за 1. Елемент b накриває елемент a, якщо a≤b та з a≤x≤b слідує, що або a=x, або x=b.

Очевидно, діаграма скінченної частково впорядкованої множини S ациклічного простого сагайдаку не має зайвих стрілок.

Твердження 1.25. Нехай Q — ациклічний простий сагайдак, який не має зайвих стрілок. Тоді Q є діаграмою деякої скінченної частково впорядкованої множини S. Навпаки, діаграма Q(S) скінченної частково впорядкованої множини S є ациклічним простим сагайдаком, який не має зайвих стрілок.

Доведення. За наслідком 1.22 існує нумерація вершин сагайдака Q номерами {1 , …, t} така що i<j, коли є стрілка з і до j. Оскільки в Q немає зайвих стрілок, то існування стрілки вказує на те, що немає вершини k такої, що є шлях з точки і в точку k та з точки k в точку j. Звідси випливає, що Q є діаграмою частково впорядкованої множини своїх вершин. Обернене твердження доведено раніше. Таким чином, твердження доведене.

Теорема Перона 1.26. Додатна матриця A=(a_ij)M_n() завжди має дійсне і додатне характеристичне число r, що є простим коренем характеристичного рівняння й перевищує модулі інших характеристичних чисел. Цьому “максимальному” характеристичному числу r відповідає власний вектор z=(z₁, z₂,…, z_n) матриці A з додатними координатами z_i>0 (i=1, 2,…, n).

Додатна матриця є частковим випадком нерозкладної невід’ємної матриці. Фробеніус узагальнив теорему Перона, дослідивши спектральні властивості нерозкладних невід’ємних матриць.

Теорема Фробеніуса 1.27. Перестановочно незвідна невід’ємна матриця A=(a_ij)M_n() завжди має додатне характеристичне число r, що є простим коренем характеристичного рівняння. Модулі всіх інших характеристичних чисел не перевищують числа r. “Максимальному” характеристичному числу r відповідає власний вектор z c додатними координатами.

Якщо при цьому A має h характеристичних чисел ₀=r, ₁,…,_h-1, модулі яких дорівнюють r, то ці числа всі різні між собою і є коренями рівняння

^h- r^h=0,

і, взагалі, весь спектр ₀, ₁,..., _n-1 матриці A, який розглядається як система точок в комплексній площині, переходить сам у себе при повороті цієї площини на кут . При h>1 матриця A перестановочно еквівалентна матриці “циклічного” вигляду:

A= ,

де уздовж діагоналі знаходяться квадратні блоки.

Означення 1.28. Невід’ємна матриця PM_s() називається стохастичною матрицею, якщо для всіх i=1, …, s.

Означення 1.29. Невід’ємна матриця PM_s() називається двічі стохастичною матрицею, якщо для всіх i=1, …, s та для всіх j=1, …, s.