Строение обратимых матриц над упорядоченными алгебраическими системами тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

РГБ ОД

1 1 ОКТ Î233

Ильин Сергей Николаевич

СТРОЕНИЕ ОБРАТИМЫХ МАТРИЦ НАД УПОРЯДОЧЕННЫМИ АЛГЕБРАИЧЕСКИМИ СИСТЕМАМИ

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Казань — 1999

Работа выполнена в Казанском государственном педагогическом университете

Научный руководитель: кандидат физико-математических

наук, доцент Ю.А. Альпин

Официальные оппоненты: доктор физико-математических

наук, профессор Е.М. Вечтомов, кандидат физико-математических наук, доцент А.Б. Верёвкин

Ведущая организация: Саратовский государственный университет

Защита диссертации состоится "27" октября 1999 г. в 10 часов на за( Дании диссертационного совета К053.37.03 по защите диссертаций на < искание ученой степени кандидата физико-математических наук в Ул1 новском государственном университете (432700, Ульяновск, ауд.701 koj на Набережной р. Свияга).

С диссертацией можно ознакомиться в библиотеке Ульяновского гос дарственного университета.

Автореферат разослан "77" С t>t-t TJ 1QQ9 г.

Ученый секретарь У^/Г* Û Л диссертационного совета, доцент^» ч^Х^-ЬЩ/Ф*__JE.А. Ковалев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Исследования, проведенные в диссертации, можно отнести к двум областям современной алгебры.

Первое направление связано с теорией решеток. Матрицы над решетками находят применение во многих областях математики. Различным аспектам теории булевых матриц посвящена монография Кима1. Матричные уравнения с коэффициентами в решетках тесно связаны с задачами искусственного интеллекта2 и, в частности, используются в теории распознавания образов3. Различные свойства булевых матриц, в том числе и их обратимость, исследовались в работах Веддерберна, Рузерфорда, Люка и др. Полное описание обратимых матриц над ограниченными дистрибутивными решетками дано Скорняковым4. Матрицам над т -полурешетками с наибольшим элементом 1 и наименьшим элементом 0 посвящена статья Блиса5, а матрицам над квазибулевыми решетками — статья Салия6.

Другое направление связано с быстро развивающейся в последние десятилетия теорией полуколец, имеющей приложения в компьютерной математике, идемпотентном анализе. В частности, в рамках общей теории полуколец изучаются матричные полукольца. Однако, что касается результатов об обратимых матрицах над (не сводящимися к перечисленным выше решеткам) полукольцами, то за исключением известных элементарных свойств неотрицательных вещественных матриц, а также некоторых результатов о матрицах над полукольцами специального вида7 автору из-

1 Kim К.Н. Boolean matrix theory and applications. M. Dekker, New York, 1982.

2См. Сагмасеа С.К., Даленко М.Ш. Решение систем линейных уравнений с коэффи-диентамив решетках. Ч. 1. // НТИ. Сер. 2. Информационные процессии системы. 1992. 41. С. 11-19.

1 Гисин В.Б., Цалекко М.Ш. Алгебраическая теория систем и ее приложения // Системные исследования. Методологические проблемы. — М.: Наука, 1984, с. 130-151; 1985, :. 113-135.

4 Скорнгкоа Л.А. Обратимые матрицы над дистрибутивными структурами // Сиб. лат. журн. 1986. Т. 27, N2. С. 182-185.

5 BIyth Т. S. Matrices over ordered algebraic structures // Proc. London Math. Soc. 1364. /. 39. P. 429-431.

6 Салий В.И. О хвазибулевьгх решетках и хвазибулевых преобразованиях конечного лножества // Теория полугрупп и ее приложения. Вып. 7. Саратов. 1987. С. 71—76.

7 Масло в В.П., Колокольное В.Н. Идемпотентный анализ и его применения в опти-

вестна лишь статья Ройтенауэра и Страубинга8, посвященная обратимым матрицам над коммутативными полукольцами.

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

Цель работы. В работе рассматривается широкий класс упорядоченных алгебраических систем. Основные направления исследований следующие:

1. Описание обратимых матриц.

2. Связь между обратимостью матрицы и свойствами составляющих ее элементов.

Методы исследований. В диссертации используются понятия и методы теории упорядоченных алгебраических систем (группоидов, полугрупп, полуколец).

Основные результаты. Основные результаты работы заключаются в следующем:

1. Доказано, что полученное Скорняховым4 описание обратимых матриц над ограниченными дистрибутивными решетками справедливо (за исключением одного свойства) для матриц над рассмотренными в диссертации более общими упорядоченными алгебраическими системами при условии, что все элементы как самих матриц, так и обратных к ним, не превосходят элемент 1.

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

мальком управлении. Москва.: Наука, 1984.

8 Reutenauer Ch., Straubing Н. Inversion of matrices over a commutative semiring //J. Algebra. 1984. V. 88. N2. P. 350-360.

чтобы каждый элемент как самой, так и обратной к ней матрицы не превосходил некоторой суммы единиц.) Показано также, что при отсутствии данного (ослабленного) ограничения исследование обратимых матриц в общем случае весьма затруднительно.

