Определители булевых матриц и их приложения тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Поплавский, Владислав Брониславович

• Поплавский, Владислав Брониславович
• доктор физико-математических наук
• 2012

Оглавление диссертации доктор физико-математических наук Поплавский, Владислав Брониславович

Содержание

Введение

Исторический обзор и актуальность темы исследования

Структура работы

Апробация результатов

1 Перманенты и определители квадратных булевых матриц

Введение

1.1 Основные операции алгебры булевых матриц

1.2 Определители и перманенты булевых квадратных матриц

1.3 Некоторые свойства определителей

1.4 Перманенты и определители произведений булевых матриц

1.5 Двойственные перманенты и определители

2 Разложение определителей булевых матриц

Введение

2.1 Разложения булевой матрицы на внутреннюю, детерминантную и внешнюю части

2.2 Формулы Лапласа для перманентов булевых

матриц

2.3 Комбинаторные свойства внешних

и детерминантных булевых матриц

2.4 Формулы Лапласа для булевых матриц

с нулевой внутренностью

2.5 Разложения Лапласа и вырожденные матрицы

2.6 Разложения Лапласа для произвольных

квадратных булевых матриц

3 Обратимые и присоединенные булевы матрицы

Введение

3.1 Присоединенные булевы матрицы

и формула Лапласа

3.2 Обратимые булевы матрицы

3.3 Обратимость и разложения детерминантов

3.4 Формулы Крамера для систем линейных уравнений с обратимой квадратной

матрицей коэффициентов

3.5 Правые и левые действия группы обратимых

булевых матриц и перманентное разложение

4 Степени булевых матриц

Введение

4.1 Циклические полугруппы степеней булевой

квадратной матрицы

4.2 Некоторые свойства степеней булевой квадратной матрицы

4.3 Индексы и периоды обратимых булевых матриц

4.4 Максимальные индексы и периоды

4.5 Обертоны диагональных элементов степеней

4.6 Перманенты и определители степеней квадратной булевой матрицы

4.7 Перманенты и определители транзитивных

и рефлексивных булевых бинарных отношений

на конечном множестве и их степеней

5 Классы Грина, ранговые функции

и определители булевых матриц

Введение

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

5.2 Классы Грина частичной полугруппы

булевых матриц всевозможных размеров М(В)

5.3 Минорные и перманентные ранги

булевых матриц

5.4 Ранги и определители матриц частичной

полугруппы всех булевых матриц

5.5 Двойственные минорные ранги

5.6 Совместность матричных уравнений

5.7 Регулярность и ассоциативные формулы

дуальных произведений

5.8 Вторичные идемпотенты

5.9 Вторичные идемпотенты и классы Грина

5.10 Матричные идемпотенты и транзитивно-рефлексивные замыкания

6 Минорный ранг, нули определителя булевой матрицы и их приложения

Введение

6.1 SL-зависимость и ее свойства

6.2 О минорно-ранговых столбцах и строчках

булевой матрицы

6.3 Свойства матриц с нулевым определителем

6.4 Приложения к комбинаторике матриц

7 Приложения к матричным уравнениям и неравенствам

Введение

7.1 Минорные ранги и достаточные условия совместности простейших матричных уравнений

и неравенств над В2

7.2 Формулы Крамера для систем линейных неравенств с квадратной матрицей коэффициентов

Приложение

Литература

Публикации автора по теме диссертации

Введение диссертации (часть автореферата) на тему «Определители булевых матриц и их приложения»

Введение

Исторический обзор и актуальность темы исследования

Теория детерминантов, или определителей, возникла в результате поисков рациональных приёмов решения систем линейных уравнений над полями. Прежде чем определители и операции с ними обрели привычный для нас вид, они прошли долгий путь становления и развития. Для системы двух линейных уравнений с двумя неизвестными, записанной в виде

Г а\х + Ь\у = С\ \ а2х + Ъ2у = с2 '

решения можно представить в форме

С1&2 - С2&1 а\С2 - а2С1

х —-, у =-.

а1&2 — а2Ь1' а\Ъ2 — а2Ь\

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

Готфрид Вильгельм Лейбниц был первым, кто попытался сформулировать этот закон. В письме своему другу Гийому Франсуа Лопиталю от 28 апреля 1693 года [58], [36] он сообщает, что придумал (по сути, с помощью двух индексов) способ обозначения коэффициентов уравнений и может

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

Как указывает Вениамин Фёдорович Каган в предисловии к учебнику "Основания теории определителей"[28], ссылаясь на переписку Лейбница с Лопиталем, заслуга Лейбница заключается, в том, что он, во-первых, установил особый способ обозначения коэффициентов при неизвестных в уравнениях, во-вторых, показал, как из этих коэффициентов составляются отдельные члены общего знаменателя в выражениях для неизвестных, в-третьих, дал правило, которым определяется знак каждого члена. Своему открытию Лейбниц придавал большое значение. В последующих письмах к Лопиталю он неоднократно к нему возвращался. При этом открытие Лейбница оставалось неизвестным в течение 150 лет, вплоть до опубликования его переписки с Лопиталем в 1850 году (см. [36],[96], письма IV, VIII, XI, XII, XIII).

В 1750 г. швейцарский математик Габриэль Крамер опубликовал работу по теории алгебраических кривых [89]. В приложении к ней он дал правило составления общего знаменателя и числителей тех дробей, которыми выражаются значения неизвестных определенной системы линейных уравнений. Он также ввёл обозначение коэффициентов уравнений и правила составления членов общего знаменателя, определения знаков слагаемых, составляющих числители и знаменатели. На этот раз открытие обратило на себя внимание — во Франции во второй половине XVIII столетия правила Крамера вошли в программу государственных экзаменов rio алгебре.

Крамер занимался теорией решения систем линейных уравнений лишь применительно к изучению алгебраических кривых. Французский же математик Александр Теофил Вандермонд первый приступил к этому вопросу специально. В мемуаре [193], доложенном французской Академии наук в 1771 году, Вандермонд строит теорию многочленов, открытых Крамером для решения линейных уравнений. Лейбниц и Крамер начинали с установления особых обозначений для коэффициентов уравнений, Вандермонд первый ввёл схемы построения этих выражений, которые позже были заменены более удобными, но они сыграли свою роль. Он дал также правило рекуррентного составления формул ДЛЯ решений системы II линейных уравнений с п неизвестными по уже найденным решениям системы (п-1) уравнений с (п-1) неизвестными. Он установил правило знаков, обнаруживая, что каждое такое выражение имеет равное число положительных

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

Замечательными выражениями, открытыми Крамером и разработанными Вандермондом, воспользовались такие величайшие деятели математики, как Лаплас, Лагранж, Безу, Гаусс, Монж, Вронский и другие. Они применили метод Крамера — Вандермонда и показали, что эти замечательные алгебраические выражения весьма полезны в различных областях математических исследований и дают возможность выражать результаты в изящной форме. Лаплас ими пользуется в небесной механике, Лагранж — в теории вращательного движения, Безу — в общей теории алгебраических уравнений, Монж — в геометрических исследованиях. Появление определителей в работах таких выдающихся математиков естественно содействовало значительному их распространению в математической литературе.

Особое применение выражения Крамера — Вандермонда получили у Карла Фридриха Гаусса. Так, в 1798 году в знаменитых " Арифметических исследованиях " [95] он рассмотрел свойства квадратичных форм, в значительной мере зависящие от значений выражений, которые составляются из коэффициентов формы по тому же закону, что и выражения Крамера — Вандермонда. В современной терминологии они называются дискриминантами квадратичных форм. Гаусс же называет эти выражения "детерминантами", на русский язык этот термин переводится как "определители".

В 1812 году теория определителей вступила в новую фазу своего развития, благодаря работам выдающихся французских математиков Жака Филлипа Мари Бине и Огюстена Луи Коши. Получив схожие результаты (во избежание споров о приоритете), в один и тот же день (30 ноября 1812 года) в Институте Академии Франции они сделали доклады о своих исследованиях по теории детерминантов и опубликовали их в одновременно вышедших 16-й и 17-й тетрадях журнала Политехнической школы [67], [78]. В своих мемуарах Бине привёл некоторые тождества для перманентов

матриц размеров 2 хи, 3 хп, 4хп без доказательств и общих формул, а Коши ввёл понятие "перманента"как "перманентной симметрической функции". Примечательно, что рецензент ставит автору в упрек введение столь нелепого термина. Несмотря на то, что Гаусс и ранее называл дискриминант квадратичной формы "детерминантом"("определителем"), в широкое употребление этот термин ввёл Коши. Считается, что именно этот мемуар Коши дал новый толчок развитию теории определителей и перманентов.

При построении определителей Коши отталкивался не от проблемы формы записи решений системы линейных уравнений, а от знакопеременных (кососимметричных) функций нескольких переменных, и пришёл к уже известным результатам совершенно иным путём. "Не будет преувеличением сказать, — писал Томас Мюир в 1906 году в своём четырёхтомнике по истории теории определителей, — хотя это может показаться утрированным, что учебники по теории определителей, предназначенные студентам в настоящее время, то есть через сто лет, в сущности не содержат больше материала, чем знаменитый мемуар Коши"[153].

Заслуга Коши заключается в том, что он дал ряд приёмов, посредством которых можно вычислять значения определителей и производить над ними различные операции, не развёртывая их по правилу Крамера. Среди свойств определителей, обнаруженных Коши, важное место занимает правило умножения определителей, известное и Бине. Эта формула произведения определителей названа их именами. Сам Коши ещё в 14 мемуарах возвращается к определителям, внося дополнения и усовершенствования то в свои, то в исследования по теории определителей других авторов.

"Однако точная формулировка полилинейного свойства (детерминанта), пишут Ричард Бруальди и Ганс Шнейдер в своей замечательной статье, посвященной детерминантным тождествам и их истории [77], — появляется благодаря Шерку (1825), в то время как теорема о том, что прибавление одной строки, умноженной на число, к другой не изменяет определитель, по-видимому, не была сформулирована до третьих мемуаров Якоби в 1841 году".

Около 30 работ по общей теории определителей опубликовал замечательный германский математик Карл Густав Якоб Якоби (с 1827 по 1841 год). Из этих работ три наиболее замечательные относятся к последне-

му 1841 году [114]—[116]. Якоби сделал предметом особого исследования функциональные определители. Он устанавил правило дифференцирования таких определителей и основные приемы дифференциального исчисления применительно к определителям. Якоби ввёл определители особого типа, составленные из производных п функций от п независимых переменных для решения вопроса о зависимости функций. Эти замечательные определители вошли в историю математики как определители Якоби и стали обязательным инструментом в анализе бесконечно малых и теории функций.

Джордж Буль, не употребляя термины "определитель"и "перманент", однако, уделяет им часть статьи 1843 года [72].

