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

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

Поплавский Владислав Брониславович

ОПРЕДЕЛИТЕЛИ БУЛЕВЫХ МАТРИЦ И ИХ ПРИЛОЖЕНИЯ

Специальность 01.01.06 - математическая логика, алгебра и теория чисел

Автореферат

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

Ульяновск - 2012

3 1 янв ш

005048826

Работа выполнена иа кафедре геометрии в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования "Саратовский государственный университет имени Н.Г.Чернышевского"

Официальные оппоненты: Бредихин Дмитрий Александрович,

доктор физико-математических паук, профессор (Саратовский государственный технический университет ); Кожухов Игорь Борисович доктор физико-математических наук, профессор (Московский государственный институт электронной техники); Пихтильков Сергей Алексеевич доктор физико-математических наук, профессор (Оренбургский государственный университет).

Ведущая организация: ФГВОУ ВПО "Московский педагогический

государственный университет"

Защита диссертации состоится 20 февраля 2013 г. в Ю00 часов на заседании диссертационного совета Д 212.278.02 при ФГБОУ ВПО "Ульяновский государственный университет"по адресу: РФ, 432017, г. Ульяновск, ул. Набережная р. Свияги, 106, корп. 1,ауд. 703.

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета. С авторефератом можно ознакомиться на сайте http: //www.uni.ulsu.ru и на сайте Высшей аттестационной комиссии при Министерстве образования и пауки РФ http://vak.ed.gov.ru .

Отзывы по данной работе просим направлять по адресу: 432017, г. Ульяновск, ул. Л. Толстого, 42, УлГУ, Отдел послевузовского профессионального образования.

Автореферат разослан "¿<С" 20Щ г.

Ученый секретарь диссертационного совета

М.А. Волков

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

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

уравнений над полями.

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

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

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

определителей названа их именами.

Около 30 работ по общей теории определителей опубликовал замечательный германский математик Карл Якоби (с 1827 по 1841 год). Якоби сделал предметом особого исследования функциональные определители. Эти замечательные определители вошли в историю математики как определители Якоби и стали обязательным инструментом в анализе бесконечно малых и теории функций.

В 1841 году Кэли ввёл обозначение определителя в виде вертикальных линий. Позже, в 1845 году, отталкиваясь от исследований Гаусса, Коши и Якоби, он опубликовал весьма замечательную работу "О линейных преобразованиях", в которой детерминанты получили дальнейшее развитие в качестве инвариан-

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

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

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

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

История развития теории перманентов и их применений, начало которой положил Коши в 1812 году, не столь стремительна. В 1865 году Хорнер в работе, посвященной связи определителей с перманентами матриц 3-го порядка, назвал перманенты "контерминантами", а Хэмонд в 1879 году — "альтернирующими детерминантами". Сам термин "перманент"появился только в 1882 году в работе Мюира "О классе перманентных симметрических функций", посвященной свойствам перманента, подобным свойствам определителя квадратных матриц. Бурное продвижение теории перманентов, начиная с конца XIX века, связано, прежде всего, с работами Фробениуса и Кёнига, посвященными целочисленным матрицам, и развитием прикладной матричной комбинаторики в XX веке.

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

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

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

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

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

1 Понизовский И.С. Об определителе матриц с ч.тсменташ! из некоторого кольца // Мат. сборник. 1358. Т.45(87), N 1. С. 3-10.

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

По-видимому, первыми работами, в которых изучались булевы матрицы и исследовались системы линейных уравнений над булевыми алгебрами, были работы Лёвенгейма 2 • 3, появившиеся в начале прошлого века . Следующими заметными работами по булевым матрицам были работы Веддербёрна 4 'J (1934г.), Луица 6 • 7 (1950-1952 гг.), Вейландта 8 (1950 г.), Лгоца 9 (1952 г.), Рузер-форда 10 ■11 ' 12(1963-1066гг.). Значительным событием в развитии теории стал выход монографии Кима13.

Веддерберн в 1934 году ввёл понятие определителя квадратной матрицы с элементами из произвольной булевой алгебры через перманент новой матрицы, построенной особым образом с помощью булевых операций над элементами исходной матрицы14. Как показал Хансен 15, всякий мультипликативный гомоморфизм на полугруппе квадратных булевых матриц со значениями в булевой алгебре всегда является функцией детерминанта Веддербёрна.

В 1963 году Соколов 16 ввёл определитель через симметрическую разность булевозначных величии:

