Идемпотентные аналоги теорем отделимости и образующие идемпотентных полумодулей тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Сергеев, Сергей Николаевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2008
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
Московский государственный университет имени М В. Ломоносова Механико-математический факультет
На правах рукописи УДК 512 553+512 56
Сергеев Сергей Николаевич
ИДЕМПОТЕНТНЫЕ АНАЛОГИ ТЕОРЕМ ОТДЕЛИМОСТИ И ОБРАЗУЮЩИЕ ИДЕМПОТЕНТНЫХ ПОЛУМОДУЛЕЙ
01 01 06 — математическая логика, алгебра и теория чисел
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
Москва - 2008
Работа выполнена на кафедре высшей алгебры Механико-математического факультета Московского государственного университета имени М В Ломоносова
Научный руководитель
Официальные оппоненты
Ведущая организация
академик РАН, профессор Виктор Павлович Маслов
доктор физико-математических наук, профессор Игорь Борисович Кожухов
доктор физико-математических наук, профессор Аскар Аканович Туганбаев
Тульский государственный педагогический университет им Л Н Толстого
Защита диссертации состоится 18 апреля 2008 г в 16 ч 40 мин на заседании диссертационного совета Д 501.001 84 в Московском государственном университете имени М В. Ломоносова по адресу 119991, Российская Федерация, Москва, ГСП-1, Ленинские горы, Московский Государственный Университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08
С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ имени М В Ломоносова (Главное здание, 14 этаж)
Автореферат разослан 18 марта 2008 г
Ученый секретарь диссертационного совета Д 501 001 84 в МГУ доктор физико-математических наук, профессор
АО Иванов
Общая характеристика работы Актуальность темы
При решении ряда задач в теории оптимизации (проблемы оптимизации на графах, теория оптимального управления, дискретные системы событий, сети Петри), в физике (теория обобщенных решений уравнения Гамильтона-Якоби, низкотемпературная асимптотика в статистической физике), в алгебраической геометрии и в других областях явно или неявно используется линейность по отношению к операции "сложения" ф, которая является идемпо-тентной (а®а = в) Этот общий принцип, сформулированный академиком В П Масловым1'2 для ряда задач теории оптимизации и теории нелинейных систем, во многом определяет развитие новой области математики, которая получила название идемпотентная математика. Многие интересные результаты, полученные в этой области, содержатся в сборнике статей3 В практически важных задачах, для решения которых используется идемпотентная математика, роль идемпотентного сложения часто играет операция взятия минимума или максимума двух элементов, а основной алгебраической структурой является некоторое идемпотентное полуполе Например, полуполе RmaX)X, определяемое как множество неотрицательных чисел снабженное операцией идемпотентного сложения ф = max и обычного умножения © = х, или изоморфное ему полуполе Мтах, определяемое как множество чисел К U {—оо} с операциями ф = шах и О = +
Основные приложения идемпотентной математики связаны с задачами оптимизации Одно из первых таких приложений было описано в работах Б А. Kappe 4,5 В этих работах замечено, что метод исключения Гаусса без выбора ведущего элемента можно рассматривать как прототип для оптимизационных алгоритмов на графах и применять для решения систем линейных уравнений над широким классом полуколец. Главный объект в этих работах — это ряд I ф А ф А2 ф. , где А — это некоторая квадратная матрица с элементами из идемпотентного полукольца, являющийся очевидным аналогом операции (I — А)-1 и называемый алгебраическим замыканием А Эти идеи получили свое дальнейшее развитие в работах Г.Л Литвинова, В П Маслова
lV Р Maslov New superposition principle for optimization problems // Séminaire sur les Equations aux Dérivées Partielles 1985/86, Centre Math de l'Ecole Polytechnique, Palaaseau (1986), exposé 24
2BII Маслов Новый подход к обобщенным решениям нелинейных систем // ДАН СССР, том 292, №1, стр 37-41,1987
3G Ь Litvinov and V Р Maslov, eds Idempotent Mathematics and Mathematical Physics VoL 377 of Contemporary Mathematics American Mathematical Society, Providence, 2005
4B A Carré An algebra for network routing problems // J of the Inst of Maths and Applies, vol 7, p. 273-299, 1971
5B A Carré Graphs and Networks Clarendon Press, Oxford, 1979
и др 6'7, посвященных универсальным алгоритмам линейной алгебры
Другие задачи линейной алгебры над идемпотентными полуполями, в частности, решение систем вида Ах = Ь и нахождение собственных значений и собственных векторов Ах = Хх, возникают в связи с составлением расписаний, синхронизацией производства и сетями Петри8,9,10 Такие приложения возникают и в физике В качестве примера, рассмотрим модель Френкеля-Конторовой В простейшем варианте это одномерная цепочка атомов, находящихся в периодическом потенциале При статическом описании этой модели задача заключается в нахождении основных состояний и значений параметров, которые характеризуют эти состояния Алгоритм для нахождения основных состояний был предложен У Чоу и Р Б Гриффитсом,11 которые использовали для этого собственные векторы и собственные значения некоторого интегрального оператора над идемпотентным полуполем Метод Чоу и Гриффитса был использован в ряде физических задач 12'13 Близкие по математическому описанию задачи возникают и в математической экономике, а именно, в задачах динамической оптимизации с бесконечным горизонтом, где требуется найти траектории, приносящие максимальный доход14
В связи с этими практическими приложениями, возникает интерес к теории идемпотентных полуколец и полуполей, и к теории полумодулей (те "пространств") над этими полукольцами Значительная часть этих результатов собрана в монографии Дж. Голана15 Отметим, что линейная алгебра над идемпотентными полукольцами (и над полукольцами вообще) отличается тем, что в ней есть много способов определить, что такое линейная незаг висимость, ранг и определитель, и в связи с этим возникает много новых нетривиальных задач 16
Идемпотентный анализ был развит в работах В П Маслова и его сотрудников Основной объект идемпотентного анализа В П Маслова — это полумо-
eG L Litvmov, V Р Maslov, and A Ya Rodionov Unifying approach to software and hardware design for scientific calculations // Intern Sophus Lie Centre, Moscow, 1995 E-prmt arXtv quant-ph/9904024
7G L Litvmov and Б V Maslova. Universal numerical algorithms and their software implementation // Programming and Computer Software, vol 26, no 5, p 275-380, 2000 E-prmt arXiv math NA/010S144
8R A Curunghame-Green Mmtmax Algebra Springer, Berlin, 1979
9F L Baccelli, G Cohen, G J Olsder, and J P Quadrat Synchronization and Linearity Wiley, Chichester, New York, 1992
10B Heidergott, G -J Olsder, and J van der Woude Max-plus at work. Princeton Umv Press, 200S
nW ChouandRB Griffiths Ground states of one-dimenstonal systems using effective potentials //Physical Review B, vol 34, p 6219-6234, 1986
12 J J Mazo, F Falo and L M Florfa Josephson junction ladders ground state and relaxation phenomena // Physical Review B, vol 52, p 10433-10440,1995
13C Micheletti, R.B Griffiths, and J M Yeomans Surface spin-flop and discommensuration transitions tn antiferromagnets Physical Review B, vol 59, p 6239-6249,1999
14B П Маелов и В H Колокольцов Идемпотентный анализ и его применение в оптимальном управлении М Наука, 1994
15J Golan Semtrmgs and their applications Kluwer, Dordrecht, 2000
16A E Guterman Rank and determinant functions for semirings // London Mathematical Society Lecture Notes, vol 347, p 1-33, 2007
дуль полунепрерывных функций на некотором топологическом пространстве, принимающих значение в некотором идемпотентном полукольце17'18,19 В цитированных работах была развита теория идемпотентных мер, интегралов, обобщенных функций и идемпотентно линейных операторов) Эти результаты были использованы для построения обобщенных решений уравнения Беллмана, а также в упоминавшихся выше задачах динамической оптимизации с бесконечным горизонтом В работах Г.Л Литвинова, В П Маслова и Г Б Шпиза20'21 развит алгебраический подход к идемпотентному анализу Этот подход отличается тем, что в нем основные топологические понятия и результаты моделируются на чисто алгебраическом уровне, с привлечением результатов теории решеток и решеточно упорядоченных групп
Большую роль в развитии идемпотентной математики играет эвристический принцип соответствия,22 родственный известному принципу соответствия H Бора у многих интересных конструкций и результатов "традиционной" математики над полями должны быть интересные идемпотентные аналоги В частности, это касается идемпотентного аналога выпуклой геометрии, развитию которого посвящена данная диссертация Один из первых результатов в этом направлении получил К Циммерманн23 В его работе рассмотрены выпуклые множества в конечномерных полумодулях над Ктах и доказана теорема об отделимости точки от замкнутого идемпотентно выпуклого множества Обобщения этого результата расматриваются в работе С.Н Самборского и Г Б Шпиза24 (на полумодули функций над идемпотент-ными полуполями), а также в работах Г Коэна, С. Гобера, Ж-П Квадра и И. Зингера 25 Изучению этого типа выпуклости также посвящена работа M Девелина и Б Штурмфельса 26 В этой работе развивается другой подход к
17В П Маслов Асимптотические методы решения псевдодифференциальных уравнений M Наука, 1987
18V Р Maslov and S N Samborskiï, eds Idempotent analysis, vol 13 of Advances in Soviet Math American Mathematical Society, Providence, 1992
ieV N Kolokoltsov and V P Maslov Idempotent analysts and applications Kluwer Acad Publ, Dordrecht et al, 1997
МГ J1 Литвинов, В П Маслов и Г Б Шпиз Линейные функционалы на идемпотентных пространствах алгебраический подход // Доклада РАН, том 363, Ш, стр 298-300,1998
21Г Л Литвинов, В П Маслов и Г Б Шпиз Тензорные произведения идемпотентных полумодулей Алгебраический подход // Мат Заметки, том 65, №4, стр 572-585,1999
S2G L Litvmov and V P Maslov Correspondence principle for idempotent calculus and some computer applications // J Gunawardena (Ed ), Idempoteney, Publications of the I Newton Institute, pages 420-443 Cambridge Umv Press, 1998
23K Zimmermann A general separation theorem m extremal algebras // Ekonomicko-matematicky obzor, vol 13, no 2, 1977, p 179-201
24S N Samborskiï and G В Shpiz Convex sets m the semimodule of bounded functions //VP Maslov and S N Samborskiï, eds Idempotent analysis, pages 135-137. AMS, Providence, 1992
2SG Cohen, S Gaubert, J P Quadrat, and I Smgei Max-plus convex sets and functions // G Litvmov and V Maslov, eds Idempotent mathematics and mathematical physics, pages 105-129 AMS, Providence, 2005 E-prmt arXiv math FA/0308166
2eM Develin and В Sturmfels Tropical convexity // Documenta Math, vol 9, 2004, p 1-27 E-print
идемпотентной выпуклости, в основе которого лежит разложение свободного полумодуля, элементами которого являются некоторые выпуклые (в обычном смысле) области, то есть клетки Отметим, что важную роль в этих работах играют проекторы на идемпотентные полумодули, имеющие много общего с ортогональными проекциями на выпуклые множества Композиции этих проекторов, исследуемые в данной диссертации и называемые здесь циклическими проекторами на идемпотентные полумодули, также используются для нахождения точки, лежащей в пересечении нескольких полумодулей27
Абстрактные версии теорем отделимости, а также результаты, касающиеся соотношений между числами Хелли, Радона и Каратеодори, известны в аксиоматической теории выпуклости 28 В частности, известны теоремы отделимости двух непересекающихся обобщенно выпуклых множеств с помощью двух дополняющих друг друга полупространств 29 Существует также много других обобщений и аналогов теории выпуклости, актуальных в настоящее время в связи с приложениями в математической экономике30
Основное затруднение при построении идемпотентного аналога выпуклой геометрии состоит в том, что доказательства многих теорем выпуклой геометрии не переносятся тривиальным образом на исследуемый случай Например, в обычном выпуклом анализе можно легко показать, что два выпуклых множества А к В отделяются друг от друга тогда и только тогда, когда точка О отделяется от разности А — В, однако в идемпотентной математике нет операции вычитания и идемпотентный аналог разности А — В оказывается слишком "слабым" Похожие трудности возникают и в случае теоремы Мин-ковского о крайних элементах замкнутых выпуклых множеств Преодоление этих трудностей — основной стимул данной работы
Цель работы
Цель работы — исследовать аналог выпуклой геометрии в полумодулях над идемпотентными полуполями, в частности, получить новые аналоги некоторых известных теорем конечномерной выпуклой геометрии
arXivmath MG/0308254
27RA Cunmghame-Green and P ButkoviC The equation A ® x = В ® у over (max,+) // Theoretical Computer Science, vol 293, 2003, p 3-12
28B П Солтан Введение в аксиоматическую теорию выпуклости Кишинев, Штиилца, 1984
29V Chepoi Separation of two convex sets m convexity structures //J of Geometry, vol 50,1994, p 30-51
30 A Eberhard, N Hadjisawas and DT Luc, eds Generalized convexity, generalized monotonictty and applications. Vol 77 of Nonconvex Optimization and Its Applications, Springer, 2006
Методы исследования
В работе используются методы линейной алгебры над идемпотентными полукольцами, а также элементы теории решеток и теории неотрицательных матриц и операторов
Научная новизна
Основные результаты диссертации являются новыми и состоят в следующем
1 Получена теорема отделимости нескольких замкнутых полумодулей и, как следствие этой теоремы, идемпотентный аналог теоремы Хелли,
2 Получена теорема, характеризующая спектр циклических проекторов в терминах некоторого обобщения проективной метрики Гильберта;
3 Получен идемпотентный аналог теоремы Минковского,
4 В связи с клеточным разложением свободного полумодуля, описаны перенормировки операции алгебраического замыкания, определенные для широкого класса квадратных и прямоугольных матриц
Теоретическая и практическая ценность
Диссертация носит теоретический характер Результаты, полученные в ней, могут быть полезны для дальнейшего изучения идемпотентно выпуклой геометрии и теории полумодулей над идемпотентными полукольцами
Апробация результатов
1 Международная конференция "II International Conference on Matrix Methods and Operator Equations" Москва, Институт Вычислительной Математики РАН, 23-27 июля 2007 года
2 Международная конференция "Idempotent and tropical mathematics and problems of mathematical physics" Москва, Независимый Московский Университет, 25-30 августа 2007 года
3. Международная конференция "Геометрия в Астрахани" Астрахань, АГУ, сентябрь 2007 года
4 Семинар "Кольца и модули" Руководители проф А В Михалев, В Н.Латышев, В А Артамонов, Е С Голод, В К Захаров, доц В.Т Марков и А Э.Гутер-ман. Москва, МГУ им М В Ломоносова, октябрь 2007 года
Публикации
Основные результаты диссертации опубликованы в пяти работах автора Список работ приведен в конце автореферата [1-5]
Структура и объем работы
Диссертация состоит из введения и трех глав. Текст диссертации изложен на 71 странице Список литературы включает 85 наименований
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении изложена краткая история исследуемого вопроса, показана актуальность темы и сформулированы основные результаты диссертации
Первая глава
В первой главе получены основные результаты по теоремам отделимости и циклическим проекторам в идемпотентных полумодулях, полученные в статье [3] Напомним некоторые факты, касающиеся роли отношения порядка в идемпотентных полуполях и полумодулях, а также об идемпотентном аналоге выпуклости.
Рассматривается полумодуль V над полуполем К, с идемпотентным сложением ф Нуль полуполя и нуль полумодуля обозначаются 0, единица полуполя обозначается 1 Сложение © задает порядок < в полукольце 1С по правилу \ ® [л = /л \ < [I для А, ц € К, причем Л Ф /х = зир(Л, ц) (по отношению <) Идемпотентная сумма элементов произвольного множества определяется как точная верхняя грань этого множества, если таковая существует Отношение порядка с аналогичными свойствами определяется и в полумодуле, его мы также обозначаем < Так как любой элемент полуполя или полумодуля неотрицателен по этому отношению, то подполумодули V можно рассматривать как аналоги выпуклых конусов неотрицательного ор-танта Эта точка зрения согласована со следующим идемпотентным аналогом выпуклости. Дадим следующее хорошо известное определение
Определение 1 Множество С С V называется идемпотентно выпуклым, если \х@ цу € С для любых х,у £ С к таких А, Ц € /С, что А ф /л — 1
Полукольцо или полумодуль называются Ъ-полными, если они замкнуты относительно взятия сумм (т е точных верхних граней) любых подмножеств, ограниченных сверху, и если умножение дистрибутивно относительно любых таких сумм Если можно брать точные верхние грани ф ограниченных сверху
множеств, то можно брать и точные нижние грани Л множеств, ограниченных снизу Следовательно, в ¿^полном полукольце или полумодуле можно брать точные нижние грани любых подмножеств, так как все подмножества ограничены снизу нулем О
Далее мы будем считать, что полукольцо К и полумодуль V над К. удовлетворяют следующим условиям
(АО), полукольцо /С является Ь-полным идемпотентным полуполем, а полумодуль V является Ь-полным полумодулем над ¡С,
(А1) для любых элементов х и у ф О из V, множество {А 6 К. | Ху < х} ограничено сверху
Эти предположения справедливы для многих полумодулей, рассматривающихся в идемпотентном анализе Например, для полумодулей ЬБС{Х) полунепрерывных снизу функций на топологическом пространстве X, принимающих значение в некотором Ь-полном полуполе (Ктах,х) Из предположений (АО, А1) вытекает, что операция
х/у = тах{А € /С | А у < х}.
определена для всех х и всех у ф О из V. Следующее определение хорошо известно
Определение 2 Назовем подполумодуль V полумодуля V Ь-(под)полумоду-лем, если У замкнут относительно взятия сумм любых своих подмножеств, ограниченных сверху в V
Пусть V — это Ь-подполумодуль полумодуля V Рассмотрим оператор Ру, определенный по известной формуле
Ру(х) = тах{ы б V | и < х},
для любого элемента х € V- Мы пишем "тах", подчеркивая, что точная верхняя грань множества в фигурных скобках принадлежит этому множеству. Оператор Ру является проектором на подполумодуль V, так как Ру(х) € V для любого х € V и Ру(у) € V для любого V € V
Роль полупространства играет следующий известный объект
Определение 3 Множество Н, определенное с помощью
Н = {х | и/х > и/х} и {0}
где и, V € М^д^ х, и < V, называется (идемпотентным) полупространством.
Если V — Кп и все координаты и и V ненулевые, то
Н — {х\ ф х%и;1 < ф ж,«,-1},
{1, ,п} {1, ,»}
то есть Н — это аналог замкнутого однородного полупространства
Следующий результат близок к известной теореме отделимости точки от полумодуля31 Его также можно рассматривать как следствие теоремы о представлении идемпотентно линейных функционалов.32
Предложение 1 Пусть V С V — это Ь-полумодуль и пусть и $ V Тогда полупространство
Я = {х\ Pv(u)/x > и/х} U {0} содержит V и не содержит и.
Если Vi,. .,14 — это 6-полумодули, то можно определить циклический проектор Pk-- Pi, где через Рг обозначен проектор на полумодуль Vt
Определяемое ниже понятие архимедовости является упрощенной версией того, что используется в идемпотентном функциональном анализе33
Определение 4 Вектор х € V назовем архимедовым, если х/у > 0 для всех у 6 V Подполумодуль V С V назовем архимедовым, если он содержит хотя бы один архимедов вектор Полупространство будет называться архимедовым, если оба определяющих вектора архимедовы
Заметим, что в полумодулях Кп, где К — это идемпотентное Ь-полное полуполе, архимедовы векторы — это в точности те векторы, все координаты которых положительны. Другой пример полумодуля, имеющего архимедовы векторы — это полумодуль полунепрерывных функций на некотором компакте Если полумодуль V удовлетворяет (ЛО, Al) и имеет архимедовы векторы, то справедлива следующая теорема, полученная автором-
Теорема 1 Пусть у оператора P¡¡ ■ Р\ есть архимедов собственный вектор у с ненулевым собственным значением А Следующие условия эквивалентны
1. существует такой архимедов вектор х, что Pk • • Р\х < цх для некоторого ß <1.
2 для любого г — 1,.. , к существуют такие архимедовы полупространства Нг, что V,C Нг и ntff, = {0},
3. r\vt = {0},
31G. Cohen, S Gaubert, and J P Quadrat Duality and separation theorems in idempotent semimadvles // Linear Algebra Appl, vol 379, 2004, p 395-422 E-pnnt arXivmath FA/0212394
32ГЛ Литвинов, В П МасяовиГБ Шлю Идемпотентный функциональный анализ Алгебраический подход // Матем. Заметки, том 69, №5, 2001, сгр 758-797 E-pnnt (English) arXtvmath FA/0009128
33ГБ. Шпиз Теорема о существовании собственных векторов в идемпотентном анализе // Матем Заметки, том 82, №3, 2007, стр 459 - 468
4 А < 1
В общем случае удается также получить следующий результат, касающийся спектра циклических проекторов
Определение 5 Пусть Ух, .., 14 — это Ь-подполумодули V Величину с1н(Уъ вир (х'/х2) О (х2/х3) О О (хк/х1)
х'еЦ, ,хкеУк
назовем гильбертовым значением полумодулей , У^
Теорема 2 Пусть 14, ., 14 — зто Ь-подполумодули, и у оператора Рк • • Р\ есть архимедов собственный вектор у с ненулевым собственным значением А. Тогда это собственное значение совпадает с гильбертовым значением полумодулей Уь . ,14, причем на векторах х1,. ,хк, где х* — Рг- • Р\у, достигается максимум в определении гильбертова значения
Рассмотрим теперь случай V = К^ах х- В Ж^^х естественно рассматривать полумодули, замкнутые в евклидовой топологии. Можно показать, что такие полумодули являются 6-полумодулями и что проектор на такой полумодуль непрерывен (в обычном смысле) Как и в общем случае, проектор является также однородным и изотонным оператором Если Р — оператор, обладающий такими свойствами, то у него есть собственные значения, их конечное число, и спектральный радиус равен
р(Р) = тах{А € К+ | Зх € (Ж£) \ 0, Рх = Аа;} .
Справедливо также следующее нелинейное обобщение формулы Коллатцаг Виландта для спектрального радиуса неотрицательной матрицы 34
Предложение 2 Пусть Р Ж" —■> Ж" — это изотонный, однородный и непрерывный оператор Тогда
р(Р)= нй тах ^(а;)]^"1
Применимость этих результатов к циклическим проекторам позволяет усилить результаты для общего случая Сформулируем общую теорему отделимости для подполумодулей в Ж^^х
Теорема 3 Пусть Уь ..,14 — это замкнутые архимедовы полумодули в ®шах,х. Следующие утверждения эквивалентны:
MR D Nussbaum Convexity and log convexity for the spectral radius // Linear Algebra Appl, vol. 73,1986, p 59-122
1 существуют положительный вектор х и число Л < 1, такие, что Рк --Рхх< \х,
2. существуют архимедовы полупространства Н%, содержащие и такие, что = {О},
3 П,*=1К = {О},
4. р(Рк ■ -Р1)< 1
Условия 2 и 3 эквивалентны и в том случае, когда архимедовость 14, , 14 не предполагается
Эквивалентность условий 2 и 3. в этой теореме — это утверждение об отделимости нескольких полумодулей Далее, в случае К^щ^х удается полностью охарактеризовать собственные значения циклических проекторов Введем обозначение
Vм = {х € У | эирр(х) С М}, где М — произвольное подмножество {1, , п}
Теорема 4 Пусть Ц, , 14 — это замкнутые полумодули в х Тогда гильбертово значение 14, ,14 — это спектральный радиус Рк • Р\ Спектр Рк Р\ — это множество гильбертовых значений • , У/^),
где М пробегает все подмножества {1, ,п}
Еще одним следствием теоремы об отделимости нескольких полумодулей является идемпотентный аналог теоремы Хелли.
Теорема 5 (Теорема Хелли) Пусть С„ г ~ 1, ,т — это совокупность т > п + 1 идемпотентно выпуклых множеств в К^^х Если любые п + 1 из них пересекаются, то и вся совокупность в целом имеет непустое пересечение
Вторая глава
Во второй главе изложены результаты, касающиеся образующих и крайних точек подполумодулей К^ш^х, полученные автором в статье [4].
Будем говорить, что идемпотентный полумодуль V порождается множеством Э, если V является множеством конечных линейных (в смысле операций фи©) комбинаций элементов из 5 Следующее определение также хорошо известно
Определение 6 Элемент х идемпотентного полумодуля V называется крайним, если из х = и ф V следует, что х — и или х — V.
Следующее определение дано автором диссертации
Определение 7 Рассмотрим отношение предпорядка
у <3 х х3 ф 0, у3 ф 0, у/уэ < х/х,
Элемент множества Б С назовем ^минимальным, если он мини-
мален по отношению <}.
Следующие предложения, полученные автором, раскрывают роль отношения <_, и его связь с крайними элементами идемпотентных полумодулей
Теорема 6 Следующие утверждения эквивалентны
(1) элемент у является линейной комбинацией элементов х1,... , хт £
®тах,х>
(2) для любого номера ] е {1, , п}, такого, что у3 ф 0, найдется вектор х1 такой, что х1 <3 у
Теорема 7 Пусть идемпотентный полумодуль V порожден множеством 5 С Ктах,х- Следующие утверждения эквивалентны-
(1) х — это крайний элемент V;
(2) х является ] -минимальным элементом 5* для некоторого индекса у € {1, .,п},
Таким образом, крайние элементы полумодуля V — это ^-минимальные элементы множества его образующих Задача на нахождение частичных максимумов (или минимумов) в га-мерном действительном пространстве была исследована Ф Препаратой и др 35 Из этих результатов вытекает следующее.
Теорема 8 Если полумодуль V С порожден к элементами, то вы-
числительная сложность задачи о нахождении крайних элементов V не превосходит 0(к 1о§2 к) при п — Ъ и 0(/е(к^2 к)(п~®) при п > 3.
Используя теорему 7, можно вывести следующий аналог теоремы Минков-ского.
Теорема 9 Если полумодуль V замкнут, то он порождается своими крайними элементами.
35Ф Препарата и М Шеймос Вычислительная геометрия Введение М Мир, 1989
Множество крайних элементов замкнутого полумодуля, вообще говоря, не замкнуто Однако справедлив следующий результат
Предложение 3 Если множество 5 С х компактно и 0 ^ 5, то полумодуль V, порожденный множеством 5, замкнут
Отметим, что с помощью теоремы 7 можно получить также следующее предложение, следствием которого является известная теорема о единственности базиса конечнопорожденного полумодуля
Предложение 4 Пусть 5 — это множество нормированных образующих полумодуля V в Ж™ и пусть Е — это множество нормированных крайних элементов V. Тогда
1 ЕС в.
2. Пусть Р = в\Е Тогда для любого и 6 Р множество порожда-
ет К.
Третья глава
В третьей главе изложены результаты по клеточному разложению и перенормировкам операции замыкания, полученные автором в статьях [1,2,5]
Строение полумодулей, порожденных двумя векторами, описывается следующей теоремой, полученной автором в статье [1]
Теорема 10 Пусть у, г 6 ®тах,х и Бирр(у) и вирр(г) = {1, .., га} Обозначим через а такую перестановку {1, . ,п}, что
_ Уа-(п ){Мп)) •
Тогда
я-1
ерап {у, г) = У Бран« ?/+1), 8=1
где у* — 2<г(,)3/ ® причем для любого г — 1, . , п — 1 полумодуль
эрап^1, уг+1) — это выпуклый (в обычном смысле) конус, линейная размерность которого не превосходит 2
Таким образом, полумодуль с двумя образующими в!щШ Х в общем случае имеет 71—1 выпуклых "звеньев" Это частный случай клеточного разложения Следующая теорема является одним из ключевых алгебраических результатов третьей главы, полученных автором в статьях [2,5]
Теорема 11 Пусть А и В — это две квадратные матрицы, такие, что А (А) < 1 и А (В) < 1 Тогда А* = В* в том и только в том случае, когда $рап(А*) = span(B*), совпадают
Через span здесь обозначен полумодуль, порожденный столбцами соответствующей матрицы Квадратная матрица А называется определенной, если А(А) = 1 и если все ее диагональные элементы равны 1 Если А — это определенная матрица, то eig(A) = span(A*)
Следствие 1 Пусть А и В — определенные матрицы Тогда А* = В* в том и только в том случае, когда eig(A) — егд(В)
Можно проверить, что собственные полумодули определенных матриц вЕ^ ^ являются в то же время и выпуклыми конусами в М". Оказывается, имеет место следующий результат
Предложение 5 Линейная размерность собственного полумодуля определенной матрицы (как выпуклого конуса) равна мощности минимального набора идемпотентных образующих этого полумодуля
Введем ряд понятий, связанных с клеточным разложением Пусть А — это матрица размера га х т над RmaX]X и пусть у — это вектор с п компонентами Обозначим совокупность множеств S = {Sj • j € supp(j/)}, где S3 — {г у >j А,}, через type(y | А) и назовем ее комбинаторным типом точки у относительно А Можно определить комбинаторные типы и более общо, как произвольные совокупности не более чем п возможно пустых подмножеств {1, ,т} Обозначим множество тех индексов г, чьи 5, присутствуют в типе, через supp(S) Если S — type(y | А) для некоторого у, то supp(S') = supp(y) Типы частично упорядочены по следующему правилу: S С S', если supp(5") С supp(,S) и St С S't для всех г € supp(5') Множество
будем называть клеткой, соответствующей типу 5. Если Агк ф 0 для всех г € Б/с, то тип 5* называется допустимым и мы можем ввести матрицу Л5 по правилу
Справедливо следующее предложение, с помощью которого клетка представляется как собственный полу модуль матрицы А5, см [б]
Предложение 6 Если клетка Xе непуста, то Xе — егд(А
Xs = {z~ S С type(z | А)}
Отметим, что из этого предложения также можно вывести теорему 10 Используя следствие 1, сразу получаем следующий результат
Теорема 12 Пусть Б иТ — это допустимые типы, такие, что их непустые клетки X5 и ХТ совпадают между собой Тогда (Л"5)* = (Лг)*.
Эта теорема позволяет определить клеточное замыкание матрицы Л как (А3)* Эта операция корректно определена для любой клетки, будучи независимой от того типа, который определяет клетку
Рассмотрим теперь случай, когда А — это квадратная матрица размера пхп, у которой есть перестановка сг с ненулевым весом ©"=1Л1СГ(,) Перестановка с максимальным весом называется максимальной Определим V как матрицу, такую, что О^ = Лу, если у — а (г) и = 0 для остальных элементов Если перестановка а максимальна, то матрица А(В")~1 является определенной и называется определенной формой А Различные максимальные перестановки приводят к различным определенным формам, однако можно показать, что их собственные пространства совпадают, и это приводит к следующему результату [2,5]
Теорема 13 Замыкания всех определенных форм любой квадратной матрицы совпадают
Таким образом, для любой квадратной матрицы А, имеющей ненулевые перестановки, можно определить ее определенное замыкание как (Л(£>£Г)-1)*, где а — это любая максимальная перестановка Определенное замыкание является частным случаем клеточного, поскольку е1^А(1)ст)~"1) совпадает с клеткой Xя, соответствующей типу £ = ({сг(1)},. . ,{с(п)}) где а — это любая максимальная перестановка
В заключение автор выражает глубокую благодарность основателю научного направления, в рамках которого выполнена данная работа, своему наг учному руководителю академику РАН В П Маслову за постановку задачи и постоянное внимание к этой работе, а также профессорам и преподавателям кафедры Высшей Алгебры Механико-математического факультета МГУ за благожелательное отношение к этой работе и ценные обсуждения полученных в ней результатов
Работы автора по теме диссертации
ICH Сергеев Алгоритмическая сложность одной задачи идемпотентно выпуклой геометрии // Мат Заметки, том 74, №6, 2003, стр 896-901
2 С H Сергеев Идемпотентные замыкания определенных матриц // Доклады РАН, том 408, №4, 2006, стр 453-454
3 С.Н Сергеев и С Гобер Циклические проекторы и теоремы отделимости в идемпотентных полумодулях // Фундаментальная и прикладная математика, том 13, вып 4, 2007, стр 31-52
В этой статье С H Сергееву полностью принадлежат формулировки и доказательства теоремы 11 (об отделимости нескольких полумодулей в общем случае), теоремы 23 (идемпотентный аналог теоремы Хелли) и теоремы 25 (характеристика спектра циклических проекторов) Остальные результаты статьи, включая теоремы 18, 20 и 22 (об отделимости в конечномерном случае), являются плодом совместной работы С H Сергеева и С Гобёра (Dr Stéphane Gaubert, Directeur de recherche, INRIA), и эти результаты не могут быть разделены
4. S Sergeev, Р Butkovic, H Schneider. Generators, extremals and bases of max cones // Linear Algebra Appl, vol 421, 2007, p 394 - 406
Формулировка теоремы 16 и ее первоначальное (не содержащееся в статье) доказательство, а также формулировка и доказательство теоремы 18, предложения 31 и алгоритма 32 принадлежат П. Буткбвичу (Dr Peter Butkovic, Senior lecturer and reader, University of Birmingham) и Г Шнййдеру (Dr. Hans Schneider, J.J Sylvester Professor Emeritus, University of Wisconsin, Madison), a формулировки и доказательства других результатов статьи, включая предложение 11, теорему 14 (о том, что крайние элементы — это минимумы), предложение 24 (тропическая теорема Минковского), предложение 25, а также оценку вычислительной сложности задачи о нахождении крайних элементов (в конце статьи), принадлежат С H Сергееву
5 S Sergeev. Max-plus definite matrix closures and their eigenspaces // Linear Algebra Appl, vol 421, 2007, p 182 - 201
Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова
Подписано в печать 1Ц.ОЗ О В Формат 60x90 1/16 Уел печ л /<?5 Тираж /00 экз Заказ /<?
Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета
Введение
1 Циклические проекторы и теоремы отделимости
1.1 Отделимость точки от полу модуля.
1.2 Циклические проекторы: общий случай.
1.3 Циклические проекторы и отделимость в М^ах х.
2 Минимальные элементы и аналог теоремы Минковского
2.1 Образующие, базисы и крайние элементы.
2.2 Базисы конечнопорожденных полу модул ей.
3 Определенные и клеточные замыкания матриц
3.1 Определенные замыкания матриц над Мщах,х.
3.2 Клеточное разложение х.
Актуальность темы
При решении'ряда'задач в теории оптимизации (проблемы оптимизации на графах, теория оптимального управления), в физике (теория обобщенных решений уравнения Гамильтона-Якоби, низкотемпературная асимптотика в статистической физике) и в других областях явно или неявно используется линейность по отношению к операции "сложения" ф, которая является идем-потентной (афа — а). Этот общий принцип, сформулированный академиком В.П. Масловым [12, 13, 63], определяет развитие новой области математики, которая получила название идемпотентная математика. Многие интересные результаты в этой области содержатся в сборнике статей [56], см. также обзоры [б, 55]. В практически важных задачах, для решения которых используется идемпотентная математика, роль идемпотентного сложения часто играет операция взятия минимума или максимума двух элементов, а основной алгебраической структурой является некоторое идемпотентное полуполе. Например, полуполе МгпаХ)Х, определяемое как множество неотрицательных чисел R+, снабженное операцией идемпотентного сложения ф = max и обычного умножения 0 = х, или изоморфное ему полуполе Мтах, определяемое как множество чисел Ш U {—оо} с операциями ф = шах и © = +.
Основные приложения идемпотентной математики связаны с задачами оптимизации. Одно из первых таких приложений было описано в работах Б.А. Карре [27, 28], см. также [45, 71]. В этих работах замечено, что метод исключения Гаусса без выбора ведущего элемента можно рассматривать как прототип для оптимизационных алгоритмов на графах и применять для решения систем линейных уравнений над широким классом полуколец. Главный объект в этих работах — это ряд / ф А ф А2 ф.где А — это некоторая квадратная матрица с элементами из идемпотентного полукольца, являющийся очевидным аналогом операции (I — А)~г и называемый алгебраическим замыканием А. Эти идеи получили свое дальнейшее развитие в работах Г.Л. Литвинова, В.П. Маслова и др. [57, 58, 60], см. также [61],[62] и [73], посвященных универсальным алгоритмам идемпотентной математики и идемпотентному интервальному анализу.
Другие задачи линейной алгебры над идемпотентными полуполями, в частности, решение систем вида Ах = b и нахождение собственных значений и собственных векторов Ах = Хх, возникают в связи с составлением расписаний, синхронизацией производства и сетями Петри [23, 33, 49].Такие приложения возникают и в физике. В качестве примера, рассмотрим модель Френкеля-Конторовой. В простейшем варианте это одномерная цепочка атомов, находящихся в периодическом потенциале. При статическом описании этой модели основная задача заключается в нахождении основных состояний и значений параметров, которые характеризуют эти состояния [21, 22]. Алгоритм для нахождения основных состояний был предложен У. Чоу и Р.Б. Гриффитсом [30].которые использовали для этого собственные векторы и собственные значения некоторого интегрального оператора над идемпотентным полуполем. Метод Чоу и Гриффитса был использован в ряде физических задач [66, 67, 76]. Близкие по своему математическому описанию задачи возникают и в математической экономике, а именно, в задачах динамической оптимизации с бесконечным горизонтом, где требуется найти траектории, приносящие максимальный доход [14, 53, 77].
В связи с этими практическими приложениями, возникает интерес к теории идемпотентных полуколец и полуполей, и к теории полумодулей (т.е. "пространств") над этими полукольцами. Значительная часть этих результатов собрана в монографии Дж. Голана [44].Отметим, что линейная алгебра над идемпотентными полукольцами (и над полукольцами вообще) отличается тем, что в ней есть много способов определить, что такое линейная независимость, ранг и определитель, и в связи с этим возникает много новых нетривиальных задач, см. [23, 26, 33, 46, 48, 80].
Идемпотентный анализ был развит в работах В.П. Маслова и его сотрудников [4], [5], [11]-[14], [53], [63]-[65], см. также [36] и [37].Основной объект идем-потентного анализа В.П. Маслова — это полумодуль полунепрерывных функций на некотором топологическом пространстве, принимающих значение в некотором идемпотентном полукольце. В цитированных работах была развита теория идемпотентных мер, интегралов, обобщенных функций и идем-потентно линейных операторов). Эти результаты были использованы для построения обобщенных решений уравнения Гамильтона-Якоби-Беллмана, а также в упоминавшихся выше задачах динамической оптимизации с бесконечным горизонтом. В работах Г.Л. Литвинова, В.П. Маслова и Г.Б. Шпиза [7, 8, 9] развит алгебраический подход к идемпотентному анализу. Этот подход отличается тем, что в нем основные топологические понятия и результаты моделируются на чисто алгебраическом уровне, с привлечением результатов теории решеток и решеточно упорядоченных групп [1, 18].
Большую роль в развитии идемпотентной математики играет эвристический принцип соответствия [57], родственный известному принципу соответствия Н. Бора: у многих интересных конструкций и результатов "традиционной" математики над полями должны быть интересные идемпотентные аналоги. В частности, это касается идемпотентного аналога выпуклой геометрии, развитию которого посвящена данная диссертация. Один из первых результатов в этом направлении получил К. Циммерманн [78, 79], который рассмотрел идемпотентные аналоги выпуклых множеств и функций и доказал теорему об отделимости точки от замкнутого идемпотентно выпуклого множества в конечномерных полумодулях над Rmax. Его результаты были обобщены в работе С.Н. Самборского и Г.Б. Шпиза [72] (на полумодули функций над идемпотентными полуполями), а также в работах Г. Коэна, С. Гобера, Ж.-П. Квадра и И. Зингера [31, 32]. Изучению этого типа выпуклости также посвящена работа М. Девелина и Б. Штурмфельса [39]. В этой работе .развивается другой подход к идемпотентной выпуклости, в основе которого лежит разложение свободного полумодуля, элементами которого являются некоторые выпуклые (в обычном смысле) области, то есть клетки. Отметим, что важную роль в этих работах играют проекторы на идемпотентные полумодули, имеющие много общего с ортогональными проекциями на выпуклые множества. Композиции этих проекторов, исследуемые в данной диссертации и называемые здесь циклическими проекторами на идемпотентные полу модули, также используются для нахождения точки, лежащей в пересечении нескольких полу модулей [34].
Абстрактные версии теорем отделимости, а также результаты, касающиеся соотношений между числами Хелли, Радона и Каратеодори, известны в аксиоматической теории выпуклости [17]. В частности, известны теоремы отделимости двух непересекающихся обобщенно выпуклых множеств с помощью двух дополняющих друг друга полупространств [29]. Существует также много других обобщений и аналогов теории выпуклости, актуальных в настоящее время в связи с приложениями в математической экономике [40].
Основное затруднение при построении идемпотентного аналога выпуклой геометрии (как и аксиоматической теории выпуклости) состоит в том, что известные доказательства многих теорем выпуклой геометрии не переносятся тривиальным образом на исследуемый случай. Например, в обычном выпуклом анализе можно легко показать, что два выпуклых множества А и В отделяются друг от друга тогда и только тогда, когда точка 0 отделяется от разности А — В, однако в идемпотентной математике нет операции вычитания и идемпотентный аналог разности А — В оказывается слишком "слабым". Аналогичные затруднения возникают и в связи с идемпотентной версией теоремы Минковского. Преодоление этих трудностей — основной стимул данной работы.
Цель работы
Цель работы — исследовать аналог выпуклой геометрии в полумодулях над идемпотентными полуполями; в частности, получить новые аналоги некоторых известных теорем конечномерной выпуклой геометрии.
Методы исследования
В работе используются методы линейной алгебры над идемпотентными полукольцами, а также элементы теории решеток и теории неотрицательных матриц и операторов.
Научная новизна
Основные результаты диссертации являются новыми и состоят в следующем:
1. Получена теорема отделимости нескольких замкнутых полумодулей и, как следствие этой теоремы, идемпотентный аналог теоремы Хелли;
2. Получена теорема, характеризующая спектр циклических проекторов в терминах некоторого обобщения проективной метрики Гильберта;
3. Получен идемпотентный аналог теоремы Минковского;
4. В связи с клеточным разложением свободного полумодуля, описаны перенормировки операции алгебраического замыкания, определенные для широкого класса квадратных и прямоугольных матриц;
Теоретическая и практическая ценность
Диссертация носит теоретический характер. Результаты, полученные в ней, могут быть полезны для дальнейшего изучения идемпотентно выпуклой геометрии и теории полумодулей над идемпотентными полукольцами.
Апробация результатов и публикации
1. Международная конференция "II International Conference on Matrix Methods and Operator Equations". Москва, Институт Вычислительной Математики РАН, 23-27 июля 2007 года.
2. Международная конференция "Idempotent and tropical mathematics and problems of mathematical physics". Москва, Независимый Московский Университет, 25-30 августа 2007 года.
3. Международная конференция "Геометрия в Астрахани". Астрахань, АГУ, сентябрь 2007.
4. Семинар "Кольца и модули". Руководители: профессора А.В. Михалев, В.Н. Латышев, B.A. Артамонов, Е.С. Голод, В.К. Захаров, доценты B.T. Марков и А.Э. Гутерман. Москва, МГУ им. М.В. Ломоносова, октябрь 2007.
Основные результаты диссертации опубликованы в пяти работах автора
Введение: полумодули и выпуклость
Идемпотентное полуполе М-тах,х — это множество неотрицательных чисел, снабженное операциями сложения ф := max и обычного умножения О := х. Например, в этом полуполе 2ф3 = 3и2©3 = 6. Рассмотрим К^ х, то есть свободный полумодуль с тремя образующими надМтах,х- Элементы IRfnax х обозначим (x,y,z). На рис. 1 показаны сечения плоскостью z — const некоторых подполумодулей х. Первый пример — это "отрезки", то есть полумодули с двумя образующими. Далее изображены "треугольник", "многоугольник" и полумодуль с бесконечным множеством образующих (S U {и}).
81-85].
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ у У о х О х У О
X О х
Рис. 1: Сечения подполумодулей К^. шах,Х
В общем случае рассматривается полумодуль V над полуполем /С с идем-потентным сложением 0. Нуль полуполя и нуль полумодуля обозначаются О, единица полуполя обозначается 1. Операция умножения обозначается О, причем это обозначение мы будем, как правило, опускать. По определению полуполя [44], множество ЛД{0} образует абелеву группу по умножению. Сложение 0 задает порядок < в полукольце /С по правилу = для Л, \i G /С, причем А © ц = sup(A, у) (по отношению <). Идемпотентная сумма элементов произвольного множества определяется как точная верхняя грань этого множества, если таковая существует. Отношение порядка аналогично определяется и в полу модуле, и также обозначается <.
Полукольцо или полумодуль называются Ь-полпыми [9], если они замкнуты относительно взятия сумм (т.е. точных верхних граней) любых подмножеств, ограниченных сверху, и если умножение дистрибутивно относительно любых таких сумм. Напомним, что если можно брать точные верхние грани 0 ограниченных сверху множеств, то можно брать и точные нижние грани Л множеств, ограниченных снизу.
Так как любой элемент полуполя или полумодуля неотрицателен по введенному выше отношению порядка, то подполумодули V можно рассматривать как аналоги выпуклых конусов неотрицательного ортанта. Эта точка зрения согласована со следующим идемпотентным аналогом выпуклости [78].
Определение 1 Множество С С V называется идемпотентно выпуклым, если Хх 0 jiy £ С для любых х,у Е С я таких А, д G /С, что А 0 ц — 1.
Рассмотрим более подробно случай V = К.п. Элементы этого полумодуля обозначим (xi,. 7хп). Если V — подполумодуль /Сп, то его сечение по любой плоскости Xi = const является идемпотентно выпуклым подмножеством /С71-1. Наоборот, если С — идемпотентно выпуклое подмножество /С"-1, то множество V = {(Arc, А): х G С, A G /С} является подполумодулем JCn. Это аналог известного соответствия между выпуклыми конусами и выпуклыми множествами. Таким образом, на рис. 1 показаны, в сущности, идемпотентно выпуклые подмножества неотрицательного ортанта плоскости Ж2.
Циклические проекторы и теоремы отделимости
В первой главе изложены основные результаты по теоремам отделимости и циклическим проекторам в идемпотентных полумодулях, полученные в статье [81]. Предположим, что полукольцо К и полумодуль V над /С удовлетворяют следующим условиям.
ЛО): полукольцо /С является 6-полным идемпотентным полуполем, а полумодуль V является 6-полным полумодулем над /С;
А1): для любых элементов х и у ф О из V, множество {Л Е /С | Ху < ж} ограничено сверху.
Эти предположения справедливы для многих полумодулей, рассматривающихся в идемпотентном анализе. Например, для полумодулей LSC(X) полунепрерывных снизу функций на топологическом пространстве X, принимающих значение в некотором 6-полном полуполе (в частности, Мтах,х)- • Из предположений-(АО, А1) вытекает, что операция х/у = max{A Е /С | Ху <х}: определена для всех х и всех у ^ О из V.
Следующее определение, см. [9], моделирует на алгебраическом языке понятие замкнутости.
Определение 2 Назовем подполумодулъ V полумодуля V Ь- (под) полу модулем, если V замкнут относительно взятия сумм любых своих подмножеств, ограниченных сверху в V.
Пусть V — это 6-подполу модуль полумодуля V. Рассмотрим оператор Ру, определенный по известной формуле [9], [31].
Ру(х) = max{ii eV \ и< ж}, для любого элемента х Е V. Мы пишем "max", подчеркивая, что точная верхняя грань множества в фигурных скобках принадлежит этому множеству. Оператор Ру является проектором на подполу модуль V, так как Ру(х) £ V для любого х Е V и Py(v) Е V для любого v Е V. Роль полупространства играет следующий объект.
Определение 3 Множество Н, определенное с помощью
Н — {х\ и/х > v/x} U {0} где и, v Е Мщ^х, и < v, называется (идемпотентным) полупространством.
Если V — 1С1 и все координаты и и v ненулевые, то н = I 0 хтт1 < 0 wr1},
1,.,п 1 ,.,п то есть Н — это аналог замкнутого однородного полупространства конечномерной выпуклой геометрии.
Следующий результат близок к известной теореме отделимости точки от полумодуля [31].Его также можно рассматривать как следствие теоремы о представлении идемпотентно линейных функционалов [9].
Предложение 4 Пусть V С У — это Ь-полумодуль и пусть и £ V. Тогда полупространство
Н — {х\ PV(u)/x > и/х} U {0} содержит V и не содержит и.
Если V\,., — это &-полумодули, то можно определить циклический проектор Рк • • • Pi, где через Р{ обозначен проектор на полумодуль Ц.
Определяемое ниже понятие архимедовости является упрощенной версией того, что используется в идемпотентном функциональном анализе [19].
Определение 5 Вектор х £ V назовем архимедовым, если х/у > 0 для всех G V. Подполумодуль V С V назовем архимедовым, если он содержит хотя бы один архимедов вектор. Полупространство будет называться архимедовым, если оба определяющих вектора архимедовы.
Заметим, что в полумодулях JC1, где /С — это идемпотентное fr-полное полуполе, архимедовы векторы — это в точности те векторы, все координаты которых положительны. Другой пример полумодуля, имеющего архимедовы векторы — это полумодуль полунепрерывных функций на некотором компакте. Если полумодуль V удовлетворяет (Ж), А1) и имеет архимедовы векторы, то справедлива следующая теорема, полученная автором:
Теорема 6 Пусть у оператора Рк - • • Р\ есть архимедов собственный вектор у с ненулевым собственным значением А. Следующие условия эквивалентны:
1. существует такой архимедов вектор х, что Рк - • - Р\х < fix для некоторого /j, < 1.
2. для любого i = 1,., к существуют такие архимедовы полупространства Щ, что Ц С Щ и ПгЩ = {0};
3. DfVi = {0}; 4- A < 1.
В общем случае удается также получить следующий результат, касающийся спектра циклических проекторов.
Определение 7 Пусть Vi,., Т4 — это 6-подполумодули V. Величину dn{Vi,., Vy = sup (хг/х2) О (х2/хъ) О - • • 0 (хк/х1) x1eVi,.,:EfceVrfc назовем гильбертовым значением полумодулей Vi,., 14
Теорема 8 Пусть Vi,., Vk — ото b-подполумодули, и у оператора Р& • ■ • Р\ есть архимедов собственный вектор у с ненулевым собственным значением X. Тогда это собственное значение совпадает с гильбертовым значением полумодулей Vi,.,Vk, причем на векторах х1,.,хк, где хг — Pi- - • Р\у, достигается максимум в определении гильбертова значения.
Рассмотрим теперь случай V = М.„1аХ!Х. В естественно рассматривать полумодули, замкнутые в евклидовой топологии. Можно показать, что такие полумодули являются 6-полумодулями и что проектор на такой полумодуль непрерывен (в обычном смысле). Как и в общем случае, проектор является также однородным и изотонным оператором. Если F — оператор, обладающий такими свойствами, то у него есть собственные значения, их конечное число, и спектральный радиус равен p(F) = max{A G М+ | За; € \ 0, Fx = Хх} .
Справедливо также следующее нелинейное обобщение формулы Коллатца-Виландта для спектрального радиуса неотрицательной матрицы [70].
Предложение 9 Пусть F: R™ —> К™ — это изотопный, однородный и непрерывный оператор. Тогда p(F) = inf maxfFCaOlizer1.
V 7 же(М+\{0})п 1<г'<тг V 1X1 1
Применимость этих результатов к циклическим проекторам позволяет усилить результаты для общего случая. Сформулируем общую теорему отделимости для подполу модулей в
Теорема 10 Пусть ., Vk — это замкнутые архимедовы полумодули в ®*тпах, х ■ Следующие утверждения эквивалентны:
1. существуют полоэюительный вектор х и число X < 1, такие, что Pk" ■ Р\х < Хх;
2. существуют архимедовы полупространства Щ, содержащие Vi и такие, что П^=1Яг- = {О};
3. nUVi = {о};
4. p{Pk---Pi)<l.
Условия 2. и 3. эквивалентны и в том случае, когда apxuMedoeocmbVi,., Т4 не предполагается.
Эквивалентность условий 2. и 3. в этой теореме — это утверждение об отделимости нескольких полумодулей. Далее, в случае М^х удается полностью охарактеризовать собственные значения циклических проекторов. Введем обозначение
Vм = {х е V | supp(x) С М}, где М — произвольное подмножество {1,. ,п}.
Теорема 11 Пусть ., Т4 — это замкнутые полумодули в Тогда гильбертово значение Vi,., V]~ — это спектральный радиус Р^ - • • Р\. Спектр Рк ■ ■ • Р\ — это множество гильбертовых значений d^V^1,., V^1), где М пробегает все подмножества {1,., п}.
Еще одним следствием теоремы об отделимости нескольких полумодулей является идемпотентный аналог теоремы Хелли, который сформулирован здесь для идемпотентно выпуклых множеств.
Теорема 12 (Теорема Хелли) Пусть Ci, г — 1,. , m — это совокупность т > п + 1 идемпотентно выпуклых множеств в К^^х- Если любые п + 1 из них пересекаются, то и вся совокупность в целом имеет непустое пересечение.
Крайние элементы и образующие
Во второй главе изложены результаты, касающиеся образующих и крайних точек подполумодулей R^iaXiX, полученные автором в статье [84].
Будем говорить, что идемпотентный полумодуль V порождается множеством S-, если V является множеством конечных линейных (в смысле операций ф и О) комбинаций элементов из S. Следующее определение также хорошо известно, см. например работы Э. Ванье [74], [75].
Определение 13 Элемент х идемпотентного полумодуля V называется крайним, если из х = и © v следует, что х — и или х = v.
Понятие крайнего элемента идемпотентного полумодуля соответствует, в обычной выпуклой геометрии, понятию крайнего лучу выпуклого конуса. Оказывается, что крайние элементы полумодулей удобно описывать, используя следующее отношение предпорядка.
Определение 14 Рассмотрим отношение у <j х О Xj ^ 0, уз ^ 0, y/yj < x/xj.
Элемент множества S С М"1аХ;Х назовем j-минимальным, если он минимален по отношению <,-.
Следующие предложения, полученные автором, раскрывают роль отношения <j и его связь с крайними элементами идемпотентных полу модулей.
Теорема 15 Следующие утверждения эквивалентны:
1) элемент у является линейной комбинацией элементов х1,.,хт €
-^inax, х >
2) для любого номера j G 1,. ,п, такого, что yj ф 0, найдется вектор х1 такой, что xl <j у.
Теорема 16 Пусть идемпотентный полумодуль V порооюден множеством S С Ml^ х. Следующие утверждения эквивалентны:
1) х — это крайний элемент V;
2) х является j-минимальным элементом S для некоторого индекса j Е 1,., п;
Таким образом, крайние элементы полумодуля V — это j-минимальные элементы множества его образующих. Задача на нахождение частичных максимумов (или минимумов) в n-мерном действительном пространстве была исследована Ф. Препаратой и др. [15]. Из этих результатов вытекает следующее.
Теорема 17 Если полумодуль V С М^ах,х порождено к элементами, то вычислительная сложность задачи о нахождении крайних элементов V не превосходит 0(&log2 к) при п = 3 и 0(&(log2 при п > 3.
Используя теорему 16, можно вывести следующий аналог теоремы Мин-ковского.
Теорема 18 Если полумодуль V замкнут, то он порождается своими крайними элементами.
Множество крайних элементов замкнутого полумодуля, вообще говоря, не замкнуто. Однако справедлив следующий результат.
Предложение 19 Если множество S С M^^ х компактно и 0 ф S, то полумодуль V, порожденный множеством S, замкнут.
Отметим, что с помощью теоремы 16 можно получить также следующее предложение, следствием которого является известная теорема о единственности базиса конечнопорожденного полу модуля.
Предложение 20 Пусть S — это множество нормированных образующих полумодуля V в Mmax,x> и пусть Е — это множество нормированных крайних элементов V. Тогда
1. Е С S.
2. Пусть F — S\E. Тогда для любого и G F множество S\{u} порождает К.
Клеточное разложение и определенные замыкания
В третьей главе изложены результаты по клеточному разложению и определенным замыканиям матриц, полученные автором в статьях [82,83,85].
Строение полумодулей, порожденных двумя векторами, описывается следующей теоремой, полученной автором в статье [82].
Теорема 21 Пусть y,z £ М"яу х и supp(у) U supp(z) = {1,.,п}. Обозначим через а такую перестановку {1,. ,п}, что
Тогда
71—1 span(?/, z) = врап(г>г,г;г+1), г=1 где vl — za^y ф ya{i)z> причем для любого г — 1,.,п — 1 полумодуль span(?;\ г>г+1) — это выпуклый (в обычном смысле) конус, линейная размерность которого не превосходит 2.
Таким образом, полумодуль с двумя образующими вМ^;1Х;Х в общем случае имеет п— 1 выпуклых "звеньев". Это частный случай клеточного разложения.
Следующая теорема является одним из ключевых алгебраических результатов третьей главы, полученных автором в статьях [83,85].
Теорема 22 Пусть А и В — это две квадратные матрицы, такие, что \{А) < 1 и Х(В) < 1. Тогда А* = В* в том и только в том случае, когда span(A*) = span(B*).
Через span здесь обозначен полу модуль, порожденный столбцами соответствующей матрицы. Квадратная матрица А называется определенной, если А(Л) = 1 и если все ее диагональные элементы равны 1. Если А — это определенная матрица, то eig(^) = span (Л*)
Следствие 23 Пусть А и В — определенные матрицы. Тогда А* = В* в том и только в том случае, когда eig(A) = eig(B).
Можно проверить, что собственные полумодули определенных матриц являются в то же время и выпуклыми конусами в М". Оказывается, имеет место следующий результат.
Предложение 24 Линейная размерность собственного полумодуля определенной матрицы (как выпуклого конуса) равна мощности минимального набора идемпотентных образующих этого полумодуля.
Введем ряд понятий, связанных с клеточным разложением (некоторое обобщение определений [39]). Пусть А — это матрица размера пхт над Мтах,х и пусть у— это вектор с п компонентами. Обозначим совокупность множеств S = {Sj: j Е supp(?/)}, где Sj = {г: у >j А.,}, через type(?/ ) А) и назовем ее комбинаторным типом точки у относительно А Можно определить комбинаторные типы и более общо, как произвольные совокупности не более чем п возможно пустых подмножеств {1,. ,ш}. Обозначим множество тех индексов г, чьи Si присутствуют в типе, через supp(S'). Если S = type(y | А) для некоторого у, то supp(S') = supp(?/). Типы частично упорядочены по следующему правилу: S С S', если supp(S") С supp(5') и Si С S[ для всех г Е supp(<S'). Множество
Xs = {z: S С type(z \ А)} будем называть клеткой, соответствующей типу S. Если Aik ф 0 для всех г е «Sfc, то тип S называется допустимым и мы можем ввести матрицу As по правилу
A-k/Aik, если г GsuppfS) и Si ф 0; ei, если г Esupp(S') и = 0;
О, если г ^supp(S').
Справедливо следующее предложение, с помощью которого клетка представляется как собственный полумодуль матрицы As, см. [85].
Предложение 25 Если клетка Xs непуста, то Xs = eig(As).
Отметим, что из этого предложения также можно вывести теорему 3.2.1. Используя следствие 23, сразу получаем следующий результат.
Теорема 26 Пусть S иТ — это допустимые типы, такие, что их непустые клетки Xs и ХТ совпадают между собой. Тогда (As)* = (АТ)*.
Эта теорема позволяет определить клеточное замыкание матрицы А как (А5)*. Эта операция корректно определена для любой клетки, будучи независимой от того типа, который определяет клетку.
Рассмотрим теперь случай, когда А — это квадратная матрица размера п х п, у которой есть перестановка а с ненулевым весом Перестановка с максимальным весом называется максимальной. Определим .D0" как матрицу, такую, что Вц — Ац, если j? = <т(г) и D^ — 0 для остальных элементов. Если перестановка а максимальна, то матрица A(Da)~l является определенной и называется определенной формой А. Различные максимальные перестановки приводят к различным определенным формам, однако можно показать, что их собственные пространства совпадают, и это приводит к следующему результату [83,85].
Теорема 27 Замыкания всех определенных форм любой квадратной матрицы совпадают.
Таким образом, для любой квадратной матрицы А, имеющей ненулевые перестановки, можно определить ее определенное замыкание как (A(Da)~1)*, где о — это любая максимальная перестановка. Определенное замыкание является частным случаем клеточного, поскольку eig[A(Da)~l) совпадает с клеткой Xs, соответствующей типу S = ({сг(1)},., {сг(п)}) где а — это любая максимальная перестановка.
Благодарности
Автор глубоко благодарен основателю научного направления, в рамках которого выполнена данная работа, своему научному руководителю академику РАН В.П. Маслову за общую постановку задачи и постоянное внимание к этой работе, а также профессорам и преподавателям кафедры Высшей Алгебры Механико-математического факультета МГУ за благожелательное отношение к этой работе и ценные обсуждения полученных в ней результатов.
1. Г. Биркгоф. Теория решеток. М.:Наука, 1984. Пер. с англ.
2. Н.Н. Воробьев. Экстремальная алгебра положительных матриц. Elektron. Informationsverarb. und Kybemetik, 3:39-71, 1967.
3. Н.Н. Воробьев. Экстремальная алгебра неотрицательных матриц. Elektron. Informationsverarb. und Kybernetik, 6:302-312, 1970.
4. B.H. Колокольцов и В.П. Маслов. Общий вид эндоморфизмов в пространстве непрерывных функций со значением в числовом коммутативном полукольце (с операцией © = max]. ДАН СССР, 295(2)-.283-287, 1987.
5. В.Н. Колокольцов и В.П! Маслов. Задача Коши для однородного уравнения Беллмана. ДАН СССР, 296(4):796-800, 1987.
6. Г.Л. Литвинов. Деквантование Маслова, идемпотентная и тропическая математика: краткое введение. Записки научных семинаров ПО МИ, 326:145-181, 2005.
7. Г.Л. Литвинов, В.П. Маслов и Г.Б. Шпиз. Линейные функционалы на идемпотентных пространствах: алгебраический подход. Докл. РАН, 363(3) :298-300, 1998.
8. Г.Л. Литвинов, В.П. Маслов и Г.Б. Шпиз. Тензорные произведения идемпотентных полумодулей. Алгебраический подход. Мат. Заметки, 65(4):572-585,1999.
9. Г.Л. Литвинов, В.П. Маслов и-Г.Б. Шпиз. Идемпотентный функциональный анализ. Алгебраический подход.Мат. Заметки, 69(5):758-797, 2001. E-print (English) arXiv:math.FA/0009128.
10. Г.Л. Литвинов и Е.В. Маслова. Универсальные числовые алгоритмы и их программная реализация. Программирование, 5:53-62, 2000.
11. В.П. Маслов. Асимптотические методы решения псевдодифференциальных уравнений. М.:Наука, 1987.
12. В.П. Маслов. О новом принципе суперпозиции для задач оптимизации. Успехи Мат. Наук, 42(3(255)):39-48, 1987.
13. В.П. Маслов. Новый подход к обобщенным решениям нелинейных систем. ДАН СССР, 292(1):37-41, 1987.
14. В.П. Маслов и В.Н. Колокольцов. Идемпотентный анализ и его применение в оптимальном управлении. М.:Наука, 1994.
15. Ф: Препарата и М. Шеймос. Вычислительная геометрия: Введение. М.:Мир, 1989. Пер. с англ.
16. Р.Т. Рокафеллар. Выпуклый анализ. М.:Мир, 1973. Пер. с англ.
17. В.П. Солтан. Введение в аксиоматическую теорию выпуклости. Кишинев: Штиинца, 1984.
18. Л. Фукс. Частично упорядоченные алгебраические системы М.: Мир, 1965. Пер. с англ.
19. Г.Б. Шпиз. Теорема о существовании собственных векторов в идемпо-тентном анализе. Матем. Заметки, 82(3) :459 468, 2007.
20. М. Aldan, S. Gaubert, and V. Kolokoltsov. Set coverings and invertibility of the functional Galois connections. In 56], pages 19-51. Also* arXiv:math.FA/0403441.
21. S. Aubry. Exact models with a complete Devil's staircase. J. Phys. C, 16:2497-2508, 1983.
22. S. Aubry and P.Y. Le Daeron. The discrete Frenkel-Kontorova model and its extensions. I. exact results for the ground states. Physica D, 8:381-422, 1983.
23. F.L. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat. Synchronization and Linearity. Wiley, Chichester, New York, 1992.
24. P. Butkovic. Simple image set of (max,-}-) linear mappings. Discrete Appl. Math., 105:73-86, 2000.
25. P. Butkovic. Max-algebra: the linear algebra of combinatorics? Linear Algebra Appl., 367:313-335, 2003.
26. B.A. Carre. An algebra for network routing problems. J. of the Inst, of Maths, and Applies, 7:273-299, 1971.
27. B.A. Carre. Graphs and Networks. Clarendon Press, Oxford, 1979.
28. V. Chepoi. Separation of two convex sets in convexity structures. J. of Geometry, 50:30-51, 1994.30. -W. Chou and R.B. Griffiths. Ground states of one-dimensional systems using effective potentials. Physical Review B, 34:6219-6234, 1986.
29. G. Cohen, S. Gaubert, and J.P. Quadrat. Duality and separation theorems in idempotent semimodules. Linear Algebra Appl., 379:395-422, 2004. Also arXiv:math.FA/0212294.
30. G. Cohen, S. Gaubert, J.P. Quadrat, and I. Singer. Max-plus convex sets and functions. In 56], pages 105-129. Also arXiv:math.FA/0308166. •
31. R.A. Cuninghame-Green. Minimax Algebra, volume 166 of Lecture Notes in Economics and Mathematical Systems. Springer, Berlin, 1979.
32. R.A. Cuninghame-Green and P. Butkovic. The equationA®x = B®y over (max,+). Theoretical Computer Science, 293:3-12, 2003.
33. R.A. Cuninghame-Green and P. Butkovic. Bases in max-algebra. Linear Algebra Appl, 389:107-120, 2004.
34. P. Del Moral. A survey of Maslov optimization theory. In 53], pages 243-302 (Appendix).
35. P. Del Moral and M. Doisy. On the applications of Maslov optimization theory. Mathematical Notes, 69(2)-.232-244, 2001.
36. M. Develin, F. Santos, and B. Sturmfels. On the rank of a tropical matrix. In 47], pages 213-242. Also arXiv:math.CO/0312114.
37. M. Develin and B. Sturmfels. Tropical convexity. Documenta Math., 9:1-27, ■ 2004. Also arXiv:math.MG/0308254.
38. A. Eberhard, N. Hadjisawas and D.T. Luc, editors. Generalized convexity, generalized monotonicity and applications, volume 77 of Nonconvex Optimization and Its Applications. Springer, 2006.
39. H.G. Eggleston. Convexity. Cambridge Univ. Press, Cambridge, 1958.
40. S. Gaubert. Theorie des Systemes Lineaires dans les Dioides. PhD» thesis, Ecole des Mines des Paris, Paris, 1992.
41. S. Gaubert and R. Katz. The Minkowski theorem for max-plus convex sets. Linear Algebra Appl, 421:356-369, 2007. Also arXiv:math.GM/0605078.
42. J. Golan. Semirings and their applications. Kluwer, Dordrecht, 2000.
43. M. Gondran. Path algebra and algorithms. In Bl Roy, editor, Combinatorial programming: methods and/ applications, pages 137-148. Reidel, Dordrecht, 1975. •
44. M. Gondran and M. Minoux. Linear algebra of dioi'ds : a survey of recent results. Annals of Discr. Math., 19:147-164, 1984.
45. B. Heidergott, G.-J. Olsder, and J; van der Woude. Max-plus at work.Princeton Univ. Press, 2006.
46. S. Helbig. Caratheodory's and Krein-Milman's theorems in fully ordered groups. Comment. Univ. Carolin., 29:157-167, 1988.
47. D; Hilbert. Neue Begriindungen der Bolyai-Lobatchevskyschen Geometrie. Mathematische Annalen, 57:137-150, 1903.
48. M. Joswig. Tropical halfspaces. In 47], pages 409-4321 Also arXiv:math.CO/0312068.
49. V.N. Kolokoltsov and V.P: Maslov. Idempotent analysis and, applications. Kluwer Acad. Publ., Dordrecht et al., 1997.
50. H.T. Kung, F. Luccio, and F.P. Preparata. On finding the maxima of a set of vectors. J. of the ACM, 22(4):469-476, Oct. 1975.
51. G.b. Litvinov. Maslov dequantization, idempotent and tropical mathematics: a brief introduction. J. of Math. Sci., 140(3) :426-444, 2007.
52. G. Litvinov and V. Maslov, editors. Idempotent Mathematics and Mathematical Physics, volume 377 of Contemporary Mathematics. American Mathematical Society, Providence, 2005.
53. G.L. Litvinov and V.P. Maslov. Correspondence principle for idempotent calculus and some computer applications. In J. Gunawardena, editor, Idempotency, Publications of the I. Newton Institute, pages 420-443. Cambridge Univ. Press, 1998.
54. G.L. Litvinov, V.P. Maslov, and A.Ya. Rodionov. Unifying approach to software and hardware design for scientific calculations. Intern. Sophus Lie Centre, Moscow, 1995. E-print arXiv:quant-ph/9904024.
55. G.L. Litvinov, V.P. Maslov, and G.B. Shpiz. Idempotent functional analysis, an algebraical approach. Math. Notes, 69(5):696-729, 2001. E-print arXiv:math.FA/0009128.
56. G. Litvinov and E. Maslova. Universal numerical algorithms and their software implementation. Programming and Computer Software, 26(5) :275-380, 2000. E-print arXiv:math.NA/0102144.
57. G. Litvinov and A. SobolevskiT. Idempotent interval analysis and optimization problems. Reliable Computing, 7(5):353-377, 2001. E-print arXiv:math.NA/0101152.
58. P. Loreti and M. Pedicini. An object oriented approach to idempotent analysis: Integral equations as optimal control problems. In 56], pages 187208.
59. V.P. Maslov. New superposition principle for optimization problems. In: Seminaire sur les Equations aux D6rivees Partielles 1985/86, Centre Math, de l'Ecole Polytechnique, Palaiseau (1986), expose 24.
60. V.P. Maslov. Methods operatorielles. Editions MIR, Moscow, 1987.
61. V.P. Maslov and S.N. SamborskiT, editors. Idempotent analysis, volume 13 of Advances in Soviet Math. American Mathematical Society, Providence, 1992.
62. J.J. Mazo, F. Falo and L.M. Fiona. Josephson junction ladders: ground state and relaxation phenomena. Physical Review В, 52:10433-10440, 1995.
63. С. Micheletti, R.B. Griffiths, and J.M. Yeomans. Surface spin-flop and discommensuration transitions in antiferromagnets. Physical Review Д 59:6239-6249,1999.
64. С. Гобер и С.Н. Сергеев. Циклические проекторы и теоремы отделимости в идемпотентных полумодулях. Фундаментальная и прикладная математика, 13(4):31-52, 2007. El-print arXiv:0706.3347 (in English).
65. С.Н. Сергеев. Алгоритмическая сложность одной задачи идемпотент-но выпуклой геометрии. Матем. Заметки, 74(6):896-901, 2003.
66. С.Н. Сергеев. Идемпотентные определенные замыкания матриц. Докл. РАН, 408(4) :453-454, 2006.
67. P. Butkovic, Н. Schneider, and S. Sergeev. Generators, extremals and bases of max cones. Linear Algebra Appl, 421:394-406, 2007. El-print arXiv:math.RA/0604454.
68. S. Sergeev. Max-plus definite matrix closures and their eigenspaces. Linear Algebra Appl, 421:182-201, 2007. E-pyint arXiv:math.MG /0506177.