3. Для менее обширного класса алгебраических систем (в которых умножение ассоциативно и любой элемент х удовлетворяет равенствам Ох = хО = 0 ) описано строение множества обратимых матриц при отсутствии ограничений на их элементы; сделан анализ качественных отличий матриц с различными видами обратимости.

4. В каждом из рассмотренных случаев дано описание множества элементов обратимых матриц.

Научная новизна. Все результаты являются новыми и получены автором лично.

Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные результаты могут быть использованы при дальнейших исследованиях свойств матриц над упорядоченными алгебраическими системами, в том числе, в общей теории полуколец (исследование матричных полуколец), в теории частично-упорядоченных множеств (решение матричных уравнений над различными обобщениями дистрибутивных решеток), а также при чтении спецкурсов на физико-математических факультетах университетов.

Апробация. Основные результаты докладывались на ежегодной студенческой конференции, организуемой механико-математическим факультетом МГУ (Москва, 1994), II Республиканской конференции молодых ученых и специалистов (Казань, 1996), конференции "Алгебра и анализ" (Казань, 1997), на алгебраическом семинаре проф. С.П.Мищенко в Ульяновском государственном университете, а также на алгебраических семинарах в Казанском государственном университете и Казанском государственном педагогическом университете.

Публикации. По теме диссертационного исследования опубликовано 5 работ, список которых приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, двух глав, каждая из которых разбита на два параграфа, и списка литературы. Объем диссертации — 94 страницы.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Под неассоциативным кольцоидом понимается такая алгебраическая система (72,+, •, 0,1), что (71, 4-, 0) —группоид с нейтральным элементом 0; (72,-, 1} — группоид с нейтральным элементом 1; выполняются законы дистрибутивности (х + у)г — хг + уг , х(у + г) — ху+хг и 0^1. Неассоциативный кольцоид 72 будем называть предполукольцом, если (72, +, 0} — коммутативный моноид, и полукольцом, если, кроме того, (72, •, 1) — моноид и Ох = жО = 0 для всех х Е 72. Неассоциативный кольцоид 72-, на котором задано отношение порядка < , положительно упорядочен, если 1) Ча £ 72. верно 0 < а и 2) V«, 6, с е 72 а < Ь влечет а + с < Ь + с, с + а < с + Ь, ас < Ьс и со <сЬ. Аналогично определяются положительно упорядоченные полукольцо и предполукольцо.

Пусть 72 — положительно упорядоченный неассоциативный кольцоид и Мп (71) — множество матриц порядка п над 72. Поскольку сложение и умножение в 72 необязательно коммутативны и ассоциативны, приходится корректировать понятия суммы и произведения элементов из 72, либо матриц над 72, а также другие понятия (см. ниже). Так, говоря о сумме, считаем, что способ ее вычисления (то есть порядок слагаемых и способ расстановки скобок) произвольным образом фиксирован. Для таких сумм используется знак ^ > обычный же знак суммирования употребляется в случаях, когда результат суммы не зависит от конкретного способа ее вычисления. Аналогично, говоря об умножении матриц, следует учитывать, что его результат зависит от способа вычисления каждого элемента, причем для различных элементов эти способы могут быть раз-

