Ранговые функции матриц над полукольцами тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Шитов, Ярослав Николаевич

• Шитов, Ярослав Николаевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Шитов, Ярослав Николаевич

Введение

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 наименований.

Список литературы диссертационного исследования кандидат физико-математических наук Шитов, Ярослав Николаевич, 2012 год

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).