ИГ = £ • <2) А'пм) и иг = £ К(1) • А™ ■■■■■ Кы)-

ffg Р*

2Lowcnheim Ь. liber Transformation«! im Gebietekalkol// Math. Ann. 1913. 73. P.245—272.

3Lowenheim L. Gebietdetenniiianten// Math. Ann. 1919. 79. P.223—230.

■•Wedderburn J.H.M. Boolean linear associative algebra// Ann. of Math. 1934. 35. P.185—194.

'Wedderburn Л.Н.М. Lectures on matrices. American Mathematical Society. Colloq.Publ., Vol.XYlI. 1034.

0Лукц А.Г. Приложение матричной булевской алгебры к анализу а синтезу релейяо - контактных схем// Докл. Акад. наук СССР. 1930. Т. 70, .V'3. С. 421—423.

'Лунц А.Г. Алгебраические методы анализа и синтеза контактных схем// Изо. АН СССР. Сер. Математика. 1952. 1С., С. -403—426.

'Wielandt Н. Unzerlegbare, nicht negative Matrizcn// Math. Z. 1900. 52. P.G42—643.

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

"Rutherford D.E. Inverses of Boolean matrices// Proc. Glasg. Math. Assoc.. 1903. 6. P.4D—53.

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

"Rutherford D.E. Orthogonal Boolean matrices// Proc. R. Soc. Edinb., Sect. A. 196G. 07. P.126—135 .

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

14 Wedderburn 3.H.M. Boolean linear associative algebra// Ann. of Math. 1934. 35. P.185—194.

"Hansen D.J. Cauchy's multiplicative functional equation in the semigroup of Boolean matrices// Rev. Rouin. Math. Purcs Appl. 1984. 29. P.313-318.

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

Здесь Р+ и Р* обозначают все четные и нечетные подстановки соответственно. Эти величины 1Л1* естественно назвать полуперманентами, так как Per А =

|Л|+ 4- |Л|~ . Такой определитель обладает некоторыми свойствами, похожими на свойства кольцевого определителя: он сохраняет значение при транспонировании, не меняется при перестановке строк, равен нулю, если строчки матрицы одинаковые. Более того, если строчки линейно зависимы, то определитель равен нулю. Однако обратное утверждение не выполняется в общем случае.

В 1969 году Чесли и Бэвис 17 рассмотрели "три типа определителей" квадратных матриц над решетками с дополнениями. Среди них определитель Вед-дербёриа, второй — Соколова, третий — перманент квадратной булевой матрицы. В 1972 году Кунцман18 для матриц над коммутативными полукольцами употребил термин "бидетерминант", имея в виду рассмотренную выше пару полуперманентов (IЛГ, ИП . Позже Реутенауэр и Страубииг 19 ввели термины положительного и отрицательного определителей матриц над коммутативным полукольцом, имея в виду эти же полуперманеиты. Этой же терминологии придерживались Голан в монографиях 20 •21, а также Поплин и Хартвиг в своей статье 22, посвященной свойствам таких определителей. Обзор проблемы классификации линейных отображений, сохраняющих матричные инварианты и, в

23

частности, полуперманенты, можно найти в .

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

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

Цель работы. Построение теории булевых определителей и исследование различных приложений в теории булевых матриц, булево-матричных уравнений

"Chœley D.S.; Bevis J.H. Determinants for matrices over lattices// Proe. Roy. Soc. Edinburgh. 19G9. A 08, 2. P.138-144.

"Kuntzmaiin J. Théorie des réseaux (graphes). Don od, Paris, 1972.

""Reutenauer C; Straubing H. Inversion of matrices over a commutative semiring// J. of Algebra. 1984. 88. P.350—3G0.

"Golan J.S. Semirings and their Applications. Dordrecht: Kluwcr Academic Publishers. 1999. xi, 381p.

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

"Poplin Ph. L.; Hartwig П-Е. Determinantal identities over commutative semirings// Linear Algebra Appl. 2004.

387. P.99-132.

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

и неравенств, бинарных отношений, графов и комбинаторике.

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

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

Научная новизна работы. Все основные результаты диссертационной работы являются новыми и состоят в следующем:

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

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

Основные положения, выносимые на защиту.

1. Свойства булевых определителей. Аналоги формул полилинейности по строкам (столбцам) и формул Бине - Коши в форме неравенства для булевых

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

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

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

4. Характеристика вырожденных матриц. Нижняя полурешетка внешних матриц. Верхняя полурешетка внутренности и их структура полукольца и полумодуля. Приложения к комбинаторике матриц.

5. Аналоги теоремы "о базисном миноре"для матриц над полем. Условия разрешимости некоторых типов булевых матричных уравнений и неравенств, сформулированные в терминах минорных рангов (аналоги теоремы Кронекера — Капелли). Оценка решений линейных уравнений (или неравенств) с квадратными булевыми матрицами коэффициентов перед неизвестными с помощью детерминантов и перманентов. Распространение формул Крамера на квадратные системы линейных неравенств.

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

Апробация результатов. Результаты данной работы докладывались на

следующих семинарах, конкуренция и школах.

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

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

3. Международная алгебраическая конференция, посвященная 100-летию П.Г. Конторовича и 70- летшо JI.H. Шеврина. 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г., Николаев, Украина.

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

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

Публикации. Основные результаты диссертации опубликованы в 31 работе, указанных в конце автореферата, в том числе 10 статьях из списка ВАК.

Структура диссертации. Диссертация состоит из введения, 7 глав, разбитых на параграфы, приложения и списка литературы. Нумерация параграфов подчинена нумерации глав. Нумерация определений, теорем, примеров и т.д. подчинена нумерации параграфов. Объём диссертации составляет 224 стр. Список литературы содержит 204 наименования.

СОДЕРЖАНИЕ РАБОТЫ

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

Следующим образом вводится структура полумодуля булевых матриц одного размера над булевым полукольцом. Для матриц из Bmxn объединение матриц AU В = (A'j U Bj) е Bmxn заменяет сложение, а пересечение матрицы А О А = (Л П A'j) £ Втх„ с элементом из булевой алгебры В - умножение на скаляр. Здесь A'j и Bj - элементы, стоящие в г-ой строчке и j -м столбце матриц А = (A'j) и В = (Bj) соответственно.