личными. Пусть А = ||а,,7|[ и В = ||Ьи-|| — матрицы порядка п над 71. Для каждой пары индексов (г, У) фиксируем какой-либо способ вычисления суммы с,^ = ^ацЬк] . Полученную таким образом матрицу С — ||с{; [| к

назовем *-произведением матриц А и В , а состоящее из всевозможных *-произведений множество АВ — произведением. (Имеются примеры произведений, состоящих из более, чем одной матрицы.) В случае, когда произведение содержит ровно одну матрицу, фигурные скобки в записи АВ = {С} в дальнейшем опускаются.

Назовем матрицу А € Мп(71) *-обратимой справа (слева), если найдется матрица В € М„ (71) такая, что Е € АВ (Е 6 В А ), где Е = Цд^-Ц — единичная матрица. Матрица А 6 Мп (71) *-обратима, если существует матрица В € Мп (72.), являющаяся одновременно и правой, и левой ^-обратной к А матрицей. Если же соответствующее произведение матриц А и В содержит только матрицу Е, будем говорить, что матрица А, соответственно, обратима справа, обратима слева, либо обратима.

Приведем понятие сильной обратимости, введенное Блисом5 для матриц над т -полурешетками с наибольшим элементом 1 и наименьшим элементом 0. Матрица А сильно обратима справа (слева), если найдется матрица В такая, что АВ — ВТАТ — Е (ВА = АТВТ = Е). Матрица сильно обратима, если она сильно обратима справа и слева. Определения одно- и двусторонней сильной *-обратимости матриц получаются заменой соответствующих равенств включениями.

Всюду в главе 1 71 — произвольный положительно упорядоченный неассоциативный кольцоид. Однако результаты этой главы, касающиеся обратимости матриц, получены в предположении, что все элементы как самих матриц, так и обратных к ним, не превосходят единицу кольцоида (параграф 1.1), либо не превосходят некоторой суммы единиц кольцоида (параграф 1.2). Основными результатами главы 1 являются теоремы 1.1.4, 1.1.5 и 1.2.2.

Зададим на кольцоиде 71 бинарное отношение по правилу: а <С Ь, если а не превосходит некоторой суммы элементов Ь. Отношение рефлексивно и транзитивно, то есть является отношением квазипорядка. По-

лагаем а ~ Ь, если о С ^ и 4 <С а. Доказано, что множество классов эквивалентности И = ^ является положительно упорядоченным пред-полукольцом, любые два элемента которого имеют точную верхнюю грань, совпадающую с их суммой. (Отметим, что аналогичное разбиение на архимедовы классы для изучения упорядоченных групп применял Лунстра9.) Используя свойства естественного гомоморфизма -ф : И, —> 0, (случай, когда И — полукольцо неотрицательных вещественных матриц, описан Биркгофом10), многие результаты, полученные автором первоначально для предполуколец с идемпотентным сложением, удалось распространить на случай положительно упорядоченных неассоциативных кольцоидов общего вида.

Обозначим через 0 = множество элементов, не превосходящих

единицу кольцоида 72.. Заметим, что этим свойством обладают элементы булевых алгебр, ограниченных дистрибутивных решеток, а также га -полурешеток, рассмотренных Блисом5, так что приведенные ниже результаты об обратимых над 5 матрицах являются обобщениями известных результатов о матрицах над перечисленными алгебраическими системами.

Назовем элемент а 6 И- т -дополнимым, если найдется элемент а' £ Л такой, что а о! — 1, аа' = а'а — 0. На множестве Б = В (Л) всех т -дополнимых элементов кольцоида И. корректно определяется бинарная операция " V ": а V Ь — аЬ + а'Ь +- аЬ'.

Теорема 1.1.2 V, 0,1} —булева алгебра.

Отметим, что для гп -полурешеток с наименьшим элементом 0 и наибольшим элементом 1 аналогичный результат был получен Блисом5.

Согласно терминологии из статьи Скорнякова4 матрица А — ||ау-||

называется ортогональной по строкам {столбцам), если ^а^ ~ 1

з

(^а}1 — 1) для всех г и а^а^ = 0 {ацйц- =0) при г ф к. Аналогич-э

ным образом (заменой " " на "3") определяется *-ортогональность по

эСм. Фукс Л. Частично упорядоченные алгебраические системы. Пер. с англ. М.: Мир, 1965. Стр.74.

10Бчркгоф Г. Теория решеток. Пер. с англ. М.: Наука, 1984. Стр. 441.

строкам (столбцам). *

Под N -степенью элемента из 72, либо матрицы над 72 понимается ^-произведение N одинаковых сомножителей, а под N -степенью — множество, состоящее из всевозможных N -степеней.

Каждой матрице А 6 Мп(72) соответствует совокупность {>р*А} отображений множества всех п -мерных строк с элементами из 72 в себя, каждое из которых сопоставляет строке (сц,..., с„) некоторое ^-произведение (а 1,.. .,ап)А . В случае, когда все отображения, соответствующие матрице А, совпадают друг с другом, применяется обозначение <рд .

Под скалярным *-произведением строк (хх,..., хп) и (у1,...,уп) ИО-

нимается сумма х,1ц.

¡=1

Обратимые матрицы над дистрибутивной решеткой Б с наибольшим и наименьшим элементами получили полное описание в следующей теореме Л.А.Скорнякова4:

Теорема 1.1.3 Следующие свойства матрицы А € МП(В) эквивалентны:

1) А обратима справа;

2) А обратима слева;

3) А обратима;

4) А ортогональна по строкам;