В 1841 году Артур Кэли ввёл обозначение определителя в виде вертикальных линий. Позже, в 1845 году, отталкиваясь от исследований Гаусса, Коши и Якоби, он опубликовал весьма замечательную работу "О линейных преобразованиях" [79], в которой детерминанты получили дальнейшее развитие в качестве инвариантов линейных и квадратичных форм при линейных преобразованиях. Исследования преобразований и их инвариантов, проведенные Кэли в 10 работах с 1854 по 1878 год [80] и Джеймсом Джозефом Сильвестром [190], создали новое направление алгебры — теорию инвариантов алгебраических форм, или алгебру линейных преобразований. Произошло как бы слияние теории определителей и теории форм. Примечательно, что Сильвестр назвал теорию определителей "Алгеброй над алгеброй"("Algebra upon algebra").

Во второй половине XIX столетия уже трудно было найти те области математики, в которых не применялась бы теория определителей. Вопросами нахождения полного решения произвольной системы линейных уравнений занимался Леопольд Кронекер. Ему принадлежит заслуга исчерпывающего ответа на этот вопрос. Он был представлен им в форме лекций, прочитанных в осеннем семестре 1864 года и опубликованных Р. Бальце-ром в его книге по теории определителей [61]. Позднее эти рассуждения Кронекера были упрощены и углублены его учениками и последователями [130]. Кронекер и Вейерштрасс дали аксиоматическое определение детерминанта как кососимметрической функции, заданной на координатах п векторов п -мерного линейного пространства и нормированной на единичной матрице [7]. Большое внимание ученики Кронекера уделили также методам вычисления определителей. Метод автора небезызвестной "Али-

сы в стране чудес"Чарльза Доджсона и сегодня привлекает внимание и стимулирует поиск новых эффективных численных методов вычислений определителей (см. [41]).

Связь разрешимости алгебраических уравнений с совместностью бесконечных систем линейных уравнений с неограниченным числом неизвестных привела к появлению определителей бесконечного порядка. Обоснование этого метода дал Анри Пуанкаре [156]. Позже Эрик Ивар Фредгольм [94] ввёл функциональные определители бесконечного порядка, которые получили широкое применение в теории линейных интегральных уравнений.

В 1896 году Юлиус Вильгельм Рихард Дедекинд обратил внимание Фердинанда Георга Фробениуса на групповые определители, то есть определители матрицы , составленной из переменных, проиндексированных элементами 5 , £ из конечной группы [7]. Он указал на связь этих определителей с теорией характеров абелевых и некоммутативных групп. Вскоре Фробениус решил проблему разложения группового детерминанта на неприводимые множители, положив начало теории линейного представления групп.

История развития теории перманентов и их применений, начало которой положил Коши в 1812 году, не столь стремительна. В 1865 году Дж. Хорнер в работе, посвященной связи определителей с перманентами матриц 3-го порядка [110], назвал перманенты "контерминантами", а Дж. Хэмонд в 1879 году — "альтернирующими детерминантами"[106]. Сам термин "перманент"появился только в 1882 году в работе Томаса Мюира "О классе перманентных симметрических функций"[152], посвященной свойствам перманента, подобным свойствам определителя квадратных матриц (см. также [45]). Бурное продвижение теории перманентов, начиная с конца XIX века, связано, прежде всего, с работами Ф. Фробениуса и Д. Кёнига, посвящёнными целочисленным матрицам, и развитием прикладной матричной комбинаторики в XX веке (см., например, [45], [49] - [51], [56], [75]).

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

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

Особое внимание привлекает идея создания теории детерминантов матриц с элементами из некоммутативного кольца подобно теории детерминантов над полем или коммутативным кольцом. Первые попытки введения "некоммутативных"детерминантов для кватернионов сделал Кэли в 1845 году [81]. Далее, в основном в XX веке, с возникновением задач физики высоких энергий и теории элементарных частиц появились различные типы некоммутативных определителей: детерминанта Дьедонне, квантового детерминанта, детерминанта Капелли, Муди, Стади, Мура, Картье — Фо-ата, Березина, квазидетерминантов Гельфанда и Ретаха [13], [14], левых и правых кватернионных определителей Кирчея [29] и т.д. (см. обзорную статью [20]).

Последователи Дьедонне [91] ввели понятие детерминанта как гомоморфизма, определённого на группе обратимых квадратных матриц над телом в её факторгруппу по коммутанту, то есть как отображение, удовлетворяющее классической формуле Коши — Вине для определителей произведения квадратных матриц. Всякий гомоморфизм мультипликативной полугруппы квадратных матриц с элементами из некоторого кольца в некоторую коммутативную полугруппу с единицей, как показал Пони-зовский [46], можно рассматривать как определитель со свойствами аддитивности для строк и столбцов, левой однородностью для строк и правой однородностью для столбцов, обладающий в некотором смысле антиперестановочностью строк и столбцов, и позволяющий считать обратимость матрицы А эквивалентной условию ¿еЬА ф 0 .

Проблема построения некоммутативных определителей осложняется ещё и тем, что всякое стремление построить над кольцом К полилинейное относительно строк матрицы отображение с1еЬ \ Мпхп (К) К , которое имеет ядро, состоящее только из необратимых матриц, и некоторые другие свойства (см. [92]), неизбежно приводит к тому, что кольцо должно быть коммутативным.

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

прежде всего, от того, что не все элементы полукольца имеют аддитивные обратные.

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

По-видимому, первыми работами, в которых изучались булевы матрицы и исследовались системы линейных уравнений над булевыми алгебрами, были работы Лёвенгейма, появившиеся в начале прошлого века [148], [149]. Следующими заметными работами по булевым матрицам были работы Веддербёрна (1934 г. [195], [196]), Лунца (1950-1952 гг. [38], [39]), Вейландта (1950 г. [197]), Люца (1952 г. [150]), Рузерфорда (1963-1966 гг. [172] — [174]). Значительным событием в развитии теории стал выход монографии Кима по булевым (ОД)-матрицам и их приложениям в 1982 г. [121].

Жозеф Веддербёрн в 1934 году [195] ввёл понятие определителя квадратной матрицы с элементами из произвольной булевой алгебры через перманент новой матрицы, построенной особым образом с помощью булевых операций над элементами исходной матрицы. Равенство единице такого определителя булевой квадратной матрицы даёт признак обратимости этой матрицы. Однако он не обладает многими свойствами кольцевого детерминанта. Тем не менее, как показал Д. Хансен [107], всякий мультипликативный гомоморфизм на полугруппе квадратных булевых матриц со значениями в булевой алгебре всегда является функцией детерминанта

Веддербёрна.

В 1963 году О.Б. Соколовым в работе [54], посвященной матрицам, элементами которых являются формулы логики, ввёл определитель через симметрическую разность булевозначных величин:

0-GP+ аеР~

Здесь Р+ и Р~ обозначают все четные и нечетные подстановки соответственно. Эти величины естественно назвать полуперманентами, так как Per А = \А\+ + \А\~ . Такой определитель уже обладает некоторыми свойствами, похожими на свойства кольцевого определителя: он сохраняет значение при транспонировании, не меняется при перестановке строк, равен нулю, если строчки матрицы одинаковые. Более того, если строчки линейно зависимы, то определитель равен нулю. Однако обратное утверждение не выполняется в общем случае.

В 1969 году Д.С. Чесли и Ж.Х. Бэвис [85] рассмотрели "три типа определителей "квадратных матриц над решетками с дополнениями. Среди них определитель Веддербёрна, второй — Соколова, третий — перманент квадратной булевой матрицы. В 1972 году Ж. Кунцман [131] для матриц над коммутативными полукольцами употребил термин "бидетерминант", имея в виду рассмотренную выше пару полуперманентов (|А|+,|А|~) . Позже К. Реутенауэр и X. Страубинг [160] ввели термины положительного и отрицательного определителей матриц над коммутативным полукольцом, имея в виду эти же полуперманенты. Этой же терминологии придерживались Дж. Голан в известной монографии "Полукольца и их приложения"[98], а также Ф. Поплин и Р. Хартвиг в своей статье [157], посвященной свойствам таких определителей. Обзор проблемы классификации линейных отображений, сохраняющих матричные инварианты и, в частности, полуперманенты, можно найти, например, в [16].

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

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

тельно строк и столбцов в общем случае. Однако для такого детерминанта выполняется неравенство: ¿еЬАВ < • ¿еЬВ и некоторое неравенство, заменяющее по л и линейность относительно строк и столбцов. Это позволяет доказать, что введенный таким образом детерминант является инвариантом для квадратных матриц одного и того же размера, находящихся в одном и том же двустороннем главном идеале частичной полугруппе булевых матриц всевозможных размеров. Более того, оказывается, что такой определитель даёт возможность ввести понятие минорного ранга, аналогичного соответствующему понятию в теории над полем. Этот ранг также является инвариантом двусторонних главных идеалов в частичной полугруппе булевых матриц всевозможных размеров.

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

Несмотря на то, что теория булевых определителей является главной целью этой диссертации, многие её разделы посвящены общей теории матриц с элементами из произвольной булевой алгебры.

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

Структура работы

В первой главе рассматривается булева алгебра матриц одного и того же размера с элементами из некоторой произвольной булевой алгебры (Б, U, П/, 0,1) . Пусть (Bmxn, U, П/ , О, I) — булева алгебра т х п матриц с элементами из некоторой булевой алгебры (В, U, П/ , 0,1) . Операции объединения U , пересечения П , дополнения ' и, следовательно, отношение частичного порядка С определяются для матриц поэлементно. Нулем и единицей такой вторичной булевой алгебры служат матрицы О и / , образованные целиком из нулей 0 и единиц 1 соответственно.

Следующим образом вводится структура полумодуля булевых матриц одного размера над булевым полукольцом. Для матриц из Втхп объединение матриц АиВ = (AjUBlj) Е Втхп заменяет сложение, а пересечение матрицы Л П А = (Л П Л*-) € Втхп с элементом из булевой алгебры В -умножение на скаляр. Здесь Аи В.■ - элементы, стоящие в г -ой строчке и j -м столбце матриц А = (Л*-) и В = (В*) соответственно.

Кроме этого, множество всех матриц относительно конъюнктного произведения, определяемого для матриц Л = (Л*) 6 Вгпхп и В = (В*) (Е ВnXk согласованных размеров как матрица С = Л П В Е Вс элементами Cj = ULMl ^ Щ) > образует частичную полугруппу. Множество квадратных матриц Впхп относительно произведения образует решёточно упорядоченную полугруппу с единицей Е . Здесь Е - матрица, по главной диагонали которой стоят единицы, а на остальных местах - нули. Рассматриваются свойства операции конъюнктного Л П В произведения матриц АиВ подходящих размеров, а также дизъюнктного произведения Л U В , определяемого дуальным образом: (Л П В)' — A' U В' или

В §1.2 изучаются простейшие свойства полуперманентов и ориентированных детерминантов, определяемых следующим образом.

Определение. Ориентированные полуперманенты V Л, V Л п х п -матрицы Л (п > 2) с элементами Л*- из произвольной булевой алгебры (В, и, П/ , 0,1) определяются как

(Л U В)' = А' П В'.

