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

Московский государственный университет имени М. В. Ломоносова

На нравах рукописи УДК 512.530, 612.558, 512.013

Шитоп Ярослнн Николпопич

РАНГОВЫЕ ФУНКЦИИ МАТРИЦ НАД ПОЛУКОЛЬЦАМИ

СшчиШЛЬШХ'/Н, 1)1,01,00 ™ МНТСМНТИ'КЧ'КПИ

ЛОГИКИ, ПЛГоПра И ЇСОріІЯ чисел

АВТОРЕФЕРАТ диссертации ид «шскашт учопоП стши кандидати фішко-мнтчішічргкнх наук

Москва 2012

2 0 СЕН 2012

005047016

Работа выполнена на кафедре высшей алгебры Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

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

профессор Гутерман Александр Эмилевич.

Официальные оппоненты: Кожухов Игорь Борисович — доктор

физико-математических наук, профессор, Московский институт электронной техники;

Богданов Илья Игоревич — кандидат физико-математических наук, доцент, Московский физико-технический институт (государственный университет).

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

Защита состоится 28 сентября 2012 г. в 1С ч. 45 мин. па заседании диссертационного совета Д 501.001.84 при Московском государственном университете имени М.В.Ломоносова по адресу: РФ, 119991, Москва, ГСП-1, Ленинские горы, д. 1, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание МГУ, 14 этаж).

Автореферат разослан 28 августа 2012 г.

Ученый секретарь диссертационного совета Д 501.001.84 при МГУ, доктор физико-математических наук, профессор

А. О. Иванов

Общая характеристика работы Актуальность темы исследования

Множество S, на котором заданы бинарные операции сложения и умножения, обозначаемые как ф и <g>. называется полукольцом, если

• S — абслев моноид но сложению (нейтральный элемент этого моноида обозначается через 0):

• S — полугруппа по умножению (нейтральный элемент этой полугруппы, если он есть, обозначается через 1);

• умножение слепа и справа дистрибутивно по сложению;

• для любого элемента х G S верно, что х ® 0 = 0 0 .т = 0.

Как гшдим, полукольцо является алгебраической структурой, и его определение сходно с определением кольца. Основное отличие полукольца от кольца проявляется и том, что пс всякий элемент может быть обратим по сложению. В качестве примеров полуколец, не являющихся кольцами, можно привести некоторые числовые множества: например, целые неотрицательные числа Ъу и неотрицательные вещественные числа Mf являются полукольцами относительно обычных сложения и умножения. Среди важных примеров полуколец, не связанных с числовыми множествами, дистрибутивные решетки и булевы алгебры; множество всех идеалов заданного кольца также является полукольцом относительно суммы и произведения идеалов. Понятие полукольца было впервые непосредственно введено, вероятно, американским математиком Г. Вапднвером в работе1, посвященной проблемам, связанным с аксиоматической теорией оснований математики. Впоследствии па протяжении десятилетий полукольца изучались с различных точек зрения и в связи с различными теоретическими и прикладными задачами.

1 H. S. Vandiver, Note oil a simple type of algebra in which cancellation law of addition does not hold, Bull. Amcr. Math. Soc... 40(103-1), 014-920.

Подробное описании различных приложений теории полуколец дано в монографии Голапа2, и мм останошшся на описании тех и;з них, которые наиболее тесно связаны с полученными нами результатами. Одним из важнейших примеров полуколец, рассматриваемых в данной работе;, является тропическое полукольцо, т.е. множество 3R. вещественных чисел, пополненное элементом +оо, с операциями минимума и суммы. Значительная часть приложений теории полуколец связана именно с тропическим полукольцом. В первую очередь, мы отмечаем важную его роль для теории оптимизации, поскольку именно различные задачи оптимизации во многом способствовали появлению и разработке тропических методов в математике. Отметим также, что слово "тропический" было предложено Ж.-Э. Пеном3 в знак признания заслуг математиков бразильской школы. Действительно, своим развитием тропическая математика во многом обязана И. Симону, в работах которого устанавливались ее связи с алгебраической геометрией, теорией полугрупп, теорией оптимизации и некоторыми другими областями4.

Как одни из основополагающих следует также отметить работы ленинградского математика Н. Н. Воробьева0, идеям которого в значительной мере обязано развитие полукольцевого и тропического подходов в различных областях математики и теории оптимизации в частности. Важным шагом в развитии тропических методов в теории оптимизации стали работы английского математика Р. Канингсма-Грина6. Дальнейшее развитие тропические методы получили в работах французских математиков М. Гондрана и М. Мину7, которые описали методы, ставшие важным инструментом для дальнейших исследований в теории оптимизации. Тропические методы и теории оптими-

- J. S. Golaii, Semirings and their applications, Kluvvcr Acad. Publ., Dordrecht, 1999.

:1 D. Speyer, B. Sturmfels, Tropical Mathematics. Matltemati.es Magazine, 82(3)(2009), 163-173.

1 I. Simon, Recognizable sets vvith multiplicities in the tropical semiring. Mathematical foundatiom of

Computer science, Lccturc Notes in Comput. Sei., 324, Springer, Berlin, 198S. 107-120.

5 N. N. Vorobycv, Ext.rcnial algebra of positive niatricus. Elektron. Informationsverarbeitung und Kyber-

netik, 3(1907), 39-71.

s R. A. Cuninghame-Green, Minimax Algebra, Lccturc Notes in Economics and Matliematical Systems,

16G, Springer-Verlag, Berlin, 1979.

7 M. Gondran. M. Minoux, Graplis and Algorithms. Wiley-Intersriencc. New York. 1984.