5) А ортогональна по столбцам;

6) А ортогональна по строкам и столбцам;

7) Ак = Е для некоторого N > 1;

8) отображение <рл взаимно однозначно;

9) отображение <рд сюръективно;

10) отображение инъективно;

11) отображение сохраняет скалярные произведения.

Поскольку ограниченная дистрибутивная решетка является частным случаем множества Я , в рассматриваемом нами более общем случае свойства I)—11) следует понимать как свойства матрицы, обратимой над С? . Допол-аим их следующими свойствами:

1*) А ^-обратима справа над Q;

2*) А *-обратима слева над Q ;

3*) А *-обратима над Q;

4*) А ^-ортогональна по строкам;

5*) А *-ортогональна по столбцам;

6*) А *-ортогональна по строкам и столбцам;

7*) Е € AN для некоторого N > 1;

8*) отображение <р*л¡ взаимнооднозначно;

1<г»

9*) отображение (р*А i сюръективно; le»

11*) отображение сохраняет скалярные ^-произведения.

Ii"

Теорема 1.1.4 Свойства 1)-9), 1*)~9*), 11) и 11*) матрицы А € Мп{б) эквивалентны. Любое из них влечет 10), но обратное неверно.

Из результатов Веддерберна11 и Рузерфорда12 вытекает эквивалентность условий 1)-6) в случае, когда Q — булева алгебра. Эквивалентность условий 4)-6) для матриц над квазибулевыми решетками установил Салий6, а для матриц над т -полурешетками с наименьшим элементом 0 и наибольшим элементом 1 — Блис5 . Заметим также, что из теоремы 1.1.4 непосредственно следуют доказанные Блисом5 эквивалентность одно- и двусторонней сильной обратимости матриц, единственность сильно обратной матрицы и совпадение ее с транспонированной матрицей.

Завершает параграф 1.1 обобщающая соответствующие результаты Скорнякова"1 и Блиса5

Теорема 1.1.5 Множество всех элементов матриц, обратимых над в(71), совпадает с множеством элементов булевой алгебры В{72.) .

Исследования, проведенные в параграфе 1.2, в основном посвящены вопросу о том, в какой мере описание обратимых над Q матриц остается

11 Wedderbwrn J.H.M. Boolean linear associative algebra // Ann. Math. 1934. V. 35. N1. P. 185-194.

12 Rutherford D.S. Inverses of Boolean matrices // Proc. Glasgow Math. Assoc. 1SS3. V. 6. N1. P. 49-53.

справедливым, если множество <? заменить существенно большим множеством 2 , состоящим из всех элементов, каждый из которых не превосходит некоторой суммы единиц кольцоида, и являющимся подкольцоидом кольцоида 72..

Пусть А € М„ (71). Введем обозначения: а,- = > а'~ ал для всех

г, <Иаз[а1,..., а„], Л^ггсИад^1,..., а"]. Если результат не зависит от конкретного способа суммирования, применяются обозначения а,- , а', и Л2 . Доказано, что одно- и двусторонняя ^-обратимость над 2 матриц эквивалентна, соответственно, их одно-, либо двусторонней обратимости над 2 (предложение 1.2.1). Строение обратимых над 2 матриц описывает следующее

Предложение 1.2.7 Матрица А обратима справа (обратима слева, обратима) над 2 тогда и только тогда, когда А = А-^И — С/А^, где матрицы и А2 обратимы справа (обратимы слева, обратимы) над 2, а матрица II ортогональна по строкам и столбцам.

Из данного предложения вытекает

Теорема 1.2.1 Множество всех элементов обратимых: (обратимых слева, обратимых справа) над 2 матриц является произведением множества всех обратимых (обратимых слева, обратимых справа) в Q элементов кольцоида 71 и множества элементов булевой алгебры В(7£) .

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

Теорема 1.2.2 Матрица А обратима справа (обратима слева, обратима) над 2 тогда и только тогда, когда найдутся кольцоиды 0.\ ,..., 2г

такие, что й = ¿Ь х ... х йг, А= ^А,, где Л,- = (Ai)•£,Ui = {/¡(Л,)2 £

¿=1

(Д-)е > — диагональные обратимые справа (обратимые

слева, обратимые) над й2- матрицы, 11( — матрица подстановок над <2, (¿ = 1,...,г).

Из приведенной теоремы вытекает (следствия 1-3), что выполнение любого из перечисленных выше свойств для элементов из 0, влечет справедливость аналогичного свойства и для матриц над 2 .

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

равенства АЕ — А, ЕА — А; матрица ^ ^ ^ ^ , где <1 — обратимый

элемент, может не быть даже односторонне обратимой).

Однако исследование обратимых матриц, элементы которых необязательно лежат в множествах 9 к О., оказалось возможным для менее обширного класса положительно упорядоченных кольцоидов, в которых а) умножение ассоциативно; б) для любого ж верно яО = Ож = 0. Изучению этого случая посвящена глава 2 .