+

+

(Л?1 П^2П...П А?)

И VA= IJ

(ai,...,an)eP

+

где через P и P обозначаются четные и нечетные п -подстановки верхних

индексов соответственно. Ориентированные полуперманенты позволяют

+

ввести перманент Per А —V AU V А и общую часть ориентированных

полуперманентов АА =V АГ\ V А . Правый и левый (ориентированные)

+ - +

определители определяются соответственно так: RDetA =V А\ V A =V

АП (V А)' и LDetA =V А\ V А = V А П (V А)'. Определителем булевых матриц называют булеву сумму правого и левого определителя: DetA = RDetA U LDetA .

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

Det

/■■ 4-1 Ul^n В}) .. \ /.. A)_x B\ A)+l .. \

: : : С (J [А4 П Det \ \

V- Ut=i(A4n Щ) A*+l ..) i=1 V - A-_x Bp ..)

xn

и следующая

Теорема 1.3.5. Пусть для некоторой квадратной матрицы А £ В„ существует такой набор каких-то, не обязательно выбираемых из матрицы А , столбцов £?2, Bnxi , что любой столбец А\, Ач,..., Ап £

ВПХ1 матрицы А является их линейной комбинацией. Тогда если к<п, то RDetA = LDetA = DetA = 0 .

Аналогичные утверждения справедливы для строк.

В §1.4 получены аналоги формул Бине - Коши (теорема 1.4.1), дающие следующие неравенства:

Рег(А П В) D Per А П РегВ, А(А П В) D ЛАП АВ, RDet(A П В) С (RDetA П RDetB) U (LDetA П LDetB), LDet{A П В) С (LDetA П RDetB) U (RDetA П LDetB),

Det(A ПВ)С DetA П DetB.

Формулы для полуперманентов произведения матриц с элементами из полукольца можно найти в работах [160], [98], [157].

Заметим, что из приведенных выше неравенств следует, что множество матриц, определяемое условием DetA — 0 , и которое можно назвать множеством вырожденных матриц, образует идеал. Также получаем, что множество неотрицательных матриц, определяемых условием LDetA = 0 , образуют подполугруппу в полугруппе квадратных булевых пхп -матриц с единицей Е .

Глава 2 посвящена проблеме разложения определителей по элементам

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

+

полуперманентов V А , V А и перманента Per А справедливы формулы Лапласа, дающие разложения по элементам строк или столбцов любой квадратной матрицы А над произвольным коммутативным полукольцом [98], [157], [172], [160]. Для правых RDetA , левых LDetA ориентированных определителей и определителя DetA формулы Лапласа неверны в общем случае.

Попытки определения условий, при которых разложения Лапласа таких определителей возможны, предпринимались и ранее. Авторы статьи [85] указывают некоторые условия справедливости разложения определителя по строке.

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

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

В главе 3 изучаются обратные матрицы в контексте определителей.

±

Вводятся ориентированные присоединенные матрицы аф А и указывается необходимый и достаточный признак обратимости булевой квадратной матрицы в следующей форме.

Теорема 3.2.4. Для булевой квадратной матрицы А существует обратная матрица А-1 тогда и только тогда, когда БеЬА — 1 и

+

(АП аф А) П (АП аф А) = О. Кроме того, обратная матрица равна объединению ее дизъюнктных ориентированных присоединенных матриц:

1 т + - +

А = А =аф Аи аф А, аф АП аф А = О.

Далее изучается разложимость определителя булевой матрицы по строкам или столбцам и её обратимость. Основная теорема §3.3 показывает связь проблемы обратимости булевых матриц и возможности разложения их определителей: Для квадратной булевой матрицы А существует обратная матрица тогда и только тогда, когда 1)е£А = 1 и для любых ее строк (или столбцов) выполняются формулы разложений (2.3) и формулы ложных разложений (3.8) её определителя.

Как некий аналог известных выражений для элементов обратных числовых матриц, в итоге получены формулы для элементов обратной булевой п х п -матрицы (теорема 3.4.1):

(А~1){ = РегЩА = Ве1д)А, (г,'] = 1,... ,п).

Тогда аналог классических формул Крамера для систем линейных уравнений даёт

Теорема 3.4.2. Система п линейных уравнений \Л=1{А\ П Хк) = В1 с п неизвестными {Хг ; г = 1, ...,п} ис обратимой матрицей коэффициентов А имеет единственное решение, которое можно найти но формуле

= РегА{в^]у

Символом А^в^Щ) г = 1,..., п обозначена матрица, полученная из квадратной булевой матрицы А заменой её г— го столбца столбцом В .

В §3.5 рассматривается подгруппа ипхп квадратных обратимых матриц в полугруппе всех квадратных булевых п х п -матриц относительно конъюнктного произведения. Левым и правым действием группы обратимых матриц ипхп на полугруппе Впхп называются отображения

LF : Unx„ x Bnxn ->> Вnxn и : Bnxn x Unxn Bnxn , которые определяются на элементах S Е Unxn и Л Е BnX7l как LF(S,A) = S П А и RF{S,A) = АП5.

Отображения LF , RF являются линейными по каждому аргументу. Более того, для некоторого S Е Uпхп отображения LFs и RF$ , определяемые на элементах равенствами LFs(A) = LF(S,A) = S П А и RFs(A) = RF(S,A) = Л П 5, являются линейными и обратимыми, так как Li7^1 = LFs-i и ÄF^ 1 — RF$-1 . Отображения LFs и RFs сохраняют вырожденную и детерминантную части данной матрицы. Кроме этого они сохраняют соответствующий тип вырожденности матрицы,

отображая внешность во внешность, а внутренность во внутренность. Ес-

+

ли же матрица S Е Unxn положительна, то есть S =S , что равносильно условию RDetS = 1, то LFs и RFs сохраняют ориентацию матриц при отображении, то есть положительные и отрицательные части переходят в положительные и отрицательные соответственно. Если же

матрица S Е Uпхп отрицательна, то есть S =S (выполняется условие LDetS = 1), то LFs и RFs меняют ориентацию на противоположную, переводя положительные и отрицательные части матрицы-прообраза в отрицательные и положительные части образа соответственно.

Всякое отображение Ф : М х М —> В упорядоченных пар элементов некоторого множества М в булеву алгебру В называется булевым бинарным отношением на множестве М . Ясно, что булево бинарное отношение является обобщением известного понятия "бинарное отношение", которое сводится к выбору двухэлементной булевой алгебры В2 = {0,1} . В случае конечности множества М его элементы можно пронумеровать натуральными числами от 1 до п . Тогда элементы булевой алгебры, которые ставятся в соответствие паре элементов из М с номерами inj (z,j = 1,...,п) образуют квадратную булеву матрицу А = (А*) . Совершенно ясно, что смена нумерации элементов в базовом множестве М приводит к одновременной перестановке строк и столбцов полученной матрицы. Таким образом, данное булево бинарное отношение определяет некоторую булеву матрицу А с точностью до таких перестановок.

Переставляя некоторым образом столбцы (или строки) в единичной матрице Е , получаем матрицу Р , которую естественно назвать перестановочной. Так как матрица РГ\А получается из матрицы А соответству-

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

Так как выполнено равенство Р П Рт = Е , то отношение

(А « В) <-> (3Р)(Р П А П Рт = В)

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

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

(РПАГ\Рт)к = РПАкПРт,

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

Назовем конечное множество М с заданным на нем булевым отношением, представляемым булевой матрицей А , конечной системой элементов с отношением А. Степень Ак булевой матрицы А порядка к представляет отношение, появляющееся в результате "наложения"или влияния отношения на себя, после его применения в этой системе к раз. Это, по-видимому, можно назвать результатом функционирования данной системы на к -ом шаге.

Наш интерес к изучению закономерности функционирования произвольных конечных систем обуславливается широким применением теории циклических полугрупп степеней булевых матриц (или теории асимптотических форм булевых матриц) в методологии тестирования, кластеринге (разбиении совокупности на группы), диффузии информации, в исследовании коммуникационных сетей, контактных схем, конечных автоматов, теории чисел, марковских процессов и пр. и пр. Это нашло место в социологии, биологии, медицине, физике и компьютерных науках. Широкий перечень таких примеров применения и соответствующей литературы можно найти в [121]. Этим объясняется и большое количество работ математиков по теории асимптотических форм для булевых матриц над алгеброй {0,1} , неотрицательных и нечетких матриц. На некоторые и важнейшие

на наш взгляд работы мы ссылаемся здесь (например, см. [38], [84], [87],

[90], [97], [101],[102], [111], [112], [117], [121], [124], [134], [135], [133], [137]-[147], [155], [162], [177]-[179], [181]-[184], [191], [192], [200]). Хороший обзор

этой проблемы можно найти в статье [135] и монографии [121].

В параграфах 1-5 главы 4 рассматриваются закономерности функционирования произвольных конечных систем и возникновение волн в таких системах. Оказывается, что функционирование конечных систем начинается с некоторого этапа вхождения в цикл (хаоса!) с последующим возникновением волн в таких системах или стационарного состояния, как частного случая волнового. Более того, такое вхождение и дальнейшее цитирование системы, называемой осциллятором, сопровождается появлением обертонов на главной диагонали степеней любой квадратной булевой матрицы. Здесь же указаны максимальные возможные значения показателя степени вхождения системы в цикл (циклическая глубина или индекс) и возможные значения длин этих циклов (периодов) для различных квадратных булевых матриц над произвольной булевой алгеброй. В §4.2 и §4.3 рассматриваются закономерности функционирования конечных систем с рефлексивными, обратимыми, нильпотентными и другими отношениями.

Теоремы 4.2.1 и 4.2.2 показывают, что среди рефлексивных и нильпо-тентных булевых бинарных отношений не найти отношений с максимальным индексом поскольку имеет место утверждение Шварца [179], указывающее возможный максимум для индекса произвольных булевых (или неотрицательных) (п х п )-матриц:

Вместе с тем, Вейландт [197] ранее доказал, что этот предел достигается примитивными матрицами тогда и только тогда, когда они определяют булевы отношения, задаваемые матрицами вида:

к

тах

(п - I)2 + 1

/ 0 1 о ... о о \ О 0 1 ... о о

пхп

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

В §4 проводится построение булевых отношений с максимальным индексом и периодом. Доказывается следующая

Теорема 4.4.1 Период булевой матрицы размера п х п над произвольной булевой алгеброй является делителем наименьшего общего кратного всех чисел от 1 до п .

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

Как показывает вычислительный эксперимент, результатам которого посвящен §4.5 и Приложение, указанное в конце работы, для малых размеров матриц поведение осцилляторов сопровождается появлением обертонов на главной диагонали степеней Ак , составляющих парные волны. В конце §4.5 указываются технические приложения подмеченного поведения осцилляторов.

В параграфах 4.6 и 4.7 рассмотрены свойства булевых бинарных отношений на конечном множестве в терминах перманентов и определителей. Основные результаты §4.6 для степеней булевых квадратных матриц сформулированы в теоремах 4.6.5 и 4.6.6.

