Идемпотентные аналоги теорем отделимости и образующие идемпотентных полумодулей

Актуальность темы

.

При решении’ряда’задач в теории оптимизации (проблемы оптимизации на графах, теория оптимального управления), в физике (теория обобщенных решений уравнения Гамильтона-Якоби, низкотемпературная асимптотика в статистической физике) и в других областях явно или неявно используется линейность по отношению к операции «сложения» ф, которая является идем-потентной (афа — а). Этот общий принцип, сформулированный академиком В. П. Масловым [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™ —> К&trade- — это изотопный, однородный и непрерывный оператор. Тогда 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).

Условия 2. и 3. эквивалентны и в том случае, когда apxuMedoeocmbVi,., Т4 не предполагается.

Эквивалентность условий 2. и 3. в этой теореме — это утверждение об отделимости нескольких полумодулей. Далее, в случае М^х удается полностью охарактеризовать собственные значения циклических проекторов. Введем обозначение.

Vм = {х е V | supp (x) С М}, где М — произвольное подмножество {1,., п}.

Теорема 11 Пусть ., Т4 — это замкнутые полумодули в Тогда гильбертово значение Vi,., V]~ — это спектральный радиус Р^ - • • Р. Спектр Рк ¦ ¦ • Р — это множество гильбертовых значений d^V¹,., V¹), где М пробегает все подмножества {1,., п}.

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

Теорема 12 (Теорема Хелли) Пусть Ci, г — 1,., m — это совокупность т > п + 1 идемпотентно выпуклых множеств в К^^хЕсли любые п + 1 из них пересекаются, то и вся совокупность в целом имеет непустое пересечение.

Крайние элементы и образующие.

Во второй главе изложены результаты, касающиеся образующих и крайних точек подполумодулей R^iaXiX, полученные автором в статье [84].

Будем говорить, что идемпотентный полумодуль V порождается множеством S-, если V является множеством конечных линейных (в смысле операций ф и О) комбинаций элементов из S. Следующее определение также хорошо известно, см. например работы Э. Ванье [74], [75].

Определение 13 Элемент х идемпотентного полумодуля V называется крайним, если из х = и © v следует, что х — и или х = v.

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

Определение 14 Рассмотрим отношение у < x/xj.

Элемент множества S С М" 1аХ-Х назовем j-минимальным, если он минимален по отношению <,-.

Следующие предложения, полученные автором, раскрывают роль отношения.

Теорема 15 Следующие утверждения эквивалентны:

1) элемент у является линейной комбинацией элементов х1,., хт €.

-^inax, х >

2) для любого номера j G 1,., п, такого, что yj ф 0, найдется вектор х1 такой, что xl.

Теорема 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 — SE. Тогда для любого и 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 (.

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/9 128..

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/403 441..

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/212 294..

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/308 166. •.

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/312 114..

37. M. Develin and B. Sturmfels. Tropical convexity. Documenta Math., 9:1−27, ¦ 2004. Also arXiv: math. MG/308 254..

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/605 078..

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 Jvan 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. DHilbert. 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/312 068..

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/9 904 024..

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/9 128..

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/102 144..

57. G. Litvinov and A. SobolevskiT. Idempotent interval analysis and optimization problems. Reliable Computing, 7(5):353−377, 2001. E-print arXiv: math. NA/101 152..

58. P. Loreti and M. Pedicini. An object oriented approach to idempotent analysis: Integral equations as optimal control problems. In 56], pages 187 208..

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:10 433−10 440, 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/604 454..

68. S. Sergeev. Max-plus definite matrix closures and their eigenspaces. Linear Algebra Appl, 421:182−201, 2007. E-pyint arXiv: math. MG /506 177..