Кроме этого, множество всех матриц относительно конъюнктного произведения, определяемого для матриц А = (A'j) 6 Bmxn и В = (Bj) € Bnxj,. согласованных размеров как матрица С = А П В € Bmxj. с элементами Cj =

y"=1(Aj П Bj), образует частичную полугруппу. Множество квадратных матриц Вяхп относительно произведения образует решёточпо упорядоченную полугруппу с единицей Е. Здесь Е - матрица, по главной диагонали которой стоят единицы, а на остальных местах - нули. Рассматриваются свойства операции конъюнктного А П В произведения матриц А и В подходящих размеров, а также дизъюнктного произведения AUB , определяемого дуальным образом: (АП В)'= A'U В' или (AU В)' = А' П В'.

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

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

$А= (J V.4= (J (АЧ'ПА?П...ПАап"),

(ах,...,£»„ )6Р («1,...,а„)€Р

+ -

где через Р и Р обозначаются четные и нечетные п -подстановки верхпих индексов соответственно. Ориентированные полупермапенты позволяют ввести +

перманент Per A =V Ли V А и общую часть ориентированных полуперманентов A A =V АГ\ V А . Правый и левый (ориентированные) определители определяются соответственно так: RDetA =V Л\ V A =V А П (V А)' и LDetA =V А\ V А = V А П (V А)'. Определителем булевых матриц называют булеву сумму правого и левого определителя: DetA — RDetA U LDetA

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

( - А)_х A)+l к /.. Aj-i Bl Л}+1 .. N

Det \ .. : .. I С jJ[A'n Del I .. : .. ],

V-- Uf=1(A'nB(") i»J+l ..) 1=1 V» AU B" AU ••/

и следующая

Теорема 1.3.5. Пусть для некоторой квадратной матрицы А € Впхп существует такой набор каких-то, не обязательно выбираемых из матрицы А , столб-

цов Ви В2,...,Вк е B„xi , что любой столбец Ль Л2,..., Ап в Bnxi матрицы А является их линейной комбинацией. Тогда если к < п , то RDetA = LDetA = DetA = 0 .

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

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

Per (А П В) Э Per А П Per В, Д (А ПВ)ЭДЛП AB,

RDet(A П В) С (RDetA П RDetB) U (LDetA П LDetB),

LDet(A П В) С (LDetA П RDetB) U (RDetA П LDetB),

Det(A ПВ)С DetA П DetB.

Формулы для полуперманентов произведения матриц с элементами из полукольца впервые исследовались в работе 24.

Глава 2 посвящена проблеме разложения определителей по элементам строки или столбца булевой матрицы. Известно, что для ориентированных полуперманентов VA, V А и перманента Per А справедливы формулы Лапласа, дающие разложения по элементам строк или столбцов любой квадратной матрицы А над произвольным коммутативным полукольцом 25 • 26 ' 27 ' 28. Для правых RDetA, левых LDetA ориентированных определителей и определителя DetA формулы Лапласа неверны в общем случае.

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

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

21 Reutenauer С; Straubing H. Inversion of matrices over a commutative semiring// J- of Algebra. 1984. 88. P.350-3G0.

"Poplin Ph. L.; Hartwig R.E. Detei minantal identities over commutative semirings// Linear Algebra Appl. 2004. 387. Р.9Э-132.

MRutherford D.E. Inverses of Boolean matrices// Proc. Glasg. Math. Assoc. 19C3. 6. P.49—53.

"Golan J.S. Semirings and their Applications. Dordrccht: Kluwer Acadcmic Publishers. 1999. xi, 381p.

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

MChesIey D.S.; Bevis J.H. Determinants for matrices over lattices// Proc. Roy. Soc. Edinburgh. 19C9. A 68, 2. P.138—144.

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

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

±

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

Теорема 3.2.4. Для матрицы Л существует обратная матрица А~1 тогда

+

и только тогда, когда БеХА = 1 и (ЛП аф' А) П (ЛП ай] А) = О. Кроме

того, обратная матрица равна объединению ее дизъюнктных ориентированных

+ ~ +

присоединенных матриц: А'1 = А =аф" Ли аф' А, аЛ] ЛП аф' А = О.

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

Теорема 3.3.1. Для квадратной булевой матрицы А существует обратная матрица тогда и только тогда, когда ИеЬА = 1 и для ее определителя выполняются формулы разложений Бе1А = и£=1 (^а- ^ В^д^А) и формулы ложных разложений 1Л=1 ПОеЬд^А) = 0(г ^ ]) для любых ее строк (или столбцов).

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

(Л"1)?' = Ретд)А = Оегд)А, (¿,.7 = 1,..., п).

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

Теорема 3.4.2. Система п линейных уравнений и"=1 (^ь п = В' с п неизвестными {.¥' ; г = 1,...,п} и с обратимой матрицей коэффициентов А имеет единственное решение, которое можно найти по формуле

Х{ = РегЛ(в=> и).

Символом г=1,...,п обозначена матрица, полученная из квадрат-

ной булевой матрицы А заменой её г— го столбца столбцом В .

В §3.5 рассматривается подгруппа и,,*,, квадратных обратимых матриц в полугруппе всех квадратных булевых п X п -матриц относительно умножения. Левым и правым действием группы обратимых матриц и„х„ на полугруппе Впхп называются отображения ЬР : и„х„ х Впхп —¥ В,1ХП и Л/1 : Впх„ х ипх„ Впхп , которые определяются на элементах 5 € ипх„ и А & В„хп как А) = 5 П А и ЯР(Б, А) = А П Я .

Отображения ЬР , ЯР являются линейными по каждому аргументу. Более того, для некоторого 5 € ипх„ отображения ЬР$ и ЯРз , определяемые па элементах равенствами ЬРз(А) = ЬР(3,А) = ЯП А и = ЯР(Б, А) — А ПЯ , являются линейными и обратимыми, так как ЬРЦ* = LPs-^ и Л^"1 = . Отображения и ЯРя сохраняют вырожденную и детер-минантную части данной матрицы. Кроме этого они сохраняют соответствующий тип вырожденности матрицы, отображая внешность во внешность, а внутренность во внутренность. Если же матрица Я € и„х„ положительна, то есть +

Я =5 , что равносильно условию РЮеЬБ = 1, то ЬР$ и ЯРз сохраняют ориентацию матриц при отображении, то есть положительные и отрицательные части переходят в положительные и отрицательные соответственно. Если же матрица Я е и,1Х„ отрицательна, то есть 5 =3 или выполняется условие ¿£>е<5 = 1, то и ЯРз меняют ориентацию па противоположную, перево-

дя положительные и отрицательные части матрицы-прообраза в отрицательные и положительные части образа соответственно.

Всякое отображение Ф : М х М —>• В упорядоченных пар элементов некоторого множества М в булеву алгебру В называется булевым бинарным отношением на множестве М . Ясно, что булево бииарное отношение является обобщением известного понятия "бинарное отношение", которое сводится к выбору двухэлементной булевой алгебры В2 = {0,1} . В случае конечности множества М его элементы можно пронумеровать натуральными числами от 1

до п . Тогда элементы булевой алгебры, которые ставятся в соответствие паре элементов из М с номерами » и ] (г,^ = 1,...,«) образуют квадратную булеву матрицу А — (Лр . Совершенно ясно, что смена нумерации элементов в базовом множестве М приводит к одновременной перестановке строк и столбцов полученной матрицы. Таким образом, данное булево бинарное отношение определяет некоторую булеву матрицу А с точностью до таких перестановок.

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

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

(А » В) (3Р){Р П А П Рт = В)

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

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

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

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

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

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

ности на группы), диффузии информации, в исследовании коммуникационных сетей, контактных схем, конечных автоматов, теории чисел, математической статистике и пр. и пр. Это нашло место в социологии, биологии, медицине, физике и компьютерных пауках. Этим объясняется и большое количество работ математиков по теории асимптотических форм для булевых матриц над алгеброй {0,1} , неотрицательных и нечетких матриц. Хороший обзор этой проблемы можно найти в статье30 и монографии 31.

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

Теоремы 4.2.1 и 4.2.2 показывают, что среди рефлексивных и нильпотеитных булевых бинарных отношений не найти отношений с максимальным индексом поскольку имеет место утверждение Шварца 32, указывающее возможный максимум для индекса произвольных булевых (или неотрицательных) ( n х г» )-матриц: ктах = (п - I)2 + 1. Вместе с тем, Вейландт 33 ранее доказал, что этот предел достигается примитивными матрицами тогда и только тогда, когда они определяют булевы отношения, задаваемые матрицами определённого вида. Максимальное значение индекса квадратной булевой матрицы, в общем, зависят и от факторизационных рангов таких матриц, от их приводимости и неприводимости, от величины их периодов и пр., что отражено в миогочислен-

30Li Q.; Sliao J. The index set problem for Boolean (or nonnegative) matrices// Discrete Math. 1993.123, No.1-3. P.75—92.

31 Kiin K.H. Boolean matrix theory and applications. Гиге and Applied Mathematics, 70. New York - Basel: Marcel Dekkcr, Inc. 1982. XIV, 425p.

33Schwarz S. On the semigroup of binary relations on a finite set// Czech. Math. J. 1970. 20(95). Р.032-07Э.

33Wie]andt H. Unzerlegbare, nicht negative Matrizen// Math. Z. 1950. 52. Г.642-С48.

пых публикациях па эту тему.

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

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

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

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

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

Теорема 4.6.5. Для каждой квадратной булевой матрицы А имеет место цепочка включений 1 = Бе1Ай Э ДеМ*'1 Э ... Э Ве1Ак Э____

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

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

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

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

Теорема 4.7.2. Для полуперманентов любого рефлексивного булева бинарного отношения на конечном множестве, состоящем из п элементов, и степеней этого отношения выполняется V Ак = 1 для всех к — 0,1,2,... и V А С V А2 С ... ÇV A=V Л" = ... Следовательно, левые определители любого рефлексивного отношения и его степеней равны нулю, то есть все они являются неотрицательными булевыми отношениями.

Соотношения между различными ранговыми функциями для матриц над полукольцами, а также изменение их значений относительно операций с матрицами хорошо изучены 34 • 35 • 30 • 37 •38.

В §5.1 изучаются столбцовые С (А) и строчные R(A) пространства булевой матрицы А произвольного размера. Следующие неравенства дают сравпение факторизационных рангов и столбцовых (строчных):

rankjA < dimC(A) = rankcA, rank/A < dimR(A) = ranknA.

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

3<Бисли Л. Б., Гутерман А. Э., Пи С.-Ч. LP-проблемы для ранговых неравенств над полукольцами: граничные ранги// Фундаментальная и прикладная математика. 2004. Том 10, У2. С. 3—21.

33Пшсницыиа O.A. ФакторизационныА и граничный ранги матричного объединения над полукольцом//

Фундаментальная и прикладная математика. 2003. Т. Э, .V3. С. 175—197.

MBeasley L.B.; Guterman А.Е. Rank inequalities over semirings // J. Korean Math. Soc. 2005. V. 42, Jfc2.

P,223—241.

37Kim K.H. Воо1еал matrix theory and applications. Pure and Applied Mathematics, 70. New York - Basel: Marcel Dekker, Inc. 1982. XIV, 425p.

38Song 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.

ес{А) = {В € М(В) : С(В) = С(Л)} и еп(А) = {В 6 М(В) : R(B) = Д(Л)} - соответствующие классы эквивалентности, порожденные элементом А .

Пересечение эквивалеитностей e¡j — ее П ел также является эквивалентностью, ее классы определяются условием £ц(А) = {В 6 М(В) : (С(В) = С(А)) А (R(B) = Я(Л))} = ес(А) П eR{A).

Можно рассмотреть объединение бинарных отношений scUeji. Однако, объединение эквивалеитностей в общем случае эквивалентностью не является, так как для пего не выполняется условие транзитивности. Поэтому берем транзитивное замыкание объединения бинарных отношений to — U*Li(e<? U £li)k = £c V ej¡, как минимальное транзитивное отношение, содержащее £с и ■

Справедливы следующие равенства (предложение 5.2.3): ед = ее V £r = ¿с • £R = £п ■ £с ■

То, что булевы матрицы Л и В из частичной полугруппы М(В) находятся в отношении ej , означает существование матриц U\,U2,Vi,V2 подходящих размеров таких, что А = Vi П BV\U\ и В = V2 П Л П С^ •

Очевидно, ej является отношением эквивалентности. Кроме того, несложно показать, что ед С ej . На самом деле для булевых матриц частичной полугруппы М(В) выполняется равенство £д = ej (Предложение 5.2.3.), аналогичное известному результату из теории полугрупп, состоящему в том, что для устойчивых полугрупп, в частности, периодических полугрупп, классы Грина D и J совпадают.

Проведённое построение классов эквивалеитностей £д , £с ,£п ,£d па М(В) аналогично построению классов Грина Н , R , С , D , J для полугрупп соответственно 39 • 40.

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

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

В §5.4 показывается, что определители всех квадратных матриц одного и

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

с.

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

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

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

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

тт{гапкцА,гапксА) > rankjA > rank А.

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

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

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

Далее исследуется совместность уравнения вида АПХПВ = С, что влечёт, в частности, равносильность регулярности булевой матрицы А и ассоциативности формулы А П A17" U^LI А17" П А .

В последнем параграфе этой главы изучаются свойства произведений А П

А,т , А'ТПА, Ат ПА', Л'ПЛГ, AUA'7', A'TUA, ATUA', Л'иЛт, входящих в формулы основных теорем предыдущих параграфов 5.С -5.7. Показано, что все они являются ндемпотентами особого типа, названного вторичным, в соответствующих частичных полугруппах (M(B),U) и (М(В), П) . Доказывается также, что принадлежность матриц одному одностороннему главному идеалу частичной полугруппы булевых матриц всевозможных размеров влечёт совпадение их вторичных идемпотеитов соответствующих типов. Кроме того, в термипах ассоциативности формул указывается необходимый и достаточный признак того, когда матрица и её соответствующий вторичный идемпотент находятся в одном одностороннем идеале частичной полугруппы всевозможных булевых матриц.

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

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

Задачи сохранения матричных свойств при преобразовании матриц с элементами из некоторого полукольца являются самыми широко представленными работами по этой теме в современной математической литературе (см., например, обзор 41. Минорные ранги, как показано в главе 5, дают нижние оценки для строчных, столбцовых, факторизационных и перманентных рангов. Кроме того, минорные ранги являются инвариантами D -классов (или совпадающих с ними J -классов) частичного группоида булевых матриц всех размеров. Однако в главе б, в отличие от главы 5, рассматриваются иные преобразования матриц, которые также сохраняют минорные ранги.

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

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

линейными оболочками тех же столбцов.

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

В следующем §6.3 изучаются свойства множества квадратных матриц неполного ранга, то есть таких матриц, определитель которых равен нулю. Мы проводим это, используя перманентное разложение произвольной квадратной матрицы Л, то есть представление в виде объединения А = Ли Л и Л соответственно внешней, детерминантной и внутренней частей. Они получаются, как пересечения А = (РегА)'ПА , А= 1>е*ЛПЛ , Л = ДЛПЛ . Множество вырожденных матриц, определяемое условием БеЬА = 0 или условием Л = Л и А , образует идеал в полугруппе квадратных матриц относительно произведения матриц. Мы показываем, что все внутренние матрицы образуют подполугруппу в этом идеале. В §6.3 показано, в частности, что внешние матрицы образуют нижнюю полурешетку, а главные булевы идеалы, порожденные внешней матрицей, состоят из внешних матриц. Внутренности же образуют верхнюю полурешетку, которой принадлежат линейные комбинации и даже многочлены, построенные из всевозможных произведений внутренних матриц и их степеней с коэффициентами из булевой алгебры. Более того, множество всех внутренностей образуют полукольцо с аддитивной операцией и и мультипликативной операцией П. Все вышесказанное объясняет наш интерес к внешним и внутренним булевым матрицам.

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

В главе 7 рассматриваются приложения полученных в 6 главе результатов к матричным уравнениям и неравенствам, проблема разрешимости которых является весьма актуальной. Условия разрешимости некоторых типов матричных уравнений и неравенств сформулированы в §7.1 в терминах минорных рангов.

Несложно показать, что неравенство В С Л П X , в котором Л и В -булевы матрицы произвольного согласованного размера, может быть совместным или несовместным (пример 7.1.1), в отличие от матричного неравенства

В О А П X , которое как известно 42 (см. также предложение С.4.1 ) всегда совместно. Таким образом, становится понятным наш интерес к проблеме разрешимости матричного неравенства В С А ПХ. На эту проблему указывал также Лгоц, в своей работе 43, ставшей классической по теории булевых матриц. Мы доказываем аналог теоремы Кропекера - Капелли (теорема 7.1.3), что неравенство В С А П X для булевой матрицы А и столбца В над булевой алгеброй В2 = {0,1} имеет решение, если столбец не увеличивает минорного ранга матрицы А .

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

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

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

(ЛПХ)и(ВПУ) = С,

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

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

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

"Luce ILD. A note on Boolean matrix theory// Proc. Am. Math. Soc. 1952. 3. P.382—388.

формул, касающиеся свойств столбцов (или строк) квадратной матрицы с равным 1 детерминантом.

ВЫВОДЫ

1. Описаны свойства булевых определителей. Получены неравенства, являющиеся аналогами формул полилинейности по строкам (столбцам) (теорема 1.3.2) и аналоги формул Вине - Коши (теорема 1.4.1) для булевых определителей.

2. Введен метод перманентных разложений квадратных булевых матриц (теоремы 2.1.1 и 2.1.2).

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

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

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

6. Найдены возможные значения периодов квадратных матриц с элементами из произвольной булевой матрицы (теорема 4.4.1). Описано поведение диагональных элементов степеней квадратной булевой матрицы в терминах "обертонов1^ §4.1 и Приложение). Получены свойства перманентов и детерминантов степеней булевых квадратных матриц (или булевых бинарных отношений на конечном множестве) (теоремы 4.0.3-4.6.6). Изучены свойства транзитивных и рефлексивных булевых бинарных отношений и их степеней на конечном множестве в контексте определителей (теоремы 4.7.1, 4.7.2).

7. Введено новое понятие минорного ранга булевой матрицы произвольного размера, который пе превосходит её перманентный, факторизационный, а также строчный и столбцовый ранги (теоремы 5.3.1, 5.4.2). Более того, факто-ризационные и минорные ранги, а также размерности строчных и столбцовых пространств матриц ( т.е. строчный и столбцовый ранги), являются инвариантами для двустороннего идеала частичной полугруппы всевозможных булевых матриц с частичной операцией конъюнктного произведения (теоремы 5.2.1, 5.2.2, 5.4.3).

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

9. Введено понятие вторичного идемпотента, порождённого булевой матрицей произвольного размера, в соответствующих дуальных частичных полугруппах с конъюнктным или дизъюнктным произведениями. Доказано, что порож-даемость матрицей одного и того же одностороннего главного идеала частичной полугруппы булевых матриц всевозможных размеров влечёт совпадение соответствующих им вторичных идемпотентов определённого вида. Исследуется проблема делимости вторичных идемпотентов (теоремы 5.9.2, 5.9.8). Показана связь понятий, "транзитивпо-рефлексивное замыкание"и "вторичные идемпо-тенты"(теоремы 5.10.1 - 5.10.4).

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

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

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

матриц над полем (теоремы 6.2.1, 6.2.2).

13. Получена характеристика вырожденных матриц. Показано, в частности, что внешние матрицы образуют нижнюю полурешетку, а главные булевы идеалы, порожденные внешней матрицей, состоят из внешних матриц (теорема 6.3.4). Внутренности же образуют верхнюю полурешетку, обладая структурой полукольца и полумодуля (теорема 6.3.7). Указываются приложения к комбинаторике матриц. Доказывается утверждение, которое является эквивалентом известной теоремы Фробеииуса — Кёнига, которое сравнивает строение матрицы с нулевым перманентом со всеми матрицами, для которых перманенты отличны от нуля (теоремы 6.4.1, 6.4.2).

14. Указаны условия разрешимости некоторых типов булевых матричных уравнений и неравенств, сформулированные в терминах минорных рангов (аналоги теоремы Кронекера — Капелли). Даётся оценка решений линейных уравнений (или неравенств) с квадратными булевыми матрицами коэффициентов перед неизвестными с помощью детерминантов и перманентов. Эти формулы являются распространением формул Крамера на квадратные системы линейных неравенств (теоремы 7.1.1 — 7.1.5, 7.2.2).

СПИСОК РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в рецензируемых научных журналах из перечня ВАК

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

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

[3] 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. Перевод статьи' "О разложении определителей булевых матриц // Фундаментальная и прикладная математика. Том 13, выпуск 4, 2007 г. С. 199-223."

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

Poplavskii. On ranks, Green classes, and the theory of determinants of Boolean matrices. Discrete Mathematics and Applications. V. 18, 6 (2008), P. 641-G58.)

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

[6] Поплавский В.Б. Минорный ранг, нули определителя булевой матрицы и их приложения// Дискретная математика. 2011.23:3. С. 93-119. (Poplavskii, V. В. Minor rank, zeros of the determinant of a Boolean matrix, and their applications// Discrete Mathematics and Applications. V. 21, 5-6 (2011), P. 613-644.Translated from Discrete Mathematics.)

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

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

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

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

Монографии

[11] Поплавский В.Б. Булевы матрицы и определители. LAP Lambert Academic Publishing KG. 2011. -192c.

Прочие публикации

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

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

[14] Поплавский В.Б. Определители степеней булевых матриц // Чебышевский сборник. Труды VI Международной конференции "Алгебра и теория чисел: со-

временные проблемы и приложения". Т. 5. Вып. 3(11). 2004. С. 98-111.

[15] Poplavski V.B. Orientation and permanent decomposition of Boolean matrices // Abstracts The 9th Asian Logic Conference 1G- 19.08.2005. Novosibirsk, Russia. Novosibirsk State University, Sobolev Institute of Mathematics. P.117-119.

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

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

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

[19] 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. P. 203-214.

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

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

[22] Поплавский В.Б. О рангах булевых матриц // Тезисы Международной конференции по алгебре и теории чисел, посвященной 80-летию В.Е. Воскресенского, Самара 21-26 мая 2007 . Самара. Изд. "Универс групп", 2007. С. 42-43.

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

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

[25] Поплавский В.Б. О матрицах над булевыми алгебрами и теории буле-

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

[2G] Поплавский В.Б. Об обращении определителя булевых матриц в ноль/,/ Современные проблемы математики, механики и их приложений. Материалы междунар. науч. конф., посвящ. 70-летию ректора МГУ академика В.А. Садов-ничего. Мех.-мат. фак-т МГУ, Москва, Россия, 30 марта- 02 апреля 2009 г.- М.: Изд-во "Университетская книга", 2009. С. 399.

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

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

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

[30] Poplavski V.B. On idempotents of Boolean matrix algebra // Int. Math. Conf. Mykolayiv, June 13-19, 2012. Book of Abstracts. P. 162-1G3.

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

Подписано в печать 23.10.2012. Формат 60x84 1/16. Бумага офсетная. Гарнитура Times New Roman. Печать RISO. Объем 2,0 печ. л. Тираж 100 экз.

Заказ № 229.

Отпечатано с готового оригинал-макета Центр полиграфических и копировальных услуг Предприниматель Серман Ю.Б. Свидетельство № 3117 410600, Саратов, ул. Московская, д.152, офис 19, тел. 26-18-19, 51-16-28

Саратовский государственный университет имени Н.Г.Чернышевского

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

05201350446

Поплавский Владислав Брониславович

ОПРЕДЕЛИТЕЛИ БУЛЕВЫХ МАТРИЦ И ИХ ПРИЛОЖЕНИЯ

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

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

Саратов - 2012

Содержание

Введение 5

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

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

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

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

Введение ................................................................33

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

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

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

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

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

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

Введение ................................................................56

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

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

матриц..............................................................60

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

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

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

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

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

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

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

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

Введение ................................ 78

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

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

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

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

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

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

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

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

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

Введение ................................................................95

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

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

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

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

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

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

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

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

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

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

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

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

Введение ................................127

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение ................................163

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

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

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

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

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

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

Введение ................................187

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

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

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

Приложение 195

Литература 205

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

Введение

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

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

Г а\х + Ь\у = С\ \ а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]).

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