Теорема 4.6.5. Для каждой квадратной булевой матрицы А имеет место цепочка включений

1 = ИегА0 Э ВегА Э ВеЬА2 ВегАк Э ....

Теорема 4.6.6. Для любой квадратной булевой матрицы А найдется такое натуральное число ко , не превосходящее индекса матрицы А , что для всех конъюнктных степеней их определители становятся постоянными, то есть ВеЬА8 = ВегАко , для всех в > ко .

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

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

Стоит отметить, что (0,1)— булевы матрицы (или бинарные отношения на конечном множестве) можно отнести лишь к одному из четырех типов (внутренние, внешние, положительные и отрицательные матрицы), определяемых выше. Матрицы над произвольной булевой алгеброй устроены сложнее. Тем не менее, как было уже сказано, любая из них естественным и единственным образом раскладывается в объединение четырех матриц, две из которых дают вырожденные части данной матрицы (внешний и внутренний тип), а другие две (положительный и отрицательный тип) — её ориентированные составляющие.

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

Теорема 4.7.1.Для любого транзитивного булева отношения на конечном множестве полуперманенты всех степеней этого отношения, начиная с первой, являются постоянными. Причем левые определители любого транзитивного отношения и его степеней равны нулю.

Теорема 4.7.2. Для полуперманентов любого рефлексивного булева

бинарного отношения на конечном множестве, состоящем из п элемен-

+ ,

тов, и степеней этого отношения выполняется V А= 1 для всех к =

0,1, 2,... и v А CV А2 С ... С V Аn_1 =V Ап = ... Следовательно, левые определители любого рефлексивного отношения и его степеней равны нулю, то есть все рефлексивного отношения являются неотрицательными булевыми отношениями.

Соотношения между различными ранговыми функциями для матриц над полукольцами, а также изменение их значений относительно операций с матрицами хорошо изучены (см. [4], [47], [64], [121], [180]).

В §5.1 изучаются столбцовые С (А) и строчные R(A) пространства булевой матрицы А произвольного размера. Известно, что булевы (0,1) -матрицы обладают единственным минимальным столбцовым (или строчным) базисом. Доказательство этого факта можно найти в ([121], теорема 1.1.1). По-видимому, это не происходит в общем случае при выборе других булевых алгебр, над которыми строится матричная алгебра. Однако, можно ввести понятия размерностей этих пространств или столбцовых (строчных рангов). Значения факторизационных рангов и столбцовых (строчных) связаны неравенствами:

rankf А < dimC(A) = rankcA, rankf A < dimR(A) = гапкцА.

Второй параграф посвящен изучению строения ассоциативной частичной полугруппы (М(В), П) булевых матриц всевозможных конечных размеров относительно операции конъюнктного произведения. Отношения двух матриц А и В , для которых столбцовые или строчные пространства одинаковы, очевидно, являются отношениями эквивалентности на (М(В),П). Обозначим их символами Ее и £r соответственно. Тогда ес(А) = {В е М(В) : С (В) = С(Л)} и eR(A) = {5е М(В) : R(B) = -ñ(A)} - соответствующие классы эквивалентности, порожденные элементом А .

Пересечение эквивалентностей £# = ее П er также является эквивалентностью, ее классы определяются условием ен{А) = {В Е М(В) : (С {В) = С (A)) A (R(B) = Д(Л))} = ЕС(А) П Er(A) .

Можно рассмотреть объединение бинарных отношений ес U er . Однако, объединение эквивалентностей в общем случае эквивалентностью не является, так как для него не выполняется условие транзитивности. Поэтому берем транзитивное замыкание объединения бинарных отношений eD = {J^^ec^er^ = ecVer , как минимальное транзитивное отношение, содержащее Ее и Er .

Справедливы следующие равенства (предложение 5.2.3):

ED = V ER — Ее • ER = ER - EQ ■

То, что булевы матрицы А и В из частичной полугруппы М(В) находятся в отношении ej , означает существование матриц U^UiiVuVi

подходящих размеров таких, что А = У\П В П С/1 и В = Уг П А П С/2 .

Очевидно, Е] является отношением эквивалентности. Кроме того, несложно показать, что С . На самом деле для булевых матриц частичной полугруппы (М(В),П) выполняется равенство = е,/, что аналогично известному результату из теории полугрупп, состоящему в том, что для устойчивых полугрупп, в частности, периодических полугрупп, классы Грина V и J совпадают ([34], гл. 2, §3).

Проведённое построение классов эквивалентностей , ее , , , на М(В) аналогично построению классов Грина И , 72., С , Т>, ^ для полугрупп соответственно, см. ([30]; гл. 2) и ([34]; гл. 2).

Мы доказываем, что факторизационные ранги, а также размерности строчных и столбцовых пространств матриц, являются инвариантами для такого £J -класса частичной полугруппы всевозможных булевых матриц М(В) (теоремы 5.2.1 и 5.2.2).

Новое понятие минорного ранга вводится в §5.3. Теорема 5.3.1 сравнивает значения перманентного и минорного рангов для произвольных булевых матриц:

гапкрегА > гапкА.

В §5.4 показывается, что определители всех квадратных матриц одного и того же размера равны, если они находятся в одном таком классе еJ частичной полугруппы всевозможных булевых матриц конечного размера М(В) (теорема 5.4.1). Кроме того, справедлива

Теорема 5.4.3. Минорный ранг произведения любых булевых матриц не превосходит минорных рангов сомножителей. Таким образом, минорные ранги всех матриц, находящихся в одном £J -классе частичной полугруппы всевозможных булевых матриц М(В) , равны.

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

тт(гапкв,А, гапксА) > rankfA > гапкА.

Основной результат этой главы, проясняющий роль определителя, сформулирован в теореме 5.4.4 и заключается в том, что в некотором £,/ -классе существует квадратная п х п -матрица с ненулевым определителем тогда

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

Параграфы 5.6 — 5.10 этой главы посвящены общей теории булевых матриц. Мы изучаем свойства алгебры (М(В),П,1_1) , в которой равенства А П (В U С) = (А П В) U С или A U (В П С) = (A U В) П С общем случае не выполняются. Оказывается, что выполнение таких равенств для некоторых матриц, то есть ассоциативность таких дуальных произведений, эквивалентна определенным свойствам этих булевых матриц.

Здесь исследуются признаки совместности простейших матричных уравнений. Показано, в частности, что если уравнение А П X = В совместно, то значение формулы A\lA'TL\B не зависит от расстановки в ней скобок, то есть она является ассоциативной.

Далее исследуется совместность уравнения вида А П X П В = С , что влечёт, в частности, равносильность регулярности булевой матрицы А и ассоциативности формулы А П А'т U A U А'т П А .

В последних параграфах этой главы изучаются свойства произведений А П А'т , А!т П А , Ат П А', А' П Ат , A U А'т , А'т U А , Ат U А', А! U Ат , входящих в формулы основных теорем предыдущих §5.6 и §5.7. Показано, что все они являются идемпотентами особого типа, названного вторичным, в соответствующих частичных полугруппах (М(В),1_1) и (М(В), П) . Доказывается также, что принадлежность матриц одному одностороннему главному идеалу частичной полугруппы булевых матриц всевозможных размеров влечёт совпадение их вторичных идемпотентов соответствующих типов. Кроме того, в терминах ассоциативности формул указывается необходимый и достаточный признак того, когда матрица и её соответствующий вторичный идемпотент находятся в одном одностороннем идеале частичной полугруппы всевозможных булевых матриц.

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

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

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

Задачи сохранения матричных свойств при преобразовании матриц с элементами из некоторого полукольца являются самыми широко представленными работами по этой теме в современной математической литературе (см., например, обзор [15]). Минорные ранги, как показано в главе 5, дают нижние оценки для строчных, столбцовых, факторизационных и перманентных рангов. Кроме того, минорные ранги являются инвариантами двусторонних идеалов частичной полугруппы булевых матриц всех размеров (М(В), П) . Однако в главе 6, в отличие от главы.5, рассматриваются иные преобразования матриц, которые также сохраняют минорные ранги.

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

§6.2 посвящен доказательству теорем, показывающих, как зависят столбцы (или строки) матриц от их минорно-ранговых столбцов, то есть аналоги теоремы "о базисном миноре"для матриц над полем.

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

о

единения А = Ли A UА соответственно внешней, детерминантной и внутренней частей. Они получаются, как пересечения А = {PerА)' П А ,

А= DetA П А , А = АА П А .

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

матриц по строке или столбцу (глава 3).

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

Множество вырожденных матриц, определяемое условием ВеЬА = О или условием А = АиА , образует идеал в полугруппе квадратных матриц относительно произведения матриц, что сразу следует из свойства определителя В^АПВ С Ве1АГ\ВеЬВ . Оказывается, все внутренние матрицы образуют подполугруппу в этом идеале. В §6.3 показано, в частности, что внешние матрицы образуют нижнюю полурешетку, а главные булевы идеалы, порожденные внешней матрицей, состоят из внешних матриц. Внутренности же образуют верхнюю полурешетку, которой принадлежат линейные комбинации и даже многочлены, построенные из всевозможных произведений внутренних матриц и их степеней с коэффициентами из булевой алгебры. Более того, множество всех внутренностей образуют полукольцо с аддитивной операцией и и мультипликативной операцией П . Все вышесказанное объясняет наш интерес к внешним и внутренним булевым матрицам.

В конце главы 6 указываются также приложения к комбинаторике матриц. Доказывается утверждение, которое является эквивалентом известной теоремы Фробениуса - Кёнига о (ОД)-матрицах с равным нулю перманентом, и которое сравнивает строение матрицы с нулевым перманентом со всеми матрицами, для которых перманенты отличны от нуля (теорема 6.4.1).