зации актишю развиваются и и настоящее время: отметим работы Г. Я. Ол-едера, показывающие фундаментальную роль тропических методов в теории расписаний®. D целом, тропический подход и теории оптимизации основан по многом на том, что многие важные задачи оптимизации, не являющиеся линейными в классическом смысле, принимают линейный вид, если формализовать их с использованием тропической нотации. Иными словами, они сводятся к линейным задачам, таким как решение системы линейных уравнений или вычисление ранга, для матриц над тропическим полукольцом. Этот факт обусловливает важность исследования полуколец и тропического полукольца п особенности с точки зрения линейной алгебры.

Отметим также, что важную роль в развитии тропических методов и их приложений к важным вопросам современной математики сыграли работы академика D. П. Маслина9. Для приложений в квантовой физике важную роль играет деквантование Маслова, которое устанавливает связь классической математики над числовыми полями с тропической математикой10. Новая область теории вероятности, которая называется ндемиотептпым анализом и имеет множество приложений в квантовой физике и квантовой теории вычислений. также основана, ira работах В. П. Маслова11.

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

*в- Hcidcrgott, С,. J. Olsdcr. J. van der Woiide. Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max- Plus Algebra and Its Applications, Princeton Univ. Press, 200G.

9 D. П. Mae.tOB, О новом принципе суперпозиции для задач оптимизации, УМН, 42:3(255)(1987), 39-48.

10 Г. Л. Литвинов, Деквантование Маслова. пдемнотентная и тропическая математика: краткое введение, Теория представлений, дииамтсские системы, комбинаторные, и алгоритмические методы, XIII, Зап. научи, сем. ПОМП, 326, ПОМП, СПб., 2005. 145-182.

1 V. N. Kolokol'tsov, V. P. Maslov, Idcmpotent Analysis and Applications, Klutver, Dordrecht, 1907.

и максимума н играит фундаментальную роль в нечеткой логике и теории нечетких множеств12. D важном разделе теоретической информатики, посвященном проверке корректности компьютерных программ, фундаментальную роль играет формальная алгебраическая система, известная как логика Хо-ара13. Аналогичные способы описания дают динамические алгебры и алгебры Клини14. Перечисленные структуры также являются полукольцами, что подтверждает значимость исследования полуколец в общем случае.

Наконец, отметим еще одну область применения методов линейной алгебры над полукольцами. Раздел алгебраической геометрии, известный как тропическая геометрия, появился не так давно, но бурно развивается в настоящее время10. Тропическая геометрия рассматривает обобщения классических понятий, таких как многообразия, идеалы, стандартные базисы, на тропический случай. Методы тропической геометрии помогают установить довольно тесную связь тропической линейной алгебры с теорией матроидов10. Многие задачи тропической геометрии сводятся к задачам линейной алгебры над тропическим полукольцом, что подтверждает важность изучения тропической геометрии с точки линейной алгебры.

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

12 Л. Cogiten, The logic of ¡»exact, concepts, Synthese, 19(1908/9), 325-373.

11 С. A. R. Ho;ire, An axiomatic basis for computer programming, Comm. ACM, 12(I9G9), 576-580.

14 W. Weehler, lloare algebras versus dynamic algebras, in .1. Demetrovics et al. (eds): Algebra, Combinatorics and Logic in Computer Science, Gyor 1983, Colloquia Math. Soc. Janos Bolyai, 42, North Holland, Amsterdam, 198G.

11 M. Develin, B. Sturmfels, Tropical convexity, Documenta Math. 9(2004), 1-27.

16 M. Develin. F. Santos, B. Sturmfels, On the rank of a tropical matrix. Discrete and Computational Geometry (E. Goodman, J. Pach and E. Welzl, eds.), MSIU Publications. Cambridge Univ., Press, 2005, 213212.

Цель работы

Изучение различных линейно-алгебраических инвариантов матриц над полукольцами и применение! полученных результатеп к решению проблем ли-иейпоіі алгебрі,і, теории матроидов и т]юпичеекой геометрии.

Научная новизна

Полученные автором результаты являются новыми, следующие из них являются основными результатами работы.

• Результаты, описывающие взаимное поведение ранговых функций тропических матриц:

- решена проблема Акян, Гобера и Гутермана17 о тропических матрицах с различны ми строчным и столбцовым рангами Гопдрапа -Мину: покачано, что п = 5 и m = 6 суть минимальные целые числа, для которых существует тропическая матрица размера ті х тп с различными строчным и столбцовым рангами Гондрана-Мниу;

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

• Результаты, описі,тающие функцию ранга Гопдрапа-Мипу матриц над

полукольцами:

- получена характеризация идемпотентпых полуколец, над которыми выполнено неравенство па ранг Гондрана-Мину произведения матриц; в частности, это неравенство доказано для тропических матриц;

" М- Akia"' S" Gaubm- А- Guarnían, Linear independence over tropical semirings and beyond, Contemporary Mathematics, AMS, 495(2009), 1-38.

- показано, что ранг Гондрана-Мину матрицы совпадает с рангом Гондрапа-Мппу ос шаблона с точностью до тропического умножения строк матрицы на ненулевые элементы;

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

• Результаты о функции ранга Капранова тропических матриц:

- доказано неравенство на ранг Капранова произведения тропических матриц в случае бесконечного базового поля; в случае конечного базового поля приведен пример матриц, для которых это равенство нарушается;

- решена проблема Чан, Йенсспа п Рубеи18 о тропических матрицах с различными тропическим рангом и рангом Капранова: приведен пример матрицы размера 6x6с тропическим рангом 4 и рангом Капранова 5 и показано, что эта матрица имеет наименьший возможный размер среди всех матриц с различными тропическим рангом и комплексным рангом Капранова;