В параграфе 2.1 принято еще одно допущение: элемент 1 является талией (иначе говоря, сравним с любым элементом) либо относительно порядка < , либо относительно квазипорядка . Этот подкласс кольцоидов не сводится полностью к рассматриваемому в параграфе 1.2 подклассу положительно упорядоченных неассоциативных кольцоидов, совпадающих с множеством Q , однако весьма к нему близок, так что описания обратимых матриц над кольцоидами из указанных подклассов оказываются во многом схожи.

Пусть 71 — положительно упорядоченный кольцоид, в котором элемент 1 является талией относительно порядка < (если 1 является талией относительно <С, в формулировках приводимых ниже результатов " 0 " следует заменить на "2").

Предложение 2.1.1 По крайней мере одно из включений Я С 71 и

{0,1} С В{%) является равенством множеств.

Таким образом, если кольцоид Л таков, что {0,1} С В(72.), то 0 ~ Л. Обратимые матрицы над кольцоидами такого вида описаны в главе 1. Поэтому имеет смысл рассматривать только такие кольцоиды, для которых О С Л и, следовательно, В (Л) = {0,1} . Доказано, что *-обратимость матриц над такими кольцоидами эквивалентна обычной обратимости. Строение обратимых матриц описывает следующее предложение.

Предложение 2.1.4 Матрица А Е М„(Л) обратима справа (обратима слева, обратима) тогда и только тогда, когда А = А%и — X] АР , где диагональные матрицы Ае и А? обратимы справа (обратимы слева, обратимы), а II — матрица подстановок.

Полное описание обратимых матриц над Л дают следующие две теоремы.

Теорема 2.1.1 Следующие свойства матрицы А <Е Мп(Л) эквивалентны:

1) А сильно обратима справа;

2) А сильно обратима слева;

3) А сильно обратима;

4) А обратима;

5) справедливо равенство А — А^М, где Аъ — обратимая матрица, а II — матрица подстановок;

6) справедливо равенство А = и АР , где Ар — обратимая матрица, а 1/ — матрица подстановок;

I) ААР — диагональная обратимая матрица;

8) Ар А — диагональная обратимая матрица;

9) А АР — обратимая матрица;

10) АР А — обратимая матрица;

II) А** — диагональная обратимая матрица для некоторого N > 1.

Теорема 2.1.2 Если в формулировке теоремы 2.1.1 отбросить свойства 1)-3) и заменить в свойствах \)~11) "обратимость" на "обратимость справа (слева)", то полученные свойства тоже будут эквивалентны.

Доказано также, что такие свойства, как отсутствие в % односторонне обратимых элементов и единственность односторонне обратного элемента наследуются множеством матриц над Т1 (теоремы 2.1.4 и 2.1.5).

В параграфе 2.2 рассматриваются кольцоиды в которых элемент 1 необязательно является талией. В этом случае детальное описание удалось получить лишь для сильно обратимых матриц, однако, имеются результаты и об обратимых матрицах. В частности, доказаны равенство правой и левой ^-обратных матриц и единственность ^-обратной матрицы (предложение 2.2.1 и следствие к нему), эквивалентность ^-обратимости и обратимости, а также то, что множество ^-обратимых матриц образует относительно умножения группу (следствия 1 и 2 к предложению 2.2.2). Центральными результатами главы 2 являются теоремы 2.2.1 и 2.2.2.

Теорема 2.2.1 Следующие свойства матрицы А 6 Мп(Л) эквивалентны:

1) А сильно (*-)обратима справа;

2) А сильно (*-)обратима слева;

3) А сильно (*-)обратима;

4) А? сильно (*-) обратима;

5) А односторонне (*-)обратима, А£ и А (Ле и А ) обратимы;

* *

6) справедливы равенства А = АеЕ/ — УА (А —А^и = УА ), где

* *

матрицы Ае и А2 ( Ае и А ) обратимы, а II и V ортогональны по строкам и столбцам;

7) одна из матриц А и АТ (*-)обратима, другая — односторонне (*-)обратима.

Найден также вид сильно обратной матрицы (предложение 2.2.5): А= ((Ах)~1А)Т(Аъ)-1 = (А2)-1 .

Теорема 2.2.2 Изображенный ниже ориентированный граф отражает связь между следующими свойствами матрицы А Е Мп(71) :