Далее в главе 7 мы рассматриваем приложения полученных в 6 главе результатов к матричным уравнениям и неравенствам, проблема разрешимости которых является весьма актуальной (см., например, монографии Рудяну ([164], гл. 6) и ([168], гл. 7, 15). Условия разрешимости некото-

рых типов матричных уравнений и неравенств сформулированы в §7.1 в терминах минорных рангов.

Несложно показать, что неравенство В С А П X , в котором А и В - булевы матрицы произвольного согласованного размера, может быть совместным или несовместным (пример 7.1.1), в отличие от матричного неравенства В ~Э А П X , которое как известно (см. [150],[168], а также предложение 6.4.1) эквивалентно неравенству X С (Ат)' U В , то есть всегда совместно. Аналогично, X \1 А С В -H- X С В U (Ат)'. Очевидно, это обобщает на булевы матрицы известную эквивалентность (Буль, Шрёдер) : а П х Ç b -п- ж С a' U 6 , которая справедлива для элементов а , 6 их произвольной булевой алгебры.

Таким образом, становится понятным наш интерес к проблеме разрешимости матричного неравенства В С АГ\Х . На эту проблему указывал также Р.Д. Люц, в своей работе, ставшей классической по теории булевых матриц [150]. Мы доказываем (теорема 7.1.3), что неравенство В С АПХ для булевой матрицы А и столбца В над булевой алгеброй В2 = {0,1} имеет решение, если столбец не увеличивает минорного ранга матрицы А . Это напоминает теорему Кронекера - Капелли для систем линейных уравнений над полями.

Далее доказывается теорема 7.1.4 о том, что совместность матричного уравнения А П X = В (или X П А = В ) над любой булевой алгеброй, всегда влечет равенство Кронекера - Капелли для минорных рангов вида гапк(А\В) = гапкА . Таким образом, то, что столбцы матрицы В , при их приписывании к столбцам матрицы А , не изменяют минорного ранга матрицы А является необходимым признаком совместности матричного уравнения АПХ-В (или X П А = В).

Здесь же доказывается следующее утверждение, касающееся проблемы разрешимости матричного неравенства такого же типа В С А П X , и которое является достаточно неожиданным и не имеющим аналогов в теории матриц над полем.

Теорема 7.1.5. Пусть А и В - булевы матрицы размеров m х п и тхк соответственной С - столбец размера тх 1 над — {0,1} такие, что система m линейных уравнений с п + к неизвестными, записанная в матричной форме как

(А П X) U {В П Y) = С,

имеет решение. Тогда, если столбцы матрицы В не увеличивают минорный ранг матрицы А , то матричное неравенство со столбцом неизвестных Ъ вида

с сАпг

имеет решение.

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

Апробация результатов

Результаты данной работы докладывались на следующих семинарах, конференция и школах.

1. 6-ая Междунар. конф. "Алгебра и теория чисел: современные проблемы и приложения", посвященной 100-летию Н.Г. Чудакова (Саратов, 13-17 сентября 2004г.).

2. 9-ая Азиатская конференция по логике. 16- 19.08.2005, Новосибирск, Россия.

3. Международная алгебраическая конференция, посвященная 100-летию П.Г. Конторовича и 70- летию Л.Н. Шеврина. 29 августа - 3 сентября 2005г., Екатеринбург, Россия.

4. Алгебраический семинар "Кольца и модули", МГУ ( 5.12.2005, 26.02.07)

5. IX Международная конференция "Интеллектуальные системы и компьютерные науки". МГУ, Москва, 23-27 октября 2006 г.

6. Международная конференция по алгебре и теории чисел, посвященная 80-летию В.Е.Воскресенского, 21-26 мая 2007 . Самара, Россия.

7. Международный алгебраический семинар. 17-22 сентября 2007 г., ВГПУ, Волгоград, Россия.

8. Международная алгебраическая конференция, посвященная 100-летию со дня рождения профессора А. Г. Куроша. 28 мая - 3 июня 2008 года. МГУ, Москва, Россия.

9. Международная научная конференция, посвященная 100-летию В.В. Вагнера. 5-7 ноября 2008 г., Саратов, Россия.

10. Международная научная конференция, посвященная 70-летию ректора МГУ академика В.А. Садовничего, "Современные проблемы математики, механики и их приложений". 30 марта- 02 апреля 2009 г. МГУ, Москва, Россия.

11. X Международный семинар "Дискретная математика и ее приложения". 1-6 февраля 2010г. МГУ, Москва, Россия.

12. Семинар профессора Васильева А.Ю. Института Математики университета Бергена (Норвегия), 26 июня 2010.

13. Международный алгебраический симпозиум, посвященный 80-летию кафедры высшей алгебры механико-математического факультета МГУ и 70-летию профессора А.В.Михалева, 15- 18 ноября 2010 г.

14. Международная конференция по алгебре и теории чисел, посвященная 190-летию П.Л. Чебышева и 120-летию И.М. Виноградова. Саратов, 12-17 сентября 2011г.

15. Международная математическая конференция, посвященная 70-летию профессора В. Кириченко. 13-19 июня, 2012г., Николаев, Украина.

16. 10-ая Международная конференция "Алгебра и теория чисел: современные проблемы и приложения "Волгоград, 10-16 сентября 2012г.

17. Ежегодные научные конференции по математике и механике СГУ, Саратов, 2005-2012г.г.

Список литературы диссертационного исследования доктор физико-математических наук Поплавский, Владислав Брониславович, 2012 год

Литература

[1] Артамонов В.А., Салий В.Н., Скорняков JI.A. Общая алгебра. М..-Наука, 1991. 480 с.

[2] Артин Э. Геометрическая алгебра. М.:Наука, 1969. 284 с.

[3] Алиева A.A. , Гутерман А.Э. Перестановочность ранга и аддитивные операторы, сохраняющие некоторые условия на ранг произведения// Фундаментальная и прикладная математика. 2004. Том 10, №4. С. 3— 14.

[4] Висли JI. Б., Гутерман А. Э., Йи С.-Ч. LP-проблемы для ранговых неравенств над полукольцами: граничные ранги// Фундаментальная и прикладная математика. 2004. Том 10, №2. С. 3- -21.

[5] Висли JL Б., Гутерман А. Э., Канг К.-Т., Сонг С.-З. Идемпотент-ные матрицы и мажорирование // Фундаментальная и прикладная математика. 2007. Том 13, №1. С. 11-29.

[6] Биркгоф Г. Теория структур. М.: Изд-во иностр. лит., 1952. 408 с.

[7] Н. Бурбаки. Очерки по истории математики. М.: Изд-во иностр. лит., 1963.

[8] Вагнер В.В. Теория отношений и алгебра частичных отображений// Теория полугрупп и ее приложения, Изд-во. Сарат. ун-та, 1965. 1. С.3-178.

[9] Владимиров Д.А. Булевы алгебры. М: Изд-во Наука, 1969. 320 с.

[10] Вайсман O.A., Гутерман А.Э. Факторизационный ранг для неотрицательных матриц // Чебышевский сборник. 2005. Т.6, вып.4. С.64—67.

[11] Гантмахер Ф.Р. Теория матриц. 4-е изд. М: Наука. 1988. 502 с.

[12] Гантмахер Ф.Р., Крейн М.Г. Осцилляционные матрицы и ядра и малые колебания механических систем. 2-е изд. М.: JL: Гос.Изд-во техн.-теор. лит. ,1950. 360с.

[13] Гельфанд И. М., Ретах В. С. Детерминанты матриц над некоммутативными кольцами // Функциональный анализ и его приложения, 1991. Т. 25, вып. 2. С. 13 -25.

[14] Гельфанд И. М., Ретах В. С. Теория некоммутативных детерминантов и характеристические функции графов // Функциональный анализ и его приложения,1993. Т. 26, вып. 4. С.1—20.

[15] Гутерман А.Э., Михалев A.B. Общая алгебра и линейные отображения, сохраняющие матричные инварианты // Фундаментальная и прикладная математика. 2003. Т. 9, №1. С. 83—101.

[16] Гутерман А.Э., Михалев A.B. Линейные отображения, сохраняющие матричные инварианты // Математика. Механика. Информатика: Тр. конф., посвящ. 10-летию РФФИ. М.: ФИЗМАТЛИТ, 2004. С. 165-186.

[17] Гутерман А.Э. Преобразования неотрицательных целочисленных матриц, сохраняющие определитель// Успехи математических наук. 2003. Т. 58, вып.6. С. 147-148.

[18] Гутерман А. Э. Линейные отображения, сохраняющие определитель Дьедонне над произвольным телом // Успехи математических наук. 2002. Т. 57, вып.4. С. 171-172 .

[19] Гутерман А.Э., Кузьма Б. Характеризация отображений, строго сохраняющих нули матричных многочленов// Успехи математических наук. 2008. Т. 63, вып. 59(383). С. 185-186.

[20] Дуплий С.А., Котульская О.И. Квазидетерминанты, некоммутативные детерминанты и необратимые суперматричные структуры// Вестник Харьковского национального университета. Сер. "Ядра,частники, поля". 2003. Т. 585, вып. 1.21 . С. 19-28.

[21] Егорычев Г. П. Дискретная математика. Перманенты: [учебное пособие] Сиб. федерал, ун-т, Политехи, ин-т. — Красноярск: СФУ, 2007. 272 с.

[22] Егорычев Г. П. (Egorychev G. P.) Explicit formula for determinants and its corollaries// Межд. конф. по теории колец, посвященная 90-летию со дня рождения А. И. Ширшова. Новосибирск, 14-18 июля 2011 г. Тезисы докладов. - Новосибирск: Институт математики им. С. JI. Соболева СО РАН, 2011. С.63.

[23] Елизаров В. П. Условия, необходимые для разрешимости системы линейных уравнений над кольцом // Дискретн. мат. 2004. Т.16, №2. С. 44-53.

[24] Закревский А.Д. Нахождение минимального дизъюнктивного базиса булевой матрицы // ДАН БССР. 1978. Т.22, №1. С. 39- 41.

[25] Зарецкий К.А. Регулярные элементы полугруппы бинарных отношений // Успехи математических наук. 1962. Т.17, вып. 3(105). С 177— 179.

[26] Зарецкий К.А. Абстрактная характеристика полугруппы всех бинарных отношений // Учен, записки Ленинградского гос. пед. института им. А.И. Герцена. 1958. Т. 183. С. 265-269.

[27] Зарецкий К.А.Абстрактная характеристика полугруппы всех рефлективных бинарных отношений// Учен, записки Ленинградского гос. пед. института им. А.И. Герцена. 1958. Т. 183. С. 251-263.

[28] Каган В.Ф. Основания теории определителей. Одесса: Гос. изд-во Укр. 1922. 522 с.

[29] Кирчей И.И. Правило Крамера для кватернионных систем линейных уравнений // Фундаментальная и прикладная математика. 2007. ТАЗ, №4. С. 67-94.

[30] Клиффорд А., Престон Г. Алгебраическая теория полугрупп: в 2т. М.:ММИРМ, 1972. Т.1. 287 е.; Т.2. 422 с.

[31] Кожухов И.Б., Ярошевич В.А. О потенциальной делимости матриц над дистрибутивными решетками // Дискретная математика. 2010. Т. 22, №2. С. 148-159.

[32] Копытцев В. А. О числе решений систем линейных булевых уравнений в множестве векторов, обладающих заданным числом единиц // Дискретная математика. 2002. Т. 14, №4. С. 87-109.

[33] Кумаров В.Б. Решетка идемпотентных матриц над дистрибутивными решетками // Фундаментальная и прикладная математика. 2007. Т. 13, вып.4. С. 121-144.

[34] Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: "Мир", 1985. 440 с.

[35] Ланкастер П. Теория матриц. М.: "Наука", 1982. 272 с.

[36] Лейбниц Г.В. Избранные отрывки из математических сочинений/ Пер. А.П.Юшкевича // Успехи математических наук. 1948. Т. 3, вып. 1. С. 165-204.

[37] Леонтьев И.К., Тоноян Г.П. Приближенное решение систем булевых уравнений // Вычисл. мат. и мат.-физ. 1993. Т.ЗЗ, №9. С. 1383—1390.

[38] Лунц А.Г. Приложение матричной булевской алгебры к анализу и синтезу релейно - контактных схем// Докл. Акад. наук СССР. 1950. Т. 70, №3. С. 421-423.

[39] Лунц А.Г. Алгебраические методы анализа и синтеза контактных схем// Изв. АН СССР. Сер. Математика. 1952. 16., С. 405-426.

[40] Мальцев А.И. Алгебраические системы. М.: Наука, 1970. 432с.

[41] Малашонок Г. И. Алгоритмы вычисления определителей в коммутативных кольцах// Дискретная математика. 1995. Т. 7,№4. С. 68—76.

[42] Маренич Е. Е. Факторизация (ОД)-булевых матриц// Фундаментальная и прикладная математика. 2008. Т. 14,№5. С. 155—164.

[43] Маренич Е.Е., Кумаров В.Г. Обратимые матрицы над решетками с псевдодополнениями// Фундаментальная и прикладная математика. 2005. Т. И, №3. С.139-154.

[44] Маркус М. Минк X. Обзор по теории матриц и матричных неравенств. М.: Едиториал УРСС, 2004. 232 с.

[45] Минк X. Перманенты. (Перевод с английского В.Е. Тараканова). М.: Изд. "МИР". 1982. 212с.

[46] Понизовский И.С. Об определителе матриц с элементами из некоторого кольца // Мат. сборник. 1958. Т.45(87), N 1. С. 3-16.

[47] Пшеницына O.A. Факторизационный и граничный ранги матричного объединения над полукольцом// Фундаментальная и прикладная математика. 2003. Т. 9, №3. С. 175-197.

[48 [49

[50

51

[52 [53

[54

[55 [56

[57

[58

[59 [60 [61

Райзер Г.Дж. Комбинаторная математика. М.: МИР, 1966. 156с.

Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: "Наука", 1982. 384 с.

Сачков В.Н. Комбинаторные методы дискретной математики. М.: "Наука",1977. 320 с.

Сачков В.Н., Тараканов В.Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000. 448 с.

Сикорский Р. Булевы алгебры. М.:Изд-во "МИР", 1969. 376 с.

Скорняков JI.A. Обратимые матрицы над дистрибутивными структурами// Сибирский мат. жур. 1986. Т. XXVII, N2. С. 182-185.

Соколов О.Б. Применение булевых определителей к анализу логических многополюсников. // Учен.записки Казанского госуниверситета. 1963. Т. 123, кн. 6. С. 155—164.

Спивак М.А. Введение в абстрактную теорию автоматов. Саратов: Изд-во Сарат. ун-та, 1970. 112с.

Тараканов В.Е. Комбинаторные задачи и (0,1)-матрицы. М.: "Наука", 1985. 192с.

Харари Ф. Теория графов. М.: Изд-во. "Мир". 1973. 300с.

Хрестоматия по истории математики/ Под ред. А.П.Юшкевича. М.: Просвещение, 1976.

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

Шайн Б.М. Представление полугрупп при помощи бинарных отношений// Мат. сб. 1963. Т.60(102), №3. С. 293-303.

Baltzer R. Theorie und Anwendung der Determinanten. BiblioLife, 2009. ISBN 1103131044. 292p.

Bapat R.B. Outer inverses: Jacobi type identities and nullities of submatrices// Linear Algebra Appl. 2003. V.361. P. 107-120.

Beasley L.B.; Guterman A.E.; Lee S.-G.; Song S.-Z. Linear preservers of zeros of matrix polynomials// Linear Algebra Appl. 2005. V.401. P.325— 340.

Beasley L.B.; Guterman A.E. Rank inequalities over semirings // J. Korean Math. Soc. 2005. V. 42, №.2. P.223-241.

Beasley L.B.; Guterman A.E.; Lee S.-G.; Song S.-Z. Linear transformations preserving the Grassmannian over // Linear

Algebra Appl. 2004. V.393. P.39-46.

Beasley L.B.; Song S.-Z.; Kang K.-T.; Sarma B.K. Column ranks and their preservers over nonnegative real matrices// Linear Algebra Appl. 2005. V.399. P.3-16.

Binet J.P.M. Mémoire sur un système de formules analytiques, et leur application a des considérations géométriques// J. de l'École Polytechnique. 1812. 9 , Cah. 16. P.280-302.

Blyth T. S. (Thomas Scott) Residuation theory and Boolean matrices// Proc. Glasg. Math. Assoc. 1964. 6. P. 185-190.

Blyth T. S. (Thomas Scott) The general form of residuated algebraic structures// Bull. Soc. Math. France. 1965. 93. P.109-127.

Blyth T.S. A-distributive Boolean matrices// Proc. Glasg. Math. Assoc.

1965. 7. P.93-100.

Blyth T.S. On eigenvectors of Boolean matrices// Proc. R. Soc. Edinb.

1966. Sect. A 67. P.196-204.

Bool G. On the transformation of multiple integrals// Cambridge Math. J. 1843. 4. P.20-28.

Breen M.; Hume D. On the cardinalities of row spaces of Boolean matrices// Semigroup Forum. 2001. V.62, No.2. P.331-332.

Breen M.; Hume D. Properties of a standard form for a Boolean matrix// Linear Algebra Appl. 1997. V.254. P.49-65.

Brualdi R.A.; Ryser H.J. Combinatorial matrix theory. Encyclopedia of Mathematics and Its Applications. 39. Cambridge etc.: Cambridge University Press. 1991. ix, 367p.

Brualdi R. A.; Liu B. Hall exponents of Boolean matrices// Czech. Math. J. 1990. 40(115), No.4. P.G59-670.

Brualdi R.A.; Schneider H. Determinantal identities: Gauss, Schur, Cauchy, Sylvester, Kronecker, Jacobi, Binet, Laplace, Muir, and Cayley// Linear Algebra and Its Application. 1983. 52/53. P.769-791.

Cauchy A.L. Mémoire sur les functions qui ne peuvent obtenir qui deux valeurs égales et de signes contraires par suit des transpositions opérées entre les variables qu'elles renferment //de l'Ecole Polytechnique. 1812. 10. Cah. 17. P.29-112.

Cayley A. On linear transformations// The Cambrige Mathematical Journal. 1845. IV.

Cayley A. Memoirs upon Quantics// Philosophical Transactions of the Royal Society of London. Volumes 144,146,148,149,151,157,161,169 (1854 - 1878).

Cayley A. On certain results relating to quaternions// Phil. Mag. 1845. V. 26. P.141—145.

Chaudhuri R.; Mukherjea A. Idempotent Boolean matrices// Semigroup Forum. 1980. 21. P.273-282.

Chen W-K. Boolean matrices and switching nets// Math. Mag. 1966. 39. P.l-8.

Chen X.; Zhang K. The upper bounds of the generalized maximum density index of irreducible Boolean matrices// Linear Algebra Appl. 1997. 256. P.75-93.

Chesley D.S.; Bevis J.H. Determinants for matrices over lattices// Proc. Roy. Soc. Edinburgh. 1969. A 68, 2. P.138-144.

Cho H.H. Prime Boolean matrices and factorizations// Linear Algebra Appl. 1993. 190. P.87-98.

[87] Cho H.H. Indices of irreducible Boolean matrices// J. Korean Math. Soc. 1993. 30, No.2. P.267—274.

[88] Cho H.H. Permanents of prime Boolean matrices// Bull. Korean Math. Soc. 1998. 35, No.3. P.605-613.

[89] Cramer I. Introduction a l'Analyse des Lignes Courbes algebriques. Geneve, 1750.

[90] Daode H. On circulant Boolean matrices// Linear Algebra Appl. 1990. 136. P. 107-117.

[91] Dieudonne' J. Les determinants sur un corps noncommutatiff// Bul. Soc. Math. France. 1943. V. 71. P.27-45.

[92] Dyson F. Quaternion determinants// Helv. Phys. Acta. 1972. 45. P.289-302.

[93] Flegg H.G. Boolean algebra and its application including Boolean matrix algebra. London-Glasgow: Blackie & Son Ltd. 1964 . XV, 261 p.

[94] Fredholm A. Sur une classe d'équations fonctionelles// Acta Mathematica, 1903.

[95] Gauss C. F. Disquisitiones Arithmeticae. Leipzig, 1801.

[96] Gerhardt C. I. Leibnizens mathematische Schriften. 2 Bd. Berlin, 1850.

[97] Give'on Y. Lattice matrices// Inform. And Control. 1964. 7 , §4 . P.477-484.

[98] Golan J.S. Semirings and their Applications. Dordrecht: Kluwer Academic Publishers. 1999. xi, 381p.

[99] Golan J.S. Semirings and affine equations over them: theory and applications. Kluwer Academic Publishers. 2003. xi, 244p.

[100] Glazek K. A guide to the literature on semirings and their applications in mathematics and information sciences. With complete bibliography. (English) Dordrecht: Kluwer Academic Publishers. 2002. viii, 392p.

[101] Gregory D.A.; Kirkland S.; Pullman N.J. Power convergent Boolean matrices// Linear Algebra Appl. 1993. 179. P.105-117.

102] Gregory D.A.; Kirkland S.J.; Pullman N.J. A bound on the exponent of a primitive matrix using Boolean rank// Linear Algebra Appl. 1995. 217. P.101 116.

103] Gregory D.A.; Pullman N.J. Semiring rank: Boolean rank and nonnegative rank factorizations// J. Comb. Inf. Syst. Sci. 1983. 8. P.223— 233.

104] Gregory D.A.; Pullman N.J.; Kirkland S.J. On the dimension of the algebra generated by a Boolean matrix// Linear Multilinear Algebra. 1994. 38, No.1-2. P.131-144.

105] Hammer P.L.; Rudeanu S. Boolean methods in operations research and related areas. Berlin - Heidelberg - New York, Springer, 1968. XV, 329 p.

106] Hammond J. Questtion 6001// Educ. Times. 1879. 32. P. 179.

107] Hansen D.J. Cauchy's multiplicative functional equation in the semigroup of Boolean matrices// Rev. Roum. Math. Pures Appl. 1984. 29. P.313—318.

108] Hong S. Distribution of cardinalities of row spaces of Boolean matrices of order n // Southeast Asian Bull. Math. 2000. 24, No.l. P.51-64.

109] Hong S. Gaps in the cardinalities of row spaces of Boolean matrices// Semigroup Forum. 1998. 56, No.2. P. 158-186.

110] Horner J. Notes on determinants// Quart. J. Math. 1865. 8. P.157-162.

111] Huang W. Matrices which belong to an idempotent in a sandwich semigroup of circulant Boolean matrices// Linear Algebra Appl. 1996. 249. P.157—167.

112] Huang W. On the sandwich semigroups of circulant Boolean matrices// Linear Algebra Appl. 1993. 179. P. 135-160.

113] Hwang S.-G.; Kim, S.-J.; Song, S.-Z. Linear operators that preserve maximal column rank of Boolean matrices// Linear Multilinear Algebra. 1994. 36, No.4. P.305—313.

114] Jacobi C.G. De formatione et proprietatibus Determinantium// Journal fur reine und angewandte Mathematik. Bd. XXII. 1841.

115] Jacobi C.G. De determinantibus functionalibus// Journal für reine und angewandte Mathematik. Bd. XXII. 1841.

