Определители булевых матриц и их приложения Поплавский, Владислав Брониславович

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Поплавский, Владислав Брониславович. Определители булевых матриц и их приложения : диссертация ... доктора физико-математических наук : 01.01.06 / Поплавский Владислав Брониславович; [Место защиты: ГОУВПО "Ульяновский государственный университет"].- Ульяновск, 2013.- 224 с.: ил.

Введение к работе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

По-видимому, первыми работами, в которых изучались булевы матрицы и исследовались системы линейных уравнений над булевыми алгебрами, были работы Лёвенгейма ² ' ³, появившиеся в начале прошлого века . Следующими заметными работами по булевым матрицам были работы Веддербёрна ⁴ ' ⁵ (1934г.), Лунца ⁶ ' ⁷ (1950-1952 гг.), Вейландта ⁸ (1950 г.), Люца ⁹ (1952 г.), Рузер-форда ¹⁰ ' ^п ' ¹²(1963-1966гг.). Значительным событием в развитии теории стал выход монографии Кима¹³.

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

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

_{иг = к}⁽¹⁾ _<²⁾ ^А_п^п)_{) *} _{иг = Ек}⁽¹⁾ _<²⁾ ^А_п^п)_У

а&Р+ а&Р-

²Lowenheim L. Uber Transformationen im Gebietekalkol// Math. Ann. 1913. 73. P.245—272. ³Lowenheim L. Gebietdeterminanten// Math. Ann. 1919. 79. P.223—236.

⁴Wedderburn J.H.M. Boolean linear associative algebra// Ann. of Math. 1934. 35. P.185—194. ⁵Wedderburn J.H.M. Lectures on matrices. American Mathematical Society. Colloq.Publ., Vol.XYII. 1934. ⁶Лунц А.Г. Приложение матричной булевской алгебры к анализу и синтезу релейно - контактных схем// Докл. Акад. наук СССР. 1950. Т. 70, №3. С. 421-423.

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

⁸Wielandt Н. Unzerlegbare, nicht negative Matrizen// Math. Z. 1950. 52. P.642—648. ⁹Luce R.D. A note on Boolean matrix theory// Proc. Am. Math. Soc. 1952. 3. P.382—388. ¹⁰Riitherford D.E. Inverses of Boolean matrices// Proc. Glasg. Math. Assoc. 1963. 6. P.49—53. ⁿRutherford D.E. The eigenvalue problem for Boolean matrices// Proc. R. Soc. Edinb. Sect. A. 1965. 67, Part I 3. P.25-38.

¹²Rutherford D.E. Orthogonal Boolean matrices// Proc. R. Soc. Edinb., Sect. A. 1966. 67. P.126—135 . ¹³Kim K.H. Boolean matrix theory and applications. Pure and Applied Mathematics, 70. New York - Basel: Marcel Dekker, Inc. 1982. XIV, 425p.

¹⁴Wedderburn J.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. Roum. Math. Pures Appl. 1984. 29. P.313-318.

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

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

В 1969 году Чесли и Бэвис рассмотрели "три типа определителей" квадратных матриц над решетками с дополнениями. Среди них определитель Вед-дербёрна, второй — Соколова, третий — перманент квадратной булевой матрицы. В 1972 году Кунцман¹⁸ для матриц над коммутативными полукольцами употребил термин "бидетерминант", имея в виду рассмотренную выше пару полуперманентов (|^4| ⁺ , |^4|~) Позже Реутенауэр и Страубинг ¹⁹ ввели термины положительного и отрицательного определителей матриц над коммутативным полукольцом, имея в виду эти же полуперманенты. Этой же терминологии придерживались Голан в монографиях ²⁰ ' ²¹, а также Поплин и Хартвиг в своей статье ²², посвященной свойствам таких определителей. Обзор проблемы классификации линейных отображений, сохраняющих матричные инварианты и, в частности, полуперманенты, можно найти в ²³.

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

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

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

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

¹⁸Kuntzmann J. Theorie des reseaux (graphes). Dunod, Paris, 1972.

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

²⁰Golan J.S. Semirings and their Applications. Dordrecht: Kluwer Academic Publishers. 1999. xi, 381p.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6-ая Междунар. конф. "Алгебра и теория чисел: современные проблемы и приложения", посвященной 100-летию Н.Г. Чудакова (Саратов, 13-17 сентября 2004г.).
9-ая Азиатская конференция по логике.16- 19.08.2005, Новосибирск, Россия.
Международная алгебраическая конференция, посвященная 100-летию П.Г. Конторовича и 70- летию Л.Н. Шеврина. 29 августа - 3 сентября 2005г., Екатеринбург, Россия.
Алгебраический семинар "Кольца и модули", МГУ ( 5.12.2005, 26.02.07).
IX Международная конференция "Интеллектуальные системы и компьютерные науки". МГУ, Москва, 23-27 октября 2006 г.

Международная конференция по алгебре и теории чисел, посвященная 80-летию В.Е.Воскресенского, 21-26 мая 2007. Самара, Россия.
Международный алгебраический семинар. 17-22 сентября 2007 г., ВГПУ, Волгоград, Россия.
Международная алгебраическая конференция, посвященная 100-летию со дня рождения профессора А. Г. Куроша. 28 мая - 3 июня 2008 года. МГУ, Москва, Россия.
Международная научная конференция, посвященная 100-летию В.В. Вагнера. 5-7 ноября 2008 г., Саратов, Россия.

Международная научная конференция, посвященная 70-летию ректора МГУ академика В.А. Садовничего, "Современные проблемы математики, механики и их приложений". 30 марта- 02 апреля 2009 г. МГУ, Москва, Россия.
X Международный семинар "Дискретная математика и ее приложения". 1-6 февраля 2010г. МГУ, Москва, Россия.
Семинар профессора Васильева А.Ю. Института Математики университета Бергена (Норвегия), 26 июня 2010.
Международный алгебраический симпозиум, посвященный 80-летию кафедры высшей алгебры механико-математического факультета МГУ и 70-летию профессора А.В.Михалева, 15- 18 ноября 2010 г.
Международная конференция по алгебре и теории чисел, посвященная 190-летию П.Л. Чебышева и 120-летию И.М. Виноградова. Саратов, 12-17 сентября 2011г.

Международная математическая конференция, посвященная 70-летию профессора В. Кириченко. 13-19 июня, 2012г., Николаев, Украина.
10-ая Международная конференция "Алгебра и теория чисел: современные проблемы и приложения"Волгоград, 10-16 сентября 2012г.
Ежегодные научные конференции по математике и механике СГУ, Саратов, 2005-2012г.г.

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

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

Определители булевых матриц и их приложения Поплавский, Владислав Брониславович

Похожие диссертации на Определители булевых матриц и их приложения