- получено полное решение проблемы Депелина, Сантоса и Штурмфельса10 о рангах тропических матриц размера 5x5: показано, что тропические матрицы размера 5 х 5 с тропическим рангом 3 и рангом Капранова 4 существуют в том и только том случае, если базовое поле содержит не более трех элементов.

- построен контрпример к гипотезе Чан, Йенсспа и Рубен о тропическом базисе идеала кольца многочленов, порожденного всеми минорами порядка г матрицы переменных размера d. х п: доказано,

М. Chan, А. N. Jensen. Е. lUibci, The 4x4 minors of a 5xn matrix are a tropical basis, Linear Algebra Appl, 435(7)(2011), 1338-1011.

что миноры порядка 6 матрицы переменных размера 7x7 не образуют тропического базиса.

Основные методы исследования

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

Теоретическая и практическая значимость

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

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

Результаты диссертации неоднократно докладывались на научно-исследовательском семинаре кафедры высшей алгебры Механико-математического факультета МГУ, на семинарах "Кольца и модули" и "Теория матриц" Механико-математического факультета МГУ (2009-2012 гг.) Также результаты докладывались на следующих семинарах и конференциях:

• XVII Международная конференция студентов, аспирантов и молодых ученых "Ломоносов", Москва, 2010;

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

• XVIII Международная конференция студентов, аспирантов и молодых ученых "Ломоносов". Москва, 2011;

• Международная конференция но матричным методам в математике и приложениях "МММА-2011", Москва, 2011;

• Научная конференция "Ломоносовские чтения", Москва, 2011;

• семинар "Гомологические и гомотопические методы в геометрии", Национальный исследовательский университет Высшая школа экономики, Москва, 2012;

• XIX Международная конференция студентов, аспирантов и молодых ученых "Ломоносов", Москва, 2012;

• Международная конференция "Future Directions in Tropical Mathematics and its Applications", Манчестер, 2012.

Структура диссертации

Диссертация состоит из введения, трех глав, разбитых па разделы, списка литературы и списка публикаций автора по теме диссертации. Общий объем работы составляет 128 страниц. Общий список литературы включает 63 наименования.

Публикации

Результаты диссертации опубликованы в 13 работах автора, их список приведен в конце автореферата [1-13].

Краткое содержание работы

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

В главе 1 вводятся базовые понятия теории полуколец и излагаются основы линеіпюй алгебрі,! с точки зрения полуколец. В разделе 1.2 определяются понятия, обобщающие классические понятия линейной алгебры, такие как линейная зависимость векторов и ранг матрицы. Отмстим, что в связи с различными приложениями возникает необходимость рассмотрения нескольких различных ранговых функций матриц с элементами из полукольца. Среди ранговых функций, изучаемых в нашей работе, функции строчного и столбцового максимальных слабых рангов (обозначаются через Wr и IVc, соответственно). строчного и столбцового рангов Гондрана-Мину (обозначаются через G Л/г и GMc, соответственно), факторизационпого ранга (обозначается через /), дегермипантного ранга, (обозначается через d) и тропического ранга (обозначается черга trop). В разделе 1.3 изучаются обобщения на полукольцевой случай неравенств па ранг произведения, суммы и объединения матриц. А именно, исследуется выполнение условий

если А ® в = С, то CMr{C) < min{GMr(A),GMr{B)}, (1)

если Л © В = С, то GMr(C) < GMr(A) + GMr(B), (2)

если (Л\В) = С, то GMr{C) ^ G AI г (Л) + GMr{B) (3)

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

Теорема 1. (Теорема 1.3.13.) Условия (1)-(3) выполняются для матриц с элементами tus макс-алгебры Ктах-

Теорема 2. (Теорема 1.3.18.) Пусть S — идемпотентпое полукольцо, не содержащее склигпелей пуля. Тогда условия 1) - 4) эквивалентны:

1) условие (1) выполняется для м,атрии, с элементами из S;

2) условие (2) выполняется для матриц с элементами u,s S;

3) условие (3) выполняется для лштриц с элементами из S;

4) полукольцо S является обобщенно-селективным.

Кроме того, приводится пример селективного полукольца, для матриц над которым не выполняются условия (1)-(3).

В раздело 1.4 исслсдуотся взаимное поведение ранговых функций матриц и доказываются неравенства ¿гор(А) ^ у/С'Мг(А), ¿(А) ^ у/СМг(А), Ь-ор(А) ^ дЛЯ матриц над бинарным булевым полукольцом.

Глава 2 посвящена изучению свойств функции ранга Гондрана-Мину тропических матриц. Важным для изучения этой ранговой функции является метод тропических шаблонов матриц, обоснование которого дается в раздело 2.1. В раздело 2.2 иллюстрируются некоторые приложения метода тропических шаблонов. В частности, неравенства ¿гор(А) > ^СМг(А), ¿гор(Л) ^ доказываются для матриц над макс-

алгеброй Етах. Кроме того, в разделе 2.2 исследуется вычислительная сложность функции ранга Гондрана-Мину и доказываются следующие теоремы.

Теорема 3. (Теорема 2.2.11.) Пусть к — фиксированное целое число. Тогда задача распознавания свойства СЛ/г(Л) < к решается за полиномиальное по размеру матрицы А Е Мт^Г оремя.

Теорема 4. (Теорема. 2.2.12.) Пусть Ь - фиксированное целое число. Тогда задача вычисления СМ-ранга матрицы А 6 К^*™ тропического ранга, не. большего £, решается за полиномиальное время.

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

Теорема 5. (Примсі) 2.3.7 и теорема 2.3.14.) Пусть

' 0 -оо О 0 -зо -с О -эо —оо —зо О О