116] Jacobi C.G. De funetionibus alternantibus earumque divisione per produetum e differentiis elementorum conflatum// Journal für reine und angewandte Mathematik. Bd. XXII. 1841.

117] Jiang Z. On the indices of convergence of reducible Boolean matrices with the generalized period// Linear Algebra Appl. 1996. 248. P.355—374.

118] Kenig D. Theorie der endlichen und unendlichen Graphen. Leipzig, 1936.

119] Kenig D. Graphok es matrixok. Mat. Fiz. Lapok. 1931. 38. P.116—119.

120] Kim J.B. Boolean matrix representations of final choice functions// J. Fuzzy Math. 1995. 3, No.2. P.365-372.

121] Kim K.H. Boolean matrix theory and applications. Pure and Applied Mathematics, 70. New York - Basel: Marcel Dekker, Inc. 1982. XIV, 425p.

122] Kim, K.H.; Roush, F.W. Strong shift equivalence of Boolean and positive rational matrices// Linear Algebra Appl. 1992. 161. P.153—164.

123] Kirn K.H.; Roush F.W. The algebraic structure of the semigroup of binary relations on a finite set// Glasg. Math. J. 1981. 22. P.57—68.

124] Kim K.H.; Schwarz S. The semigroup of circulant Boolean matrices// Czech. Math. J. 1976. 26(101). P.632-635.