1) справедливо включение (Аи)2 € ААТ (справедливо равенство ААТ = (Ае)2 ), причем матрица Ля (Ац ) обратима;

2) справедливо включение (Ар)2ЕАтА (справедливо равенство АТА— (Л2)2 ), причем матрица А* (А2 ) обратима;

3) А сильно (*-)обратима;

4) справедливо равенство А—А^и (А=АаЕ/), где матрица Ах (Аз)

обратима, а матрица II ортогональна по строкам и столбцам;

* *

5) справедливо равенство А=УА (А=УА2), где матрица А (А2) обратима, а матрица 17 ортогональна по строкам и столбцам;

6) А (*-)обратпима;

7) при любом (при некотором) способе вычисления А" является диагональной обратимой матрицей для некоторого N > 1.

Наличие в графе пути, ведущего из вершины Г^г) в вершину означает справедливость импликации г) }), если же такой путь отсутствует, значит, данная импликация в общем случае неверна.

Пусть X = Х(72.) — множество всех обратимых элементов кольцоида 72..

Теорема 2.2.3 Множество всех элементов сильно обратимых матриц над 72 образует относительно операции умножения моноид, являющийся произведением группы. I и булевой алгебры Б, рассматриваемой как моноид.

С учетом равенства ХБ = Б2 (следствие к лемме 2.2.1) вполне очевидно, что элементами множества ХВ являются также все элементы матриц, обладающих свойством 4) или 5) из теоремы 2.2.2, однако для матриц, обладающих свойством 7) (а следовательно, и 6)), аналогичное утверждение в общем случае неверно.

Работы автора по теме диссертации

1. С.Н. Ильин Обратимость матриц над упорядоченными алгебраическими системами //II Республиканская научная конференция молодых ученых и специалистов. Казань, 1996, с. 11.

2. С.Н. Ильин Описание сильно обратимых матриц над полукольцами с идемпотентным сложением // Алгебра и анализ. Материалы конференции, посвященной 100-летию Б.М. Гагаева. Казань, 1997, с. 101-102.

3. C.B. Ильин Описание обратимых матриц над полукольцами с идемпотентным сложением // Международная алгебраическая конференция памяти проф. JI.M. Глускина. Славянск, 1997, с. 8.

4. С.Н. Ильин Описание ортогональных матриц над положительно упорядоченными полукольцами // Тезисы докладов на Международной алгебраической конференции памяти А.Г. Куроша. Москва, 1998, с. 177-178.

5. С.Н. Ильин Обратимость матриц над упорядоченными алгебраическими системами // Сиб. мат. журн. 1998. Т. 39, N 3, с. 551-559.

Введение

1 Обратимые матрицы над положительно упорядоченными неассоциативными кольцоидами

1.1 Описание матриц, обратимых над областью целостности кольцоида

1.2 Описание матриц, обратимых над областью квазицелостности кольцоида

2 Обратимость матриц над положительно упорядоченными кольцоидами

2.1 Обратимость матриц над кольцоидами, в которых элемент 1 является талией

2.2 Описание сильно обратимых матриц над кольцоидами общего вида

Известно, что многие вопросы в алгебре зачастую оказываются так или иначе связаными с матрицами, причем наряду с классическими вещественнозначными и комплекснозначными матрицами различные применения имеют, например, булевозначные матрицы, матрицы над решетками. Разумеется, при изучении матриц над различными алгебраическими системами далеко не последнее место отводится вопросу о их обратимости. Однако, в то время как свойства обратимых матриц над полями и кольцами иследуются достаточно давно, многие вопросы, касающиеся обратимости матриц над полукольцами и, в частности, упорядоченными алгебраическими системами, обладающими полукольцевой структурой (булевы алгебры, дистрибутивные решетки, т-полурешетки) либо были решены в течение последних 30-40 лет, либо остаются открытыми до настоящего времени.

Как известно, решетку Ь можно рассматривать как алгебраическую систему (Ь,и,П), в которой роль сложения и умножения элементов играют операции их объединения и пересечения, так что реше-точнозначные матрицы можно обычным образом складывать и умножать, используя сложение и умножение, имеющиеся в самой решетке. Особый интерес в этом отношении представляют ограниченные решетки, то есть решетки, обладающие наибольшим элементом 1 и наименьшим элементом 0, поскольку в этом случае матрица Е = играет роль единичной матрицы, а следовательно, имеет смысл говорить об обратимости матриц над такими решетками.