— эо —ос

\

.1 = -зо -зс О О О О

є К;

5x6 'шах*

— зо О 0 —зо 0 —оо

зо 0 —оо 0 —эо О

Тогда СМг(Л) = 5, СМс(А) = 4, СЫг(АТ) = 4, СМс(Ат) = 5. Матрица А содержит минимально возможные среди всех матриц М над 1Ктм числа строк и столбцов при условии <7А4г(Л/") > СМс(М). Матрица АТ содержит минимально возможные среди всех матриц М' над Ешах числа строк и столбцов при условии СМс(М') > СМг(М').

Глава 3 посвящена исследованиям в области тропической алгебраической геометрии. В разделе 3.1 вводятся основные понятия тропической геометрии, которые дают обобщения классических понятии идеала, гиперповерхности и многообразия на тропический случай. В разделе 3.2 определяется понятие ранга Капранова тропической матрицы относительно базового поля Р (обозначается через Кр). Эта ранговая функция имеет непосредственную связь с проблемами тропической алгебраической геометрии, по имеет элементарного описания и поэтому не изучалась в предыдущих разделах. Мы отвечаем па вопрос Чан. Йенсена и Рубеи18, приводя приме]) матрицы размера 6x6с различными тропическим рангом и комплексным рангом Капранова.

Теорема 6. (Пример 3.2.17 и теорема 3.2.18.) Пусть

/0 0 4444\

А =

0 0 2 4 1 4

4 4 0 0 4 4

2 4 0 0 2 4

4 4 4 4 0 0

\ 2 4 1 4 О О