125] Kirkland S.; Pullman N.J. Boolean spectral theory// Linear Algebra Appl. 1992. 175. P.177-190.

126] Kirkland S.; Pullman N.J. Linear operators preserving invariants of nonbinary Boolean matrices// Linear Multilinear Algebra. 1993. 33, No.3/4. P.295-300.

127] Konieczny J. On cardinalities of row spaces of Boolean matrices// Semigroup Forum. 1992. 44, No.3. P.393-402.

128] Konieczny J. Reduced idempotents in the semigroup of Boolean matrices// J. Symb. Comput. 1995. 20, No.4. P.471-482.

129] Konieczny J. The semigroup generated by regular Boolean matrices// Southeast Asian Bull. Math. 2002. 25, No.4. P.627—641.

130] Kronecker L. Vorlesungen uber die Theorie der Determinanten. Leipzig, 1903.

131] Kuntzmann J. Théorie des réseaux (graphes). Dunod, Paris, 1972.

132] Li Ch.; Yu H. Intervals of gaps on cardinalities of Boolean matrices// Math. Appl. 1998. 11, No.4. P.114-116.

133] Li J. Periodicity of powers of fuzzy matrices (finite fuzzy relations)// Fuzzy Sets Syst. 1992. 48, No.3. P.365-369.

134] Li Q.; Shao J. On the powers of Boolean matrices// Appl. Math., J. Chin. Univ. 1988. 3, No.2. P.186-199.

135] Li Q.; Shao J. The index set problem for Boolean (or nonnegative) matrices// Discrete Math. 1993. 123, No.1-3. P. 75- 92.

136] Li W.; Zhang M.-C. On Konieczny's conjecture of Boolean matrices// Semigroup Forum. 1995. 50, No.l. P.37—58.

137] Liu B. k-common consequents in Boolean matrices// Czech. Math. J. 1996. 46, No.3. P.523—536.

138] Liu B. Generalized exponents of Boolean matrices// Linear Algebra Appl. 2003. 373. P.169 182.

139] Liu B. On exponent of indecomposability for primitive Boolean matrices// Linear Algebra Appl. 1999. 298, No.1-3. P. 1—8.

140] Liu B. On fully indecomposable exponent for primitive Boolean matrices with symmetric ones// Linear Multilinear Algebra. 1992. 31, No.1-4. P.131—138.

141] Liu B. On the index of convergence for imprimitive Boolean matrices// Southeast Asian Bull Math. 1994. 18, No.l. P.89-95.

142] Liu B.; Bo Z. On the Hall exponents of Boolean matrices// Linear Multilinear Algebra. 1999. 46, No.3. P.165-175.

143] Liu B.; Bo Z.; Li Q.; Shen J. Generalized index of Boolean matrices// Ars Comb. 2000. 57. P.247-255.

144] Liu B.; Li Q. Estimation of convergence exponents of Boolean matrices with postive symmetric elements on exactly t rows// Acta Math. Appl. Sin. 1995. 18, No.4. P.549-558.

145] Liu B.; Li Q. Exact upper bound of convergence index for Boolean matrices with non-zero trace// Adv. Math., Beijing. 1994. 23, No.4. P.331—335.

146] Liu B.; Shao J. The index of convergence of Boolean matrices with nonzero trace// Adv. Math., Beijing. 1994. 23, No.4. P.322-330.

147] Liu B.; Zhou B.; Li Q. The generalized indices of convergence of Boolean matrices with non-zero trace// Acta Math. Appl. Sin. 1999. 22, No.4. P.574 -578.

148] Lôwenheim L. Ûber Transformationen im Gebietekalkôl// Math. Ann. 1913. 73. P.245—272.

149] Lôwenheim L. Gebietdeterminanten// Math. Ann. 1919. 79. P.223-236.

150] Luce R.D. A note on Boolean matrix theory// Proc. Am. Math. Soc. 1952. 3. P.382-388.

151] Markowsky G. Ordering D-classes and computing Schein rank is hard// Semigroup Forum. 1992. 44, No.3. P.373-375.

152] Muir Th. On a class of permanent symmetric functions// Proc. Roy. Soc. Edinburgh. 1882. 11. P.409-418.

153] Muir Th. The theory of determiaants in the historical order of development. London, MacMillan, 4 vols.(1906),(1911),(1920),(1923).

154] Nieminen U.J. A graphical way to solve the Boolean matrix equations AX=B and XA=B// Kybernetika, Praha. 1974. 10. P.61-65 .

155] Oharu S. A note on the powers of Boolean matrices// Proc. Japan Acad. 1967. 43. P.624—628.

156] Poincaré H. Sur les déterminants d'ordre infini// Bulletin de la Société Mathématique de France, 1885 - 1886.

157] Poplin Ph. L.; Hartwig R.E. Determinantal identities over commutative semirings// Linear Algebra Appl. 2004. 387. P.99-132.

158] Rao P.; Rao K. On generalized inverses of Boolean matrices// Linear Algebra Appl. 1975. 11. P.135-153.

159] Rao K. On generalized inverses of boolean matrices. II. // Linear Algebra Appl. 1982. 42. P.133—144.

160] Reutenauer C; Straubing H. Inversion of matrices over a commutative semiring// J. of Algebra. 1984. 88. P.350-360.

161] Rosenblatt D. On linear models and the graphs of Minkowski-Leontief matrices// Econometrica. 1957. 25. P.325—338.

162] Rosenblatt D. On the Graphs and Asymptotic Forms of Finit Boolean Relation Matrices and Stochastic Matrices// Naval Res. Logist. Quart. 1957. 4. P.151-167.

163] Rosenblatt D. On the graphs of finite idempotent Boolean relation matrices// J.Res. Natl. Bur. Stand. B. 1963. 67. P.249-256.

164] Rudeanu S. Lattice functions and equations. Discrete Mathematics and Theoretical Computer Science. London: Springer, 2001. xi,435 p.

165] Rudeanu S. Unique solutions of Boolean ring equations// Discrete Math. 1993. 122, No.1-3. P.381-383.

166] Rudeanu S. Linear Boolean equations and generalized minterms// Discrete. Math. 1983. 43, No.2-3. P.241-248.

167] Rudeanu S. Systems of linear Boolean equations// Publ. Inst. Math., Nouv. Ser. 1977. 22(36). P.231-235.

168] Rudeanu S. Boolean functions and equations. Amsterdam - London: North-Holland Publishing Company; New York: American Elsevier Publishing Company, Inc., 1974. XIX, 442p.

169] Rudeanu S. On Boolean matrix equations// Rev. Roum. Math. Pures Appl. 1972. 17. P.1075-T090.

170] Rudeanu S. Boolean equations for the chromatic decomposition of graphs// An. Univ. Bucureti. Mat. Mec. 1969. 18, No.2. P.119-126.

171] Rudeanu S. Irredundant solutions of Boolean and pseudo-Boolean equations.Rev. Roum. Math. Pures Appl. 1966. 11, No.2. P.183-188.

172] Rutherford D.E. Inverses of Boolean matrices// Proc. Glasg. Math. Assoc. 1963. 6. P.49—53.

173] Rutherford D.E. The eigenvalue problem for Boolean matrices// Proc. R. Soc. Edinb. Sect. A. 1965. 67, Part I 3. P.25-38.

174] Rutherford D.E. Orthogonal Boolean matrices// Proc. R. Soc. Edinb., Sect. A. 1966. 67. P.126-135 .

175] Schein B. M. Regular elements of the semigroup of all binary relations// Semigroup Forum. 1976. 13. P.95—102.

176] Schein B. M. Relation algebras and function semigroups (Survey articles)// Semigroup Forum. 1970. 1. P.l—62.

177] Schwarz S. A counting theorem in the semigroup of circulant Boolean matrices// Czech. Math. J. 1977. 27(102). P.504-510.

178] Schwarz S. The Euler-Fermat theorem for the semigroup of circulant Boolean matrices// Czech. Math. J. 1980. 30(105). P.135-141.

179] Schwarz S. On the semigroup of binary relations on a finite set// Czech. Math. J. 1970. 20(95). P.632-679.

180] Song S.-Z.; Lee. S.-G. Column ranks and their preservers of general Boolean matrices// J. Korean Math. Soc. 1995. 32, No.3. P.531-540.

181] Shao J.; Li Q. The index set for the class of irreducible Boolean matrices with given period// Linear Multilinear Algebra. 1988. 22, No.3. P.285-303.

182] Shao J. On the indices of convergence of irreducible and nearly reducible Boolean matrices// Acta Math. Appl. Sin. 1992. 15, No.3. P.333-344.

183] Shao J.; Li Q. On the index of convergence of an irreducible Boolean matrix// Linear Algebra Appl. 1987. 97. P. 185—210.

184] Shao J.; Li Q. On the index of maximum density for irreducible Boolean matrices// Discrete Appl. Math. 1988. 21, No.2. P.147-156.

185] Song S.-Z. Linear operators that preserve column rank of Boolean matrices// Proc. Am. Math. Soc. 1993. 119, No.4. P.1085-1088.

186] Song S.-Z. Rank preservers of nonbinary Boolean matrices// Far East J. Math. Sci. 2000. 2, No.4. P.609-614.

187] Song S.-Z. ; Lee S.-G. Column ranks and their preservers of general Boolean matrices// J. Korean Math. Soc. 1995. 32, No.3. P.531-540 .