В первую очередь исследовались матрицы над булевыми алгебрами. По всей видимости, первой работой в данном направлении следует считать статью Веддерберна [1]. Исследуя различные свойства матриц с элементами в булевой алгебре, Веддерберн в частности получил необходимые и достаточные условия обратимости матрицы А — \\dij|| • и«ч = 1 (г = 1,. . ,п), (0.1)

3 = 1 а{]Пак] = 0 (г ф /г), (0.2) п и ау'1 ~ 1 (г = 1,.,п), (0.3) 1 а^Па^ = 0 (0.4)

Позднее Люк [2] показал, что булевозначная матрица А обратима тогда и только тогда, когда она ортогональна, то есть удовлетворяет равенству ААТ — Е, где Ат — матрица, транспонированная к матрице А, при этом Ат является обратной матрицей. Следующий важный шаг был сделан Рузерфордом [3]. Оказалось, что для булевозначной матрицы А условия {(0.1), (0.2)} эквивалентны условиям {(0.3), (0.4)}, так что для обратимости матрицы А необходимо и достаточно выполнения половины условий Веддерберна. В этой же статье Рузерфордом была установлена эквивалентность одно- и двусторонней обратимости булевозначной матрицы. Следует также отметить обзорные статьи Рудеану [4], Сагнаевой и Цаленко [5], затрагивающие те же вопросы.

После того, как были изучены свойства обратимых матриц над булевыми алгебрами, возник вопрос о распространении данных результатов на более широкие классы решеток. Значительный вклад в развитие этой темы был сделан Скорняковым [6]. Он дал полное описание (состоящее из 11 эквивалентных свойств, включая условия Веддерберна-Рузерфорда) обратимых матриц над ограниченными дистрибутивными решетками. Им же был установлен следующий факт: множество элементов обратимых матриц над ограниченной дистрибутивной решеткой образует булеву алгебру.

Другое обобщение результатов Веддерберна-Рузерфорда было сделано Б лисом [7]. Блис исследовал матрицы над упорядоченным группоидом с 0 и 1, образующим верхнюю полурешетку, для которой 0 и 1 являлись, соответственно, наименьшим и наибольшим элементами. Предполагалась также дистрибутивность имеющегося в группоиде умножения относительно операции объединения. Согласно терминологии из [8](с. 416,417) описанный упорядоченный группоид является ограниченной целостной т-полурешеткой. Ограниченную дистрибутивную решетку и, в том числе, булеву алгебру можно рассматривать как частный случай т-полурешетки, в которой умножение элементов совпадает с их пересечением. С учетом того, что умножение в т-полурешетке необязательно коммутативно, и следовательно, формула (АВ)Т — ВтАт, вообще говоря, перестает быть верной, Блис ввел понятие сильной обратимости матриц. Согласно [7] матрица А сильно обратима справа (слева), если найдется матрица В такая, что АВ = ВТАТ = Е (ВА — АТВТ = Е). Матрица А сильно обратима, если она сильно обратима слева и справа. Для матрицы над т-полурешеткой с наименьшим элементом 0 и наибольшим элементом 1 Блис доказал необходимость и достаточность условий Веддерберна-Рузерфорда для ее сильной обратимости, эквивалентность одно- и двусторонней сильной обратимости, единственность сильно обратной матрицы и совпадение ее с транспонированной матрицей, а также то, что элементы сильно обратимых матриц образуют булеву алгебру. Наконец, заканчивая обзор публикаций об обратимых матрицах над упорядоченными алгебраическими системами, следует также упомянуть о доказанной Салием [9] эквивалентности условий {(0.1), (0.2)} и {(0.3), (0.4)} Веддерберна-Рузерфорда для матриц над квазибулевыми решетками.

Обратимся теперь к матрицам над полукольцами. Под полукольцом понимается такая алгебраическая система {£,+,•, 0,1), что (¿>,+,0) — коммутативный моноид, (¿>,-,1) — моноид, выполняются законы дистрибутивности, Ох = х0 = 0 для всех х £ 5. Если умножение в £ необязательно ассоциативно, говорят, что S — неассоциативное полукольцо. Неассоциативное полукольцо, в котором нейтральный элемент по сложению 0 необязательно является мультипликативным нулем, будем для краткости называть предполуколъ-цом.

Легко видеть, что все перечисленные выше авторы (за исключением Салия) исследовали свойства обратимых матриц над упорядоченными множествами, которые могут рассматриваться как полукольца (у Блиса — неассоциативные полукольца) с идемпотентным сложением, каждый элемент х которых удовлетворяет равенствам