Тогда <;гор(.А) — 4, КС(Л) = 5. Матрица А (-.одержит минимально возможные среди всех тропических матриц М числа строк и столбцов при условии Ьгар{М) ф КС{М).

В разделе 3.3 исследуются арифметические свойства ранга. Капранова, мы показываем, что функция ранга Капранова может принимать на некоторых матрицах меньшее значения, а на некоторых — большее, чем функция ранга Гопдрапа-Мипу. Мы показываем, что матрицы размера 5 х 5 с различными тропическим рангом и рангом Капранова существуют в том и только том случае, если базовое поле содержит не более трех элементов; это даст полное решение проблемы, поставленной Девелином, Сантосом и Штурмфсльсом16. Кроме того, мы изучаем неравенство на ранг Капранова произведения матриц и доказываем следующую теорему.

Теорема 7. (Теорема 3.3.18.) Пусть А е Етхк, В е Ккх". Тогда Кцг(Л ® В) ^ 1шп{Кр(.Д). Кр(В)}, если, поле, Е бесконечно.

Мы приводим примеры, показывающие, что у тверждение предыдущей теоремы перестанет быть верным, если предположить, что Г — некоторое конечное поле.

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

Утверждение 8. (Пример 3.4.17.) Пусть

В =

/ О

0

1 1 1 1 1

О

о

0

1 1 1 1

1 1 о о

0

1 1

0

1 1 1 о

0

1

1 1

0

1 1 о о

\

Тогда 1гор(Л) = 5, КГ(Л) = 6 для любого поля F.

Утверждение 8 позволяет построить контрпример к гипотезе Чан. Йенсе-па и Рубеи о тропическом базисе идеала кольца многочленов, порожденного всеми мигюрамн порядка г матрицы переменных размера йхп.

Теорема 9. (Теорема 3.4.18.) Миноры порядка 6 матрицы переменных размера 7x7 не образуют тропического базиса.

Заключение

Следующие результаты являются основными результатами работы и выносятся на защиту.

1. Решены проблема Штурмфельса, Девелипа и Сантоса (2005 г.) о рангах Капранова тропических матриц размера 5x5, проблема Акяп, Го-бера и Гутермапа (2008 г.) описания минимальных матриц с различными строчным и столбцовым рангами Гондрана-Мину, проблема Чал, Иенсена н Рубеи (2011 г.) описания минимальных матриц с различными тропическим рангом и рангом Капранова; построен контрпример к гипотезе Чан, Йснсена и Р.убеп (2011 г.) о тропическом базисе идеала кольца многочленов, порожденного всеми минорами порядка г матрицы переменных.

2. Разработан быстрый (т.е., работающий за время, ограниченное полиномиальной функцией размера матрицы) алгоритм проверки свойства, равен ли ранг Гондрана-Мину тропической матриц!,I любому наперед заданному числу к.

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

4. Изучены свойства рангов Капранова и Гондрана-Мину произведения матриц. В частности, доказаны классические неравенства для ранга

Гоидрапа-Мипу и ранга Капранова в случае бесконечного базового поля; охарактеризован класс иде.мпотептных полуколец, для матриц над которыми справедливы классические неравенства для ранга Гондрапа-Мипу произведения матриц; доказано, что в случае конечного базового поля классические неравенства для ранга Капранова, вообще говоря, не выполняются.

Благодарность

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

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

1. Я. Шитов, Минимальный пример матрицы, различающей GM- и d-ранги в макс-алгебрах, Фундаментальная и прикладная математика, 14(4)(2008), 231-2G8.

2. Ya. Sliitov, Inequalities for Gondran-Minoux rank and idcinpotent semirings, Linear Algebra AppL, 435(7)(2011). 1709 -1777.

3. Я. Шитов, Пример матрицы размера 6x6с различными тропическим рангом и рангом Капранова, Вестник Моск. Уииа., Сер. 1. Математика. Механика, 66(5)(2011), 58-01.

4. Ya. Sliitov, On the Kapranov ranks of tropical matrices. Linear Algebra AppL, 436(9)(2012), 3247-3253.

5. Я. Шитов, О матрицах с различными тропическим рангом и рангом Капранова, Матем. заметки, 92(2)(2012), 316-320.

6. A. Gutcrman. Ya. Shitov, Tropical patterns of matrices and the Gondran-Minoux rank function, Linear Algebra Appl., 437(7)(2012), 1793-1811.

7. Ya. Sliitov, Tropical matrices and group representations, ./. of Algebra, 370(2012), 1-4.

8. Ya. Sliitov, On tropical matrices of small factor rank, Linear Algebra Appl., 437(2012), 2727-2732.

9. Ya. Sliitov, Mixed subdivisions and ranks of tropical matrices, accepted for publication in Proc. Amcr. Math. Sue.

10. Ya. Shitov, When do the r-by-r minors of a matrix form a tropical basis?, arXiv: 1109.2210, submitted to ./. Combin. Theory Scr. A.

Публикации в сборниках тезисов конференций

11. Ранговые неравенства для матриц над идемпотептпымн полукольцами. Материалы Международного молодежного научного форума "ЛОМОНОС013-20КГ, отв. ред. И. А. Алешковский, П. II. Кос :тылев. А. И. Андреев, А. В. Андриянов. М„ МАКС Пресс, 2010.

12. Когда, миноры порядка г матрицы переменных образуют тропический базис? Материалы Международного молодежного научного форума " JIOMOHOCOD-2011", отв. ред. А. И. Андреев, А. В. Андриянов, Е. А. Ан-тииоп, М. В. Чистякова. М., МАКС Пресс, 2011.

13. When the r-by-r minors of a matrix form a tropical basis? Ill Int. Conf. он Matrix Methods in Mathematics and Applications (MMMA-2011), Moscow, 22-25 June 2011, Book of Abstracts (2011).

Работа [G| написана Я. H. Шитовым в соавторстве с А. Э. Гутермапом. Разделы 1 и 3 этой работы были написаны А. Э. Гутерманом, разделы 2 и 4 принадлежат Я. Н. Шитову.

Подписано в печать 27.08.2012 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 100 экз. Заказ № 1232 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д. 1 Главное здание МГУ, к. А-102

Введение

1 Матрицы над полукольцами и их ранги в общем случае

1.1 Полукольца.

1.1.1 Основные определения и обозначения.

1.1.2 Примеры полуколец.

1.2 Основы линейной алгебры с точки зрения теории полуколец

1.2.1 Линейная зависимость.

1.2.2 Ранги матриц.

1.3 Неравенства с рангами суммы и произведения матриц.

1.3.1 Квазиселективные полукольца без делителей нуля

1.3.2 Полукольца, не являющиеся квазиселективными.

1.3.3 Полукольца с делителями нуля.

1.4 Ранги матриц над бинарным булевым полукольцом.

1.4.1 Ранг Гондрана-Мину и другие ранговые функции

1.4.2 Детерминантный и тропический ранги.

1.4.3 Примеры

2 О ранге Гондрана-Мину тропических матриц

2.1 О ранге тропического шаблона матрицы.

2.2 Некоторые приложения метода тропических шаблонов.

2.2.1 Взаимное поведение ранговых функций.

2.2.2 О вычислительной сложности ранга Гондрана-Мину

2.3 О совпадении рангов Гондрана-Мину матриц малого размера

2.3.1 Примеры матриц, различающих ранговые функции

2.3.2 Пример матрицы размера 5 х 6 с различными строчным и столбцовым рангами.

2.3.3 Доказательство минимальности примера.

3 Тропическая геометрия и ранги матриц

3.1 Основы тропической алгебраической геометрии

3.2 Ранговые функции с точки зрения алгебраической геометрии

3.2.1 Геометрическое описание ранговых функций.

3.2.2 Различие функций тропического ранга и ранга Капранова

3.3 Арифметические свойства ранга Капранова.

3.3.1 Ранг Капранова и другие ранговые функции.

3.3.2 Ранг Капранова над произвольным базовым полем.

3.3.3 О рангах Капранова суммы и произведения матриц

3.4 Представимые матроиды и ранг Капранова.

3.4.1 Основные понятия теории матроидов

3.4.2 Представимость тропических 01-матриц.

Общая характеристика работы

Актуальность темы исследования

Множество <5, на котором заданы бинарные операции сложения и умножения, обозначаемые как фи®, называется полукольцом, если

• 5 — абелев моноид по сложению (нейтральный элемент этого моноида обозначается через 0);

• Б — полугруппа по умножению (нейтральный элемент этой полугруппы, если он есть, обозначается через 1);

• умножение слева и справа дистрибутивно по сложению;

• для любого элемента а; Е <5 верно, что = =

Иными словами, основное отличие полуколец от колец проявляется в том, что не всякий элемент полукольца может быть обратим по сложению. Наиболее простые примеры полуколец, не являющихся кольцами, дают числовые множества: например, целые неотрицательные числа Ъ+ и неотрицательные вещественные числа ®.+ являются полукольцами относительно обычных сложения и умножения. Важные примеры полуколец, не связанных с числовыми множествами, дают дистрибутивные решетки, булевы алгебры; множество всех идеалов заданного кольца также является полукольцом относительно суммы и произведения идеалов. Понятие полукольца было впервые непосредственно введено, вероятно, американским математиком Г. Вандивером в работе [48], посвященной проблемам, связанным с аксиоматизацией натуральных чисел. Впоследствии на протяжении многих лет полукольца изучались многими математиками с различных точек зрения и в связи с различными теоретическими и прикладными задачами.

Подробное описание различных приложений теории полуколец дано в монографии [17]; мы остановимся на описании тех из них, которые наиболее тесно связаны с полученными нами результатами. Одним из важнейших примеров полуколец, рассматриваемых в данной работе, является тропическое полукольцо, т.е. множество К вещественных чисел, пополненное элементом +оо, с операциями минимума и суммы. Значительная часть приложений теории полуколец связана именно с тропическим полукольцом. В первую очередь, мы отмечаем важную его роль для теории оптимизации, поскольку именно различные задачи оптимизации во многом способствовали появлению и разработке тропических методов в математике. Отметим также, что слово "тропический" было предложено Ж.-Э. Пином (см. [45]) в знак признания заслуг математиков бразильской школы. Действительно, своим развитием тропическая математика во многом обязана И. Симону, в работах которого устанавливались ее связи с алгебраической геометрией, теорией полугрупп, теорией оптимизации и некоторыми другими областями, см. [42, 43].

Как одну из основополагающих следует также отметить работу [49] ленинградского математика Н. Н. Воробьева, идеям которого в значительной мере обязано развитие полукольцевого и тропического подходов в различных областях математики и теории оптимизации в частности. Важным шагом в развитии тропических методов в теории оптимизации стали работы английского математика Р. Канингема-Грииа, идеи которого наиболее полно представлены в монографии [11]. Дальнейшее развитие тропические методы получили в работах французских математиков М. Гон драна и М. Мину, в монографии [19] которых описаны методы, ставшие важным инструментом для дальнейших исследований в теории оптимизации. Тропические методы в теории оптимизации активно развиваются и в настоящее время: отметим работы Г. Я. Олсдера, показывающие фундаментальную роль тропических методов в теории расписаний, в частности, монографию [21]. В целом, тропический подход в теории оптимизации основан во многом на том, что многие важные задачи оптимизации, не являющиеся линейными в классическом смысле, принимают линейный вид, если формализовать их с использованием тропической нотации. Иными словами, они сводятся к линейным задачам, таким как решение системы линейных уравнений или вычисление ранга, для матриц над тропическим полукольцом. Этот факт обусловливает важность исследования полуколец и тропического полукольца в особенности с точки зрения линейной алгебры.

Отметим также, что важную роль в развитии тропических методов и их приложений к важным вопросам современной математики сыграли работы академика В. П. Маслова, см. [31, 32]. Для приложений в квантовой физике важную роль играет деквантоваиие Маслова, которое устанавливает связь классической математики над числовыми полями с тропической математикой, см. [29]. Новая область теории вероятности, которая называется идем-потентиым анализом и имеет множество приложений в квантовой физике и квантовой теории вычислений, также основана на работах В. П. Маслова, см. [27].

Несмотря на то, что значительная часть результатов нашей работы связана с тропическим полукольцом, существенное внимание уделено также изучению линейной алгебры над полукольцами в общем случае. Важность изучения свойств матриц над полукольцами в общем случае связана с тем, что самые различные полукольца возникают в различных теоретических и прикладных задачах. Например, множество вещественных чисел отрезка [0,1] является полукольцом относительно операций минимума и максимума и играет фундаментальную роль в нечеткой логике и теории нечетких множеств, см. [16]. В важном разделе теоретической информатики, посвященном проверке корректности компьютерных программ, фундаментальную роль играет формальная алгебраическая система, известная как логика Хоара, см. [22]. Аналогичные способы описания дают динамические алгебры и алгебры Кли-ни, см. [50]. Перечисленные структуры также являются полукольцами, что подтверждает значимость исследования полуколец в общем случае.

Наконец, отметим еще одну область применения методов линейной алгебры над полукольцами. Раздел алгебраической геометрии, известный как тропическая геометрия, появился не так давно, но бурно развивается в настоящее время, см. [9, 10, 14, 44]. Тропическая геометрия рассматривает обобщения классических понятий, таких как многообразия, идеалы, стандартные базисы, на тропический случай. Методы тропической геометрии помогают установить довольно тесную связь тропической линейной алгебры с теорией матроидов, см. [13]. Многие задачи тропической геометрии сводятся к задачам линейной алгебры над тропическим полукольцом, что подтверждает важность изучения тропической геометрии с точки линейной алгебры. Отметим также, что некоторые проблемы тропической геометрии действительно удается решить с помощью методов линейной алгебры, и некоторые из результатов такого рода результатов были получены автором, см. [53, 54].

Цель работы

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

Научная новизна

Полученные в работе результаты являются новыми. Следующие результаты работы являются основными и выносятся на защиту.

• Результаты, описывающие взаимное поведение ранговых функций тропических матриц: приведен пример тропической матрицы минимального размера с различными строчным и столбцовым рангами Гондрана-Мину; это дает решение проблемы Акян, Гобера и Гутермана, поставленной в [1]; доказано, что строчный и столбцовый ранги Гондраиа-Мину матрицы не превосходят квадрата ее тропического ранга; получена оценка, показывающая, что детерминантный ранг матрицы ограничен линейной функцией ее тропического ранга.

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

• Результаты, описывающие функцию ранга Капранова тропических матриц: доказано неравенство на ранг Капранова произведения тропических матриц в случае бесконечного базового поля; в случае конечного базового поля приведен пример матриц, для которых это равенство нарушается; приведен пример тропической матрицы минимального размера с различными комплексным рангом Капранова и тропическим рангом; это дает решение проблемы Чан, Йенсена и Рубеи, поставленной в [10].

Основные методы исследования

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

Теоретическая и практическая значимость

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

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

Результаты диссертации неоднократно докладывались па научно-исследовательском семииаре кафедры высшей алгебры механико-математического факультета МГУ, на семинарах "Кольца и модули" и "Теория матриц" механико-математического факультета МГУ. Также результаты докладывались на следующих семинарах и конференциях:

• XVII Международная конференция студентов, аспирантов и молодых ученых " Ломоносов", Москва, 2010;

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

• XVIII Международная конференция студентов, аспирантов и молодых ученых "Ломоносов", Москва, 2011;

• Международная конференция по матричным методам в математике и приложениях "МММА-2011", Москва, 2011;

• Научная конференция "Ломоносовские чтения", Москва, 2011;

• семинар "Гомологические и гомотопические методы в геометрии", Национальный исследовательский университет Высшая школа экономики, Москва, 2012;

• XIX Международная конференция студентов, аспирантов и молодых ученых "Ломоносов", Москва, 2012;

• International conference " Future Directions in Tropical Mathematics and its Applications", Manchester, 2012.

Структура диссертации

Диссертация состоит из введения, трех глав, разбитых на разделы, списка литературы и списка публикаций автора по теме диссертации. Общий объем работы составляет 126 страниц. Общий список литературы включает 63 наименования. Список публикаций автора по теме диссертации составляет 13 наименований.

1. M. Akian, S. Gaubcrt, A. Gutcrman, Linear independence over tropical semirings and beyond, Contemporary Mathematics, AMS, 495(2009), 1-38.

2. M. Akian, S. Gaubert, A. Guterman, Tropical polyhedra are equivalent to mean payoff games, arXiv:0912.2462.

3. F. Baccelli, G. Cohen, G.J. Olsder, J.P. Quadrat, Synchronization and Linearity, Wiley, 1992.

4. A. Barvinok, D. S. Johnson, G. J. Woeginger, The maximum traveling salesman problem under polyhedral norms, Integer programming and combinatorial optimization, Lecture Notes in Comput. Sci, 1412, 195-201. Springer, Berlin, 1998.

5. L. B. Beasley, A. E. Guterman, Rank inequalities over semirings, J. Korean Math. Soc. 42(2)(2005), 223-241.

6. L. B. Beasley, N. J. Pullman, Semiring rank versus column rank, Linear Algebra Appl, 101(1988), 33-48.

7. R. Bieri, J. R. J. Groves, The geometry of the set of characters induced by valuations, J. Reine Angew. Math., 347(1984), 168-195.

8. J. E. Blackburn, H. H. Crapo, and D. A. Higgs, A catalogue of combinatorial geometries, Mathematics of Computation, 27(121)(1973), 155-195.

9. T. Bogart, A. N. Jensen, D. Speyer, B. Sturmfels, R. R. Thomas, Computing tropical varieties, J. Symh. Comp., 42(l-2)(2007), 54-73.

10. M. Chan, A. N. Jensen, E. Rubei, The 4x4 minors of a 5xn matrix are a tropical basis, Linear Algebra Appl, 435(7)(2011), 1598-1611.

11. R. A. Cuninghamc-Grcen, Minimax Algebra, Lccturc Notes in Economics and Mathematical Systems, 166, Springer-Verlag, Berlin, 1979.

12. R. Dedekind. Uber die Theorie der ganzen algebraischen Zahlen, Supplement XI to P.G. Lejeune Dirichlet, Vorlesungen ber Zahlentheorie, 4te Aufl. Druck und Verlag, Braunschweig, 1894.

13. M. Develin, F. Santos, B. Sturmfels, On the rank of a tropical matrix, Discrete and Computational Geometry (E. Goodman, J. Pach and E. Welzl, eds.), MSRI Publications, Cambridge Univ., Press, 2005, 213-242.

14. M. Develin, B. Sturmfels, Tropical convexity, Documenta Math. 9(2004), 1-27.

15. M. Einsiedler, M. Kapranov, D. Lind. N on-Archimedean amoebas and tropical varieties, J. Reine Angew. Math., 601(2006), 139-157.

16. J. Goguen, The logic of inexact concepts, Synthese, 19(1968/9), 325-373.

17. J. S. Golan, Semirings and their applications, Kluwer Acad. Publ., Dordrecht, 1999.

18. M. Gondran, M. Minoux. L'independance lineaire dans les dioides, E.D.F. — Bulletin de la Direction des Etudies et Recherches, Serie C — Mathematiques, Informatique 1(1978), 67-90.

19. M. Gondran, M. Minoux, Graphs and Algorithms, Wiley-Interscience, New York, 1984.

20. M. Gondran, M. Minoux. Graphs, Dioids and Semirings: New Models and Algorithms, Springer Science eBusiness Media, LLC, 2008.

21. B. Heidergott, G. J. Olsder, J. van der Woude. Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max- Plus Algebra and Its Applications, Princeton Univ. Press, 2006.

22. C. A. R. Hoare, An axiomatic basis for computer programming, Comm. ACM, 12(1969), 576-580.

23. Z. Izhakian, Basics of linear algebra over the extended tropical semiring, Contemp. Math495(2010), 173-191.

24. M. Johnson, M. Kambites, Green's J-order and the rank of tropical matrices, arXiv:1102.2707vl.

25. К. H. Kim, N. F. Roush, Kapranov rank vs. tropical rank, Proc. Amer. Math. Soc. 134(9)(2006), 2487-2494.

26. V. Klee, R. Ladner, and R. Manber. Sign-solvability revisited, Linear Algebra Appl., 59(1984), 131-158.

27. V. N. Kolokol'tsov, V. P. Maslov, Idempotent Analysis and Applications, Kluwer, Dordrecht, 1997.

28. А. Г. Курош, Лекции по общей алгебре, 2-е изд., Москва, Наука, 1973.

29. Г. Л. Литвинов, Деквантованис Маслова, идемпотентная и тропическая математика: краткое введение, Теория представлений, динамические системы, комбинаторные и алгоритмические методы, XIII, Зап. научн. сем. ПОМИ, 326, ПОМИ, СПб., 2005, 145-182.

30. G. Litvinov, V. Maslov, Correspondence principle for idempotent calculus and some computer applications, Idempotency, J. Gunawardena (ed.), Cambridge University Press, Cambridge, 1998, 420-443.

31. В. П. Маслов, О новом принципе суперпозиции для задач оптимизации, УМЕ, 42:3(255)(1987), 39-48.

32. V. P. Maslov, S. N. Sambourskii, Idempotent Analysis, Advances in Soviet Mathematics, 13, Amer. Math. Soc., Providence, R.I., 1992.

33. G. Mikhalkin, Amoebas of algebraic varieties and tropical geometry, Different faces of geometry, Int. Math. Ser. (N. Y.), 3, Kluwer, Plenum, New York, 2004, 257-300.

34. H. Mine, Permanents, Addison-Wesley, Reading, 1978.

35. J. G. Oxley, Matroid Theory, Oxford University Press, New York, 1992.

36. L. Pachtcr, B. Sturmfels, Algebraic Statistics for Computational Biology, Cambridge Univ. Press, Cambridge, 2005.

37. J.-E. Pin, Tropical semirings, Idempotency, Publ. Newton Inst., 11, Cambridge Univ. Press, Cambridge, 1998, 50-69.

38. B. Poonen, Maximally complete fields, Enseign. Math., 39(1-2)(1993), 87106.

39. P. L. Poplin, R. E. Hartwig. Determinantal identities over commutative semirings, Linear Algebra Appl, 387(2004), 99-132.

40. O. A. Pshenitsyna, Factor and term ranks for matrix union over a semiring, Fundam. Prikl. Mat., 9(3)(2003), 175-197.

41. J. Richtcr-Gebert, B. Sturmfels, T. Theobald, First steps in tropical geometry, Contemporary Mathematics, AMS, 377(2004), 1-38. 289-318.

42. I. Simon, Limited Subsets of a Free Monoid, in: Proc. 19th Annual Symposium on Foundations of Computer Science, Piscataway, N.J., Institute of Electrical and Electronics Engineers, pp. 143-150.

43. I. Simon, Recognizable sets with multiplicities in the tropical semiring. Mathematical foundations of computer science, Lecture Notes in Comput. Sci., 324, Springer, Berlin, 1988, 107-120.

44. D. Speyer, B. Sturmfels, The tropical grassmanian, Adv. Geom. 4(2004), 389-411.

45. D. Speyer, B. Sturmfels, Tropical Mathematics, Mathematics Magazine, 82(3)(2009), 163-173.

46. C. Thomassen. Sign-nonsingular matrices and even cycles in directed graphs, Linear Algebra Appl, 75(1986), 27-41.

47. C. Thomassen. The Even Cycle Problem for Directed Graphs, J. Amer. Math. Soc., 5(1992), 217-229.

48. H. S. Vandiver, Note on a simple type of algebra in which cancellation law of addition does not hold, Bull Amer. Math. Soc., 40(1934), 914-920.

49. N. N. Vorobycv, Extremal algebra of positive matrices, Elektron. Informationsverarbeitung und Kybernetik, 3(1967), 39-71.

50. Я. Шитов. Минимальный пример матрицы, различающей GM- и d-ранги в макс-алгебрах, Фундаментальная и прикладная математика, 14(4)(2008), 231-268.

51. Ya. Shitov, Inequalities for Gondran-Minoux rank and idempotent semirings, Linear Algebra Appl, 435(7)(2011), 1769-1777.

52. Я. Шитов, Пример матрицы размера 6x6с различными тропическим рангом и рангом Капранова, Вестник Моск. У нив., Сер. 1. Математика. Механика, 66(5)(2011), 58-61.

53. Ya. Shitov, On the Kapranov ranks of tropical matrices, Linear Algebra Appl., 436(9)(2012), 3247-3253.

54. Я. Шитов, О матрицах с различными тропическим рангом и рангом Капранова, Матем. заметки, 92(2) (2012), 316-320.

55. A. Guterman, Ya. Shitov, Tropical patterns of matrices and the Gondran-Minoux rank function, Linear Algebra Appl, 437(7)(2012), 1793-1811.

56. Ya. Shitov, Tropical matrices and group representations, J. of Algebra, 370(2012), 1-4.

57. Ya. Shitov, On tropical matrices of small factor rank, Linear Algebra Appl., 437(2012), 2727-2732.

58. Ya. Shitov, Mixed subdivisions and ranks of tropical matrices, acccpted for publication in Proc. Amer. Math. Soc.

59. Ya. Shitov, When do the r-hy-r minors of a matrix form a tropical basis?, arXiv:1109.2240, submitted to J. Combin. Theory Ser. A.Публикации в сборниках тезисов конференций

60. Я. Шитов, Ранговые неравенства для матриц над идемпотентными полукольцами. Материалы Международного молодежного научного форума "JIOMOHOCOB-2010", отв. ред. И. А. Алсшковский, П. Н. Костылев, А. И. Андреев, А. В. Андриянов. М., МАКС Пресс, 2010.

61. Я. Шитов, Когда миноры порядка г матрицы переменных образуют тропический базис? Материалы Международного молодежного научного форума " JIOMOHOCOB-2011", отв. ред. А. И. Андреев, А. В. Андриянов, Е. А. Антипов, М. В. Чистякова. М., МАКС Пресс, 2011.

62. Ya. Shitov, When the r-by-r minors of a matrix form a tropical basis? Ill Int. Conf. on Matrix Methods in Mathematics and Applications (MMMA-2011), Moscow, 22-25 June 2011, Book of Abstracts (2011).