188] Song S.-Z.; Yang S.-D.; Hong S.-M.; Jun Y.-B.; Kim S.-J. Linear operators preserving maximal column ranks of nonbinary Boolean matrices// Discuss. Math., Gen. Algebra Appl. 2000. 20, No.2. P.255-265.

189] Subrahmanyam N.V. Boolean vector space - I// Math. Zeitschr. 1964. 83. P.422—433.

190] Sylvester J.J. On the Principles of the Calculus of Forms// The Cambrige and Dublin Mathematical Journal, Volumes 7-9. 1852 — 1855.

191] Tan Y. On semigroups of generalized circulant Boolean matrices// Southeast Asian Bull. Math. 1998. 22, No.2. P.219-224.

192] Tan Y.; Zhang M.-Ch. Primitivity of generalized circulant Boolean matrices// Linear Algebra Appl. 1996. 234. P.61—69.

193] Vandermonde A. Mémoire sur l'élimination. Histoire de l'Académie Royale des Sciences. 1772.

194] Watts V.L. Boolean rank of Kronecker products// Linear Algebra Appl. 2001. 336, No.1-3. P.261—264.

195] Weddcrburn J.H.M. Boolean linear associative algebra// Ann. of Math. 1934. 35. P.185—194.

196] Wedderburn J.H.M. Lectures on matrices. American Mathematical Society. Colloq.Publ., Vol. XYII. 1934. 206p.

197] Wielandt H. Unzerlegbare, nicht negative Matrizen// Math. Z. 1950. 52. P.642-—648.

198] Yoeli M. A note on a generalization of Boolean matrix theory// Am. Math. Mori. 1961. 68. P.552-557.

[199] Yu H. On distributions of cardinalities of row spaces of Boolean matrices//Semigroup Forum. 1998. 57, No.3. P.321—330.

[200] Zhang M.-Ch. On the maximal subgroup of the semigroup of generalized circulant Boolean matrices// Linear Algebra Appl. 1991. 151. P.229—243.

[201] Zhang M.-Ch.; Hong Sh.-F.; Kan H.-B. On the cardinalities of the row spaces of non-full rank Boolean matrices// Semigroup Forum. 1999. 59, No.l. P.152—154.

[202] Zhong L. On the contribution of cardinalities of row space of Boolean matrices// Linear Algebra Appl. 1999. 288, No.1-3. P.187—198.

[203] Zhou B. On the generalized indices of Boolean matrices// Linear Multilinear Algebra. 2001. 49, No.2. P.131 141.

[204] Zhuo M. On convergence and period of group Boolean matrices// J. Math. Study. 1999. 32, No.l. P.40-47.

Публикации автора по теме диссертации

1. Поплавский В.Б. Ориентированные определители произведения булевых матриц // Математика, механика: Сб. науч. тр. , №6. Саратов: Изд-во Сарат. ун-та, 2004, с. 111-114.

2. Поплавский В.Б. О степенях булевых матриц // Алгебра и теория чисел: современные проблемы и приложения: Тез. докл. VI Междунар. конф., посвященной 100-летию Н.Г. Чудакова (Саратов, 13-17 сентября 2004г.). - Саратов: Изд-во Сарат. Ун-та, 2004. С. 92-93.

3. Поплавский В.Б. Определители степеней булевых матриц // Чебы-шевский сборник. Труды VI Международной конференции "Алгебра и теория чисел: современные проблемы и приложения". Т. 5. Вып. 3(11). 2004. С. 98-111.

4. Поплавский В.Б. Объемы и определители степеней транзитивных и рефлексивных булевых отношений на конечных множествах // Известия Тульского госуниверситета. Серия Математика. Механика. Информатика, 2004. Т. 10. Вып. 1. С. 134-141.

5. Poplavski V.B. Orientation and permanent decomposition of Boolean matrices // Abstracts The 9th Asian Logic Conference 16- 19.08.2005. Novosibirsk, Russia. Novosibirsk State University, Sobolev Institute of Mathematics. P. 117119.

6. Поплавский В.Б. Ориентация булевых бинарных отношений на конечном множестве // Международная алгебраическая конференция. К 100-летию П.Г. Конторовича и 70- летию JI.H. Шеврина. Екатеринбург, Россия. 29 августа - 3 сентября 2005г.). - Екатеринбург: Изд-во Уральского Ун-та, 2005. С. 139-143.

7. Поплавский В.Б. О равенстве обратных булевых матриц симметрической разности ориентированных присоединенных матриц // Математика, механика: Сб. науч. тр. , №7. Саратов: Изд-во Сарат. ун-та, 2005, с. 94-97.

8. Поплавский В.Б. Обратимые и присоединенные булевы матрицы. Че-бышевский сборник. Т. 6. Вып. 1, 2005. С.174-181

9. Poplavski V. On orientability and degeneration of Boolean binary relation on a finite set. // Mathematical Logic in Asia. Proceedings of the 9th Asian Logic Conference. Novosibirsk , Russia, 16-19 August 2005. World Scientific

Publishing Co. Pte. Ltd. (2006), New Jersey - London - Singapore. ISBN 981270-045-5. P. 203-214

10. Поплавский В.Б. Обертоны осцилляторных булевых матриц // Известия Саратовского университета. Нов серия. Серия Математика. Механика. Информатика. Вып. 1/2, том 6. 2006 г. С. 29-37 .

11. Поплавский В.Б. О разложимости определителей булевых (0,1)-матриц // Математика, механика: Сб. науч. тр. , №8. Саратов: Изд-во Сарат. ун-та, 2006. С. 105-108.

12. Poplavski V. On determinant expansion and minor rank function of matrices over arbitrary Boolean algebra // Материалы IX Международной конференции "Интеллектуальные системы и компьютерные науки". Москва, 23-27 октября 2006 г., Изд МГУ. Том 1, часть 1, 2006. С. 38-40.

13. Поплавский В.Б. О рангах булевых матриц // Тезисы Международной конференции по алгебре и теории чисел, посвященной 80-летию

B.Е.Воскресенского, Самара 21-26 мая 2007 . Самара. Изд. "Универс групп".

C. 42-43.

14. Поплавский В.Б. О разложении определителей булевых матриц // Фундаментальная и прикладная математика. Том 13, выпуск 4, 2007 г. Теория матриц и её приложения. С. 199-223.

15. Poplavski V. On cofactor expansion of determinants of Boolean matrices// Journal of Mathematical Sciences. Springer New York. Journal of Mathematical Sciences, Vol. 155, No. 6, 2008. P. 932- 956.

16. Поплавский В.Б. Об одном свойстве определителей булевых матриц Математика, механика: Сб. науч. тр., №9. Саратов: Изд-во Сарат. ун-та, 2007. С. 76-80.

17. Поплавский В.Б. Классы Грина и определители матриц над булевыми алгебрами // Тезисы Международной алгебраической конференции, посвященной 100-летию со дня рождения профессора А. Г. Куроша. Москва, МГУ имени М. В. Ломоносова, 28 мая - 3 июня 2008 года. Изд МГУ 2008. С.187-189.

18. Поплавский В.Б. О рангах, классах Грина и теории определителей булевых матриц // Дискретная математика. Т.20, вып. 4, 2008, с. 42-60.

19. V. В. Poplavskii. On ranks, Green classes, and the theory of determinants of Boolean matrices. Discrete Mathematics and Applications. Volume 18, Issue 6 (2008), Pages 641-658.

20. Поплавский В.Б. О матрицах над булевыми алгебрами и теории булевых определителей //Современные проблемы дифференциальной геометрии и общей алгебры. Тез. докл. Междунар. науч. конф., посвящ. 100-летию со дня рождения проф. В.В.Вагнера. Саратов, Россия, 5-7 ноября 2008 г.- Саратов: Изд-во Сарат. ун-та, 2008. С. 128-130 (ISBN 978-5-29203818-4)

21. Поплавский В.Б. Об обращении определителя булевых матриц в ноль // Современные проблемы математики, механики и их приложений. Материалы междунар. науч. конф., посвящ. 70-летию ректора МГУ академика В.А. Садовничего. Механико-математический факультет МГУ, Москва, Россия, 30 марта- 02 апреля 2009 г.- М.: Изд-во "Университетская книга", 2009. С. 399 (ISBN 978-5-91304-078-7)

22. Поплавский В.Б. О нулях определителя булевых матриц // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2009. Т. 9, вып. 3. С. 56-61.

23. Поплавский В.Б. О сохранении равенства единице полуперманентов (0,1) булевых матриц // Математика, механика: Сб. науч. тр. , №11. Саратов: Изд-во Сарат. ун-та, 2009. C.48-51(ISSN 1609-4751)

24. Поплавский В.Б. О (ОД)-матрицах с равными единице полуперманентами //Материалы X Международного семинара "Дискретная математика и ее приложения "(Москва, МГУ, 1-6 февраля 2010г.) М.: Изд-во механико-математического факультета МГУ, 2010. С. 322-325.

25. Поплавский В.Б. Минорный ранг, нули определителя булевой матрицы и их приложения// Дискретная математика. 2011.23:3. С. 93-119.

26. Poplavskii, V. В. Minor rank, zeros of the determinant of a Boolean matrix, and their applications// Discrete Mathematics and Applications. Volume 21, Issue 5-6 (2011), Pages 613-644.

27. Поплавский В.Б. Формулы Крамера для систем линейных уравнений и неравенств над булевой алгеброй// Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2011. Т. 11, вып. 3, ч. 2. С. 43-46.

28. Поплавский В.Б. Булевы матрицы и определители. LAP Lambert Academic Publishing KG. 2011. -192c. (ISBN-13: 978-3-8443-5467-6 ISBN-10: 3844354670 EAN: 9783844354676)

29. Поплавский B.B. О частичной полугруппе всевозможных булевых матриц // Алгебра и теория чисел: современные проблемы и приложения: Тез. докл. VIII Междунар. конф (Саратов, 12-17 сентября 2011г.). 2011. С. 58.

30. Поплавский В.Б. Об определителях матриц над полями, кольцами и полукольцами // Вестник МГАДА. Сер. Философские, социальные и естественные науки. 2011. №5(11). С.160-167.

31. Поплавский В.Б. Об идемпотентах алгебры булевых матриц // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2012. Т. 12, выи. 2. С. 26-33.

32. Poplavski V.B. On idempotents of Boolean matrix algebra // Int. Math. Conf. Mykolayiv, June 13-19, 2012. Book of Abstracts. P. 162-163.

33. Поплавский В.Б. О приложениях ассоциативности дуальных произведений алгебры булевых матриц // Фундаментальная и прикладная математика. 2011/2012. Т. 17, вып. 4. С. 181-192.

34. Поплавский В.Б. Об идемпотентных булевых матрицах // Алгебра и теория чисел: современные проблемы и приложения: Тез. докл. X Междунар. конф (Волгоград, 10-16 сентября 2012г.). Волгоград. Изд-во ВГСПУ "Перемена", 2012. С. 54-55.

Л

224 1