1 + ж = ж + 1 = 1.В последние годы активно изучаются и другие виды полуколец с идемпотентным сложением, в частности, имеются результаты об обратимых матрицах (см. [10]). Однако, в полученных результатах наблюдается явное сходство с известными элементарными свойствами обратимых матриц над полукольцом неотрицательных вещественных чисел (см. напр. [11] (стр. 592, зад. 9), а также [12] (стр. 155, зад. 4226)), несмотря на, казалось бы, различную природу этих алгебраических систем. Это позволило сделать предположение о том, что и те, и другие результаты вытекают из свойств алгебраических систем, обобщающих и полукольца с идемпотентным сложением, и полукольцо неотрицательных вещественных чисел. Таковыми являются, например, положительно упорядоченные (неассоциативные) полукольца. Однако полученные автором результаты справедливы и для более общих упорядоченных алгебраических систем, определяемых ниже.

Пусть 7Z — множество, на котором заданы бинарные операции сложения " + " и умножения "•", причем (7?,,+,0) — группоид с нейтральным элементом 0, -,1) — группоид с единицей 1, выполнены законы дистрибутивности и 0 / 1. Согласно терминологии из [13](с. 94, 96) 71 является не ассоциативным дистрибутивным кольцоидом с 1 над группоидом с 0 с необязательной дистрибутивностью умножения относительно нульарной операции (иначе говоря, нейтральный элемент по сложению необязательно является мультипликативным нулем). В дальнейшем, описанную выше алгебраическую систему будем для краткости называть неассоциативным кольцоидом. Неассоциативный кольцоид 7?-, на котором задано отношение порядка <, называется положительно упорядоченным, если 1) Уж £ 71 верно 0 < ж и 2) Уж, у, г £ Л х < у влечет х + г < у + г,

2 + х < г + у, хх < уг, гх < гу. В частности, если в положительно упорядоченном неассоциативном кольцоиде 71 сложение ассоциативно и коммутативно, то 71 — положительно упорядоченное предполу-кольцо, а если к тому же для всякого х Е 71 верно Ох = х0 = 0, то 71 — положительно упорядоченное неассоциативное полукольцо.

Возвращаясь теперь к сказанному выше, нетрудно видеть, что любое полукольцо 5 с идемпотентным сложением может быть положительно упорядочено, если для всех а, 6 Е <5 положить а < Ь тогда и только тогда, когда а + Ь = 6, при этом сумма элементов а и 6 является их точной верхней гранью относительно введенного порядка, положительная упорядоченность же полукольца неотрицательных вещественных чисел очевидна.

Разумеется, исследуя столь обширный класс алгебраических систем, целесообразно разбить его на более или менее крупные подклассы. В настоящей работе соответствующее разбиение класса всех положительно упорядоченных (неассоциативных) кольцоидов связано, во-первых, с введением естественных дополнительных ограничений, налагаемых на единицу кольцоида, и во-вторых, с требованием (либо отсутствием такового) ассоциативности умножения и выполнением условия, что нейтральный элемент по сложению является также мультипликативным нулем.

1. Маслов В.П., Колоколъцов В.Н. Идемпотентный анализ и его применения в оптимальном управлении. Москва.: Наука, 1984.

2. Хорн Р., Джонсон Ч. Матричный анализ. Пер. с англ. М.: Мир, 1989.

3. Сборник задач под редакцией А.И. Кострикина. М.: Факториал, 1995.

4. Курош А.Г. Общая алгебра (лекции 1969-70 учебного года). М.: Наука. 1974.

5. Фукс JI. Частично упорядоченные алгебраические системы. Пер. с англ. М.: Мир, 1965.

6. Reutenauer Ch., Straubing Н. Inversion of matrices over а commutative semiring. // J. Algebra. 1984. V. 88. N2. P. 350-360.Работы автора по теме диссертации

7. Ильин С.Н. Обратимость матриц над упорядоченными алгебраическими системами //II Республиканская конференция молодых ученых и специалистов. Казань, 1996. С. 11.

8. Ильин С.Н. Описание сильно обратимых матриц над полукольцами с идемпотентным сложением // Алгебра и анализ. Материалы конференции, посвященной 100-летию Б.М.Гагаева. Казань, 1997. С. 101-102.

9. Ильин С.Н. Описание обратимых матриц над полукольцами с идемпотентным сложением // Международная алгебраическая конференция памяти проф. JI.M. Глускина. Славянск, 1997. С. 8.

10. Ильин С.Н. Описание ортогональных матриц над положительно упорядоченными полукольцами // Тезисы докладов на Международной алгебраической конференции памяти А.Г. Куроша. Москва, 1998. С. 177-178.

11. Ильин С. Н. Обратимость матриц над упорядоченными алгебраическими системами // Сиб. мат. журн. 1998. Т. 39. N3. С. 551-559.