Характеризации гомоморфизмов графов матричных отношений тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Максаев Артем Максимович

• Максаев Артем Максимович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Максаев Артем Максимович

1.1.1 Ориентированные графы

1.1.2 Матрицы над полукольцами

1.1.3 Скрамблинг-индекс

1.2 Обзор известных оценок для скрамблинг-индекса

1.3 Скрамблинг-индекс произвольных ориентированных графов

1.3.1 Локальный скрамблинг-индекс вершин орграфов и

1.3.2 Разбиения орграфа и скрамблинг-индекс

1.3.3 Описание орграфов с ненулевым скрамблинг-индексом

1.3.4 Верхние оценки на скрамблинг-индекс произвольных орграфов

1.4 Примитивность наборов матриц.

Многомерный скрамблинг-индекс

2 Линейные отображения, сохраняющие значения скрамблинг-индекса

2.1 Определения и обозначения

2.2 Линейные отображения булевых матриц, сохраняющие скрамблинг-индекс

2.2.1 Случай произвольного отображения

2.2.2 Случай биективного отображения и значений 1 ,шп скрамблинг-индекса

2.2.3 Случай биективного отображения и значения 0 скрамблинг-индекса

2.3 Отображения, сохраняющие А-скрамблинг матрицы

2.3.1 Обобщение скрамблинг-индекса. А-скрамблинг матрицы

2.3.2 Случай произвольного отображения

2.3.3 Случай биективного отображения

2.4 Обобщение на произвольные полукольца

3 Гомоморфизмы отношений Грина на моноиде квадратных матриц

3.1 Предварительные сведения

3.2 Отношения С и ^

3.2.1 Произвольные линейные отображения, сохраняющие отношения С и ^

3.2.2 Некоторые примеры

3.3 Отношение Н

3.4 Отношение

4 Пучковое условие для вырожденности и сохраняющие его отображения

4.1 Исторический обзор

4.2 Отображения невырожденных матриц, сохраняющие вырожденность пучков матриц

4.2.1 Сведение к отображениям, сохраняющим определитель

4.2.2 Выбор специального базиса матричной алгебры

4.2.3 Линейность отображений на множестве невырожденных матриц

4.2.4 Сведение к линейным отображениям, сохраняющим определитель

4.3 Доказательство основных результатов

5 Тотальный и регулярный графы многочлена

5.1 Цели и обозначения

5.2 Определение и основные свойства тотального и регулярного графов многочлена

5.3 Кликовое число регулярного графа многочлена

5.4 Вложенные подграфы тотального графа

Заключение

Введение

Введение диссертации (часть автореферата) на тему «Характеризации гомоморфизмов графов матричных отношений»

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

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

Актуальность темы исследования и степень её разработанности

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

Исследования графов, соответствующих отношениям на кольцах, начались сравнительно недавно. В 1988 году Бек [15] определил граф делителей нуля коммутативного кольца, позже Андерсон и Ливингстон [13] его модифицировали. До настоящего момента, кроме графов делителей нуля, активно изучались графы отношений коммутативности [5] и ортогональности [2], см. также библиографические ссылки, приведенные в работах.

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

Таким образом, главным вопросом, который мы рассматриваем, является задача характе-ризации (биективных) отображений, сохраняющих различные матричные отношения и, возможно, удовлетворяющих некоторым дополнительным условиям. Такие отображения также позволяют генерировать семейства матриц и графов с определенными свойствами. История этого вопроса восходит к работе Фробениуса [33], в которой были описаны линейные отображения комплексных квадратных матриц, сохраняющие определитель.

За последнее столетие было разработано множество методов, развивающих эту теорию. Подобными задачами занимались такие ученые, как Шур, Дьёдонне, Хуа, Маркус, Мойлз, Бисли, Шемрл и др. Для ознакомления с современным состоянием теории отображений, сохраняющих матричные инварианты, читатель может обратиться к обзору [51], где подроб-

но рассказывается про линейные отображения. Автором настоящей работы изучаются три направления этой теории, о которых рассказывается ниже.

Первое из них относится к функции скрамблинг-индекса. В 2009 году Акельбек и Кирк-ланд [10] ввели понятие скрамблинг-индекса примитивного ориентированного графа О, обозначаемого через к (О). Согласно их определению, к (О) равно наименьшему натуральному к такому, что для любых двух вершин а и Ь графа О найдется третья вершина и, для которой есть ориентированные пути длины к из а в и и из Ь в и (в путях допускаются повторения ребер и/или вершин). За счет рассмотрения матрицы смежности графа, это определение можно естественным образом распространить на примитивные неотрицательные матрицы.

Скрамблинг-индекс находит применения в теории марковских цепей, конечных автоматов и массовых коммуникаций. Например, при рассмотрении п х п матрицы А = (а^) конечной ациклической марковской цепи важную роль играет значение второго по абсолютной величине собственного значения А (наибольшее по модулю собственное значение А равно 1). Оно дает информацию об асимптотике скорости сходимости последовательности Ак, к ^ 1. В связи с этим, любая нетривиальная оценка на второе собственное значение таких матриц является значимой. В статье [10] была предъявлена такая оценка, использующая скрамблинг-индекс: для любого собственного значения А матрицы А, не равного 1, было показано, что

|А| ^ (п(А))1/к(л) < 1,

где

1 п Ti(A) = -maxY^ |aü - ají|.

2 i,j ¿—' í=i

Таким образом, исследование различных свойств скрамблинг-индекса и, в особенности, верхних оценок на него является актуальным. В той же статье [10] была установлена точная верхняя оценка на скрамблинг-индекс примитивного ориентированного графа: k(G) ^ (п 2 +1 , где n — порядок графа G. В других работах: Акельбека и Киркланда [11]; Акельбека, Фи-таля и Шена [9]; Чжена и Лью [24]; Лью и Хуанга [46] — эта теория получила дальнейшее развитие. А именно, появились верхние оценки на скрамблинг-индекс для различных семейств примитивных графов, а также во многих случаях были охарактеризованы графы, для которых достигается максимальное значение индекса. В работе [39] было предложено обобщение скрамблинг-индекса в зависимости от параметра 1 ^ A ^ n, полезное для задач теории массовых коммуникаций, было введено понятие A-скрамблинг матрицы.

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

инвариант. Несмотря на то, что в последние годы активно изучаются отображения, сохраняющие комбинаторные инварианты (например, перманент), см. главу 9 в статье [51], в литературе не были охарактеризованы отображения, сохраняющие значения скрамблинг-индекса.

Второй решаемой задачей является вопрос описания отображений, сохраняющих отношения Грина на моноиде матриц. Отношения, введенные Дж. Грином в 1951 году в работе [34] и позже названные в его честь, — это пять отношений эквивалентности, рассматриваемые на произвольной полугруппе, которые естественным образом возникают при изучении идеалов полугруппы и играют фундаментальную роль. Приведем определения отношений Грина для случая моноида.

Определение. Пусть M — моноид. Будем писать, что элементы a, b G M связаны одним из отношений Грина:

a R b, если aM = bM;

a L b, если Ma = Mb;

lui) a Jb, если MaM = MbM;

Uvj a H b, если a R b и a L b;

(v) a D b, если 3 c G M : a R c и c L b.

Авторы работы [35], мотивированные повышенным интересом к тропической алгебре в последние годы, классифицировали биективные линейные отображения, сохраняющие каждое из отношений Грина на моноиде n х n матриц над антинегативным полуполем. Таким образом, классификация была осуществлена для всех полуполей, кроме полей. Это является необычным, в свете того, что развитие теории полуполей во многом основано на обобщениях классических результатов теории полей, и побуждает исследовать эту проблему для случая полей, что и было сделано диссертантом.

Третья задача связана с отношением вырожденности суммы матриц. В 2008 году Д. Андерсон и А. Бадави [12] ввели понятие тотального графа коммутативного кольца с единицей, а в статье [6] аналогичные графы были рассмотрены и над некоммутативными кольцами. Для кольца квадратных матриц Mn(F) над полем F вершинами этого графа является все множество Mn(F), и две различные матрицы A,B соединяются ребром, если и только если det(A + B) = 0. Будем обозначать этот граф через 7n(F).

В 2017 году математики Чжоу, Вонг и Ма [61] доказали, что всякий автоморфизм а графа 72 (Fq), где Fq — конечное поле из q элементов нечетной характеристики, имеет следующий вид:

/ / a b \ \ ( f (a) f (b) \

Q для любой матрицы ( acbd ) G M2 (Fq )

а

ab c d

P

f(a) f(b) f(c) f(d)

или

а

ab cd

P

f (a) f (c) f (b) f (d)

Q для любой матрицы (ad) G M2 (Fq)

где Р^ — невырожденные матрицы над полем Fq, а f — некоторый автоморфизм поля Fq

На данный момент, вопрос описания автоморфизмов графа 7П(Е) при п > 2 остается открытым для произвольного поля Е и довольно сложным. Это обстоятельство побуждает изучить схожие вопросы, с ослабленным условием на автоморфизм — далее мы в хронологическом порядке приводим ряд результатов по этой тематике.

Первый из таких вопросов, как уже говорилось выше, был рассмотрен Фробениусом [33] в конце XIX века. Он показал, что линейные отображения кольца квадратных матриц над полем комплексных чисел Т: МП(С) ^ МП(С), которые сохраняют определитель, т.е.

ае^Т(А)) = ае^А) для всех А е Мга(С), имеют стандартный вид:

Т(А) = РАф для всех А е Мга(С)

или (1)

Т(А) = РАТд для всех А е МП(С),

где Р, д — невырожденные матрицы такие, что ае^Рф) = 1.

В 1949 году этот результат был обобщен Дьёдонне [28], который для произвольного поля Е доказал, что если линейное биективное отображение Т: МП(Е) ^ МП(Е) сохраняет свойство вырожденности (т.е. ае^А) = 0 ^ ае^Т(А)) = 0), то оно имеет вид (1), за исключением условия ае^рд) = 1.

Для нелинейного случая результат был получен Долинаром и Шемрлом [30] в 2002 году. Они показали, что если сюръективное отображение Т: МП(С) ^ МП(С) удовлетворяет следующему условию:

ае^А + АВ) = ае^Т (А) + АТ (В))

для всех А, В е МП(С) и всех А е С, — то оно линейно (а значит, стандартно).

Вскоре Тан и Ванг [57] получили обобщение этого результата для произвольного поля, в котором более п элементов. Ими было доказано, что если отображение Т: МП(Е) ^ МП(Е) удовлетворяет аналогичному условию:

ае^А + АВ) = ае^Т (А) + АТ (В)) (2)

для всех А, В е МП(Е) и всех А е Е, — то оно стандартно (1). Более того, они выяснили, что в случае сюръективности Т вывод останется прежним, если равенство (2) будет выполнено лишь для двух значений параметра А = А1, А2 е Е* таких, что (А1/А2)к = 1 при 1 ^ к ^ п — 2. В 2019 году Костара [26] усилил этот результат для полей из более п2 элементов, показав, что если Т сюръективно, то достаточно потребовать выполнения равенства (2) всего при одном значении параметра А = 0, — 1 — вывод будет аналогичен.

Наконец, в 2020 году Костара [27] рассмотрел пучковое условие для вырожденности для

пары отображений ф,ф: Мп(С) ^ Мп(С):

ёе^ЛА + В) = 0 ^^ ёе^Лф(А) + ф(В)) = 0 для всех А, В е Мп (С) и всех Л е С.

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

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

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

Цели и задачи работы

Целью диссертации является исследование вида гомоморфизмов и автоморфизмов графов следующих матричных отношений:

• отношений, определяемых значениями специальной функции на графах — скрамблинг-индекса, — над антинегативными коммутативными полукольцами с 1 и без делителей нуля;

• отношений Грина С, Я, Н, 3, " на моноиде матриц над полем;

• отношения вырожденности суммы матриц над полем.

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

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

• Точные верхние оценки на скрамблинг-индекс произвольного ориентированного графа, примеры, для которых достигается максимальное значение в верхних оценках.

• Характеризация линейных отображений, сохраняющих все значения скрамблинг-индекса на моноиде квадратных п х п матриц Мп(Б), где Б — антинегативное коммутативное

полукольцо с 1 и без делителей нуля. Описание линейных отображений, строго сохраняющих множество А-скрамблинг матриц при 1 < А ^ п.

• Характеризация линейных отображений, сохраняющих отношения Грина на моноиде квадратных п х п матриц Мп(Е), где Е — поле. В случае отношений £, ^ такое описание предъявлено при условии, что каждый многочлен степени п с коэффициентами в Е имеет корень в Е. В случае отношения Н — при условии, что Е — алгебраически замкнуто. Для отношения 3 поле произвольно.

• Характеризация отображений Т1,Т2: МП(Е) ^ МП(Е) для алгебраически замкнутого поля Е таких, что для всех А, В е МП(Е) и всех А е Е*

ае^А + АВ) = 0 ае^Т^А) + АТ2(В)) = 0,

если при этом существует невырожденная матрица О такая, что Т2(О) невырождена.

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

Объект и предмет исследования

Объект исследования — графы матричных отношений: порожденных значениями функции скрамблинг-индекса, отношений Грина на моноиде квадратных матриц над полем, отношения вырожденности суммы матриц над полем.

Предмет исследования — гомоморфизмы и автоморфизмы указанных графов, их свойства.

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

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

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

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

3. Характеризация линейных отображений, сохраняющих отношения Грина на моноиде квадратных матриц над полем при соблюдении определенных условий на поле.

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

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

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

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

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

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

Степень достоверности и апробация результатов

Результаты опубликованы в 10 статьях автора [62, 63, 64, 65, 66, 67, 68, 69, 70, 71] в журналах, индексируемых Web of Science, Scopus и RSCI. Из них 8 статей в рецензируемых научных изданиях, рекомендованных для защиты в диссертационных советах МГУ по физико-математическим специальностям. Автор выступал с докладами по результатам работы на спецсеминаре «Кольца, модули и матрицы» кафедры высшей алгебры механико-математического факультета МГУ имени М.В. Ломоносова.

Кроме того, автором были сделаны доклады по теме диссертации на следующих международных конференциях:

• 4th International Conference on Matrix Methods in Mathematics and Applications, (MMMA-2015), Сколково, Россия, 2015 (устный доклад).

• XXIII Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2016», Москва, Россия, 2016 (устный доклад).

• XXIV Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2017», Москва, Россия, 2017 (устный доклад).

• Fourth Russian Finnish Symposium on Discrete Mathematics, Турку, Финляндия, 2017 (устный доклад).

• A Tropical Panorama, Max Planck Institute for Mathematics in the Sciences, Лейпциг, Германия, 2018 (стендовый доклад).

• Международная алгебраическая конференция, посвященная 90-летию кафедры высшей алгебры, Москва, Россия, 2019 (устный доклад).

• XXVIII Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2021», Москва, Россия, 2021 (устный доклад в формате онлайн).

• 8th European Congress of Mathematics, Порторож, Словения, 2021 (устный доклад в формате онлайн).

Структура и объём работы

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

Содержание работы

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

Глава 1. В этой главе исследуются два вопроса:

• Получение верхних оценок на скрамблинг-индекс для произвольных ориентированных графов (орграфов).

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

В разделе 1.1 вводятся основные определения и обозначения, используемые на протяжении всего текста.

Пусть u,v — вершины орграфа G. Через u v мы обозначаем факт существования в G ориентированного пути длины k с началом u и концом v.

Определение (1.1.34). Скрамблинг-индексом орграфа G назовем наименьшее такое натуральное k, что Vu, v G V(G) 3w G V(G), для которого u w, v —4 w. Обозначим его через k(G). Если таких натуральных k нет, то скажем, что k(G) = 0. Пусть u,v G V(G). Введем следующие числа:

ku,v(G) = min{k G N | существует w G V(G): u w, v —4 w}.

Если множество в правой части пусто, то определим: ku,v(G) = 0. Будем называть данное число локальным скрамблинг-индексом для вершин u и v.

В разделе 1.2 проводится обзор известных результатов, касающихся верхних оценок на скрамблинг-индекс.

В разделе 1.3 представлены верхние оценки на скрамблинг-индекс произвольного орграфа.

Мы говорим, что G имеет (G1 ^ G2)-разбиение, если G1 и G2 — непустые подграфы G и выполнено следующее:

(i) V(G1) U V(G2) = V(G), то есть множества вершин орграфов G1 и G2 не пересекаются и образуют разбиение V(G);

(ii) для каждого ориентированного ребра e = (v1,v2) G E(G) выполнено: e G E(G1), или e G E(G2), или V1 G V(G1),v2 G V(G2).

Подграф H орграфа G назовем достижимым, если для каждой вершины u орграфа G

существует ориентированный путь с началом в u, оканчивающийся в некоторой вершине

H. Для достижимого орграфа H орграфа G и вершины u G V (G) определим расстояние

d(u, H) = min d(u,v), где d(u,v) — минимальная длина ориентированного пути с началом

vev (я) в u и концом в v.

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

Лемма (1.3.8). Рассмотрим (G1 ^ G2)-разбиение орграфа G. Предположим, что k(G) = 0. Тогда

1. k(G2) = 0 и k(G) ^ k(G2),

2. подграф G2 орграфа G достижим,

3. ku,v(G) ^ max{d(u, G2), d(v, G2)} + k(G2) для всех u, v G V(G),

4. k(G) ^ max d(u, G2) + k(G2) ^ |G1| + k(G2), где |G1| — порядок орграфа G1.

uev (Gi)

Пусть V1, V2,... , VS — компоненты сильной связности G. Показано, что если k(G) = 0, то ровно одна из этих компонент, скажем, Vs не имеет исходящих ребер в другие компоненты. Назовем (G1 ^ G^-разбиение орграфа G каноническим, если G2 = Vs и G1 = V U ... U VS-1.

Указанное понятие используется для доказательства критерия того, что k(G) = 0, и построения проверяющего это алгоритма.

Теорема (1.3.16). Для произвольного орграфа G следующие условия эквивалентны:

1. k(G) = 0.

2. В G найдется примитивный достижимый подграф H. Введем обозначение: K(n, s) = n — s + k(n, s) и

^ n, если s нечетно; (n-1) s, если s четно.

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

Теорема (1.3.20). Пусть С не сильно связный орграф порядка п с к(С) = 0. Рассмотрим его каноническое (С1 ^ С2)-разбиение. Пусть в — обхват С2 и |С2| = Ь ^ п — 1. Тогда к(С) ^ п—Ь+К(Ь, в). Если достигается равенство, то к(С2) = К(Ь, в) и найдется единственная вершина и орграфа С1, такая что ^(и, С2) = п — Ь.

Теорема (1.3.23). Пусть С не сильно связный орграф п с к(С) = 0. Рассмотрим его каноническое (С1 ^С2)-разбиение. Пусть |С2| = Ь. Тогда к(С) ^ п — Ь + (Ь-12) +1

Теорема (1.3.28). Пусть С не сильно связный орграф порядка п ^ 3. Тогда

< 1+[

Теорема (1.3.30). Пусть С — произвольный орграф порядка п ^ 3. Тогда

" (п — 1)2 + 1"

k(G) ^

2

В последних двух теоремах также классифицированы орграфы (с точностью до изоморфизма), на которых достигаются равенства.

В разделе 1.4 рассматривается обобщение понятия скрамблинг-индекса для раскрашенных в r цветов мультиграфов, здесь подразумеваются, что каждое ребро мультиграфа раскрашено в один из r цветов. Пусть D такой мультиграф и c = (ci, c2,... , cr) G Z+. Скажем, что u —4 v в D, где u,v G V(D), если в D найдется ориентированный путь из u в v, в котором встречается ровно c ребер цвета i = 1, 2, ...,r. Раскрашенный в r цветов мультиграф D называется примитивным, если 3c G Z+, такое что Vu,v G V(D) выполнено: u —Ц- v.

Определение (1.4.19). Пусть D — раскрашенный в r цветов мультиграф. Назовем положительное число k скрамблинг-индексом D, если оно наименьшее из таких чисел, что найдется некоторый набор c G Z+, |c| = k, что для любых u,v G V(D) существует w G V(D), такая что u —4 w, v —Ц- w. Обозначение: k(D). Если такого числа k не существует, то скажем, что k(D) = 0.

Основной результат раздела — обобщение критерия того, что скрамблинг-индекс муль-тиграфа не равен 0.

Теорема (1.4.26). Пусть D — раскрашенный в r цветов мультиграф автоматного типа (то есть из каждой его вершины выходят ребра всех цветов). Тогда следующие условия эквивалентны:

1. k(D) = 0;

2. ku,v(D) = 0 для любых u,v G V(D);

3. D содержит примитивный достижимый подграф H.

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

В разделе 2.1 вводятся основные определения и обозначения этой главы, освещается краткая история вопроса.

В разделе 2.2 характеризуются отображения, сохраняющие определенные значения скрамблинг-индекса. В первую очередь, интерес представляют экстремальные значения: 0,1, шп =

_ ~(п-1)2+1~ = 2 .

Через ^ обозначим антинегативное коммутативное кольцо с 1 и без делителей нуля. Пусть Т: Мп^ Мп(^), скажем, что Т сохраняет скрамблинг-индекс/,если V А е Мп(^) из того, что к(А) = /, следует, что к(Т(А)) = /. Будем говорить, что Т сохраняет скрамблинг-индекс, если оно сохраняет скрамблинг-индекс I для любого неотрицательного числа /. Скажем, что Т сохраняет ненулевой скрамблинг-индекс, если Т сохраняет скрамблинг-индекс I для любого / > 0.

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

Теорема (2.2.4). Пусть п ^ 3 и Т: Мп(В) ^ Мп(В) — аддитивное отображение, примитивно сохраняющее скрамблинг-индекс. Тогда Т биективно.

Теорема (2.2.26). Пусть п ^ 3 и Т: Мп(В) ^ Мп(В) — аддитивное биективное отображение,

сохраняющее значения 1 и шп

(п-1)2+1

2

такая, что для всех А е Мп(В) выполнено:

скрамблинг-индекса. Тогда существует Р е Рп

Т (А) = Р ТА Р.

Теорема (2.2.36). Пусть п ^ 3 и Т: Мп(В) ^ Мп(В) — аддитивное биективное отображение, сохраняющее скрамблинг-индекс 0. Тогда существует Р е Рп такая, что для всех А е Мп(В) выполнено:

Т (А) = Р ТА Р.

В разделе 2.3 рассматривается обобщение скрамблинг-индекса, основанное на понятии А-скрамблинг матрицы. Цель данного раздела — характеризация линейных отображений матриц над полукольцом ^, сохраняющих множество А-скрамблинг матриц.

Определение (2.3.8). Пусть А е Мп(^) и пусть А — целое число, такое, что 1 ^ А ^ п. Матрица А называется А-скрамблинг матрицей, если для любых индексов г1,г2,... , ¿д е {1, 2,... , п} найдется индекс ] е {1, 2,..., п}, для которого

А^) = 0, А(«2,^) = 0,..., А^) = 0.

Иными словами, любые А строк матрицы А пересекаются с некоторым столбцом матрицы А лишь по ненулевым элементам.

Теорема (2.3.15). Пусть 1 < А ^ п и Т: Мп(В) ^ Мп(В) — аддитивное отображение, строго сохраняющее множество Лв(п, А). Тогда Т — биекция.

Теорема (2.3.30). Пусть п ^ 3, 1 <А<п и Т: Мп(В) ^ Мп(В) — некоторое отображение. Тогда Т — аддитивное биективное отображение, сохраняющее множество Л(п,А), в том и только том случае, когда найдутся матрицы Р, ф € Рп, такие что

Т (А) = РАф.

В разделе 2.4 результаты подытоживаются и обобщаются на произвольные коммутативные антинегативные кольца с 1 и без делителей нуля. Через А о В обозначается произведение Адамара или Шура (поэлементное произведение) матриц А и В.

Теорема (2.4.13). Пусть п ^ 3 и Т: Мп(^) ^ Мп(^) — линейное отображение. Следующие условия эквивалентны:

1. Т — сюръективно и сохраняет скрамблинг-индекс 1 и шп;

2. Т — сюръективно и сохраняет скрамблинг-индекс 0;

3. Т имеет следующий вид:

Т(А) = Рт(А о В) Р

для любой матрицы А € Мп(^), где Р € Рп, а В € Мп(^) — матрица, каждый элемент которой обратим в ^.

Теорема (2.4.14). Пусть п ^ 3 и Т: Мп(^) ^ Мп(^) — линейное отображение. Тогда Т сохраняет ненулевой скрамблинг-индекс в том и только том случае, когда Т(А) = Рт(АоВ) Р для произвольной матрицы А € Мп(^). Здесь Р € Рп и В € Мп(^) — матрица, все элементы которой отличны от 0.

Теорема (2.4.16). Пусть п ^ 2, 1 <А ^ п и Т: Мп(^) ^ Мп(^) — линейное отображение. Тогда Т строго сохраняет множество Л^(п, А) в том и только том случае, когда:

а) при А < п: найдутся перестановочные матрицы Р и ф порядка п и матрица В € Мп (^), все элементы которой отличны от 0, такие, что Т(А) = Р(А о Вдля всех А € Мп(^);

б) при А = п: найдутся перестановки т, а1,... , ап € $п такие, что для всех 1 ^ г, ^ п выполнено Т(Е,-) = Ь^ЕЦ(¿),г(,•), где Ь^ € ^ \ {0}.

Теорема (2.4.21). Пусть п ^ 2, 1 <А ^ п и Т: Мп(^) ^ Мп(^) — линейное сюръективное отображение. Тогда Т сохраняет множество Л^ (п, А) в том и только том случае, когда:

а) при А < п: найдутся перестановочные матрицы Р и ф порядка п и матрица В € Мп(^), все элементы которой обратимы в ^, такие, что Т(А) = Р(А о В)ф для всех А € Мп(^);

Список литературы диссертационного исследования кандидат наук Максаев Артем Максимович, 2022 год

Литература

[1] Д. С. Ананичев, М. В. Волков, В. В. Гусев. Примитивные орграфы с большими экспонентами и медленно синхронизируемые автоматы, Зап. научн. сем. ПОМИ, 2012, том 402, 9-39.

[2] Б. Р. Бахадлы, А. Э. Гутерман, О. В. Маркова, Графы, определенные ортогональностью. — Зап. научн. семин. ПОМИ 428 (2014), 49-80.

[3] Ф. Харари. Теория графов, Издательство «Мир», 1973.

[4] S. Akbari, M. Aryapoor, M. Jamaali. Chromatic number and clique number of subgraphs of regular graph of matrix algebras, Linear Algebra Appl., 436 (2012) 2419-2424.

[5] S. Akbari, H. Bidkhori, A. Mohammadian (2008) Commuting Graphs of Matrix Algebras, Communications in Algebra, 36:11, 4020-4031.

[6] S. Akbari, F. Heydari, The regular graph of a non-commutative ring, Bulletin of the Australian Mathematical Society, 89(1) (2014), pp. 132-140.

[7] S. Akbari, M. Jamaali, S.A. Seyed Fakhari. The clique numbers of regular graphs of matrix algebras are finite, Linear Algebra and its Applications, 431 (2009) 1715-1718.

[8] M. Akelbek. A Joint Neighbour Bound for Primitive Digraphs, Ph.D. Thesis, University of Regina, 2008.

[9] M. Akelbek, S. Fital, J. Shen. A bound on the scrambling index of a primitive matrix using Boolean rank, Linear Algebra Appl. 431 (2009) 1923-1931.

[10] M. Akelbek, S. Kirkland. Coefficients of ergodicity and scrambling index, Linear Algebra Appl. 430 (2009) 1111-1130.

[11] M. Akelbek, S. Kirkland, Primitive digraphs with the largest scrambling index, Linear Algebra Appl. 430 (2009) 1099-1110.

[12] D. F. Anderson, A. Badawi, The total graph of a commutative ring, J. Algebra, 320 (2008), pp. 2706-2719.

[13] D. F. Anderson, P. S. Livingston, The zero-divisor graph of a commutative ring. — J. Algebra 217, No. 2 (1999), 434-447.

[14] L. B. Beasley, A. E. Guterman. The characterization of operators preserving primitivity for matrix k-tuples, Linear Algebra Appl. 430 (2009) 1762-1777.

[15] I. Beck, Coloring of commuatitive rings. — J. Algebra 116, No. 1 (1988), 208-226.

[16] M. Bocher, Introduction to Higher Algebra, Dover, New York, 2004.

[17] R. Bott and J. Milnor, On the parallelizability of the spheres, Bull. Amer. Math. Soc. 64 (1958), 87-89.

[18] P. Botta, Linear maps that preserve singular and nonsingular matrices, Linear Algebra Appl. 20(1) (1978), 45-49.

[19] R. A. Brualdi, B. Liu, Generalized exponents of primitive directed digraphs, J. Graph Theory 14 (1990) 483-499.

[20] R. A. Brualdi, H. J. Ryser. Combinatorial matrix theory. Encyclopedia of Mathematics and its Applications, vol. 39, Cambridge University Press, Cambridge, 1991.

[21] N. G. Bruijn, P. Erdos. A colour problem for infinite graphs and a problem in the theory of relations, Indigationes Mathematicae, 13 (1951) 371-373.

[22] P.J. Cameron. Research problems from the BCC22, Discrete Math, 311 (2011) 1074-1083.

[23] J. Cerny, "Poznamka k homogennym eksperimentom s konecnymi automatami", Matematicko-fyzikalny Casopis Slovensk. Akad. Vied, 14:3 (1964), 208-216

[24] S. Chen, B. Liu. The scrambling index of symmetric primitive matrices, Linear Algebra Appl. 433 (2010) 1110-1126.

[25] H. H. Cho and H. K. Kim. Competition indices of strongly connected digraphs, Bull. Korean Math. Soc. 48 (2011), No. 3, 637-646.

[26] C. Costara, Nonlinear determinant preserving maps on matrix algebras, Linear Algebra Appl., 583 (2019), pp. 165-170.

[27] C. Costara, Nonlinear invertibility preserving maps on matrix algebras, Linear Algebra Appl., 602 (2020), pp. 216-222.

[28] D. J. Dieudonne, Sur une generalisation du groupe orthogonal a quatre variables, Arch. Math. 1 (1949), pp. 282-287.

[29] R. L. Dobrushin. Central limit theorem for non-stationary Markov chains, I, II, Theory Prob. Appl., 1, 65-80, 329-383.

[30] G. Dolinar, P. Semrl, Determinant preserving maps on matrix algebras, Linear Algebra Appl. 348 (2002), pp. 189-192.

[31] E. Fornasini, M. Valcher. Directed graphs 2D state models and characteristic polynomials of irreducible matrix pairs, Linear Algebra Appl. 263 (1997) 275-310.

[32] E. Fornasini, M. Valcher. Primitivity of positive matrix pairs: algebraic characterization graph theoretic description and 2D systems interpretation, SIAM J. Matrix Anal. Appl. 19 (1998) 71-88.

[33] G. Frobenius, Uber die Darstellung der endlichen Gruppen durch lineare Substitutionen, Sitzungsber. Preuss. Akad. Wiss. Berlin, 1897, 994-1015.

[34] J. A. Green. On the structure of semigroups. Annals of Math. 54 (1951), 163-172.

[35] A. Guterman, M. Johnson, M. Kambites. Linear isomorphisms preserving Green's relations for matrices over anti-negative semifields, Linear Algebra Appl. 545 (2018) 1-14.

[36] C. Hollings, M. Kambites, Tropical matrix duality and Green's D relation, J. Lond. Math. Soc. 86(2) (2012) 520-538.

[37] J.M. Howie, Fundamentals of Semigroup Theory, Oxford University Press, 1995.

[38] L.K. Hua, A theorem on matrices over a field and its applications, J. Chinese Math. Soc. (N.S) 1 (1951), 110-163.

[39] Y. Huang, B. Liu. Generalized scrambling indices of a primitive digraph, Linear Algebra Appl. 433 (2010) 1798-1808.

[40] M. Kervaire, Non-parallelizability of the n-sphere for n > 7, Proc. National Acad. Sci. 44 (1958), 280-283.

[41] H. Kim. Generalized competition index of a primitive digraph, Linear Algebra and its Applications 433 (2010) 72-79.

[42] H. Kim. Scrambling index set of primitive digraphs, Linear Algebra Appl. 439 (2013) 1886-1893.

[43] H. Kim, S. G. Park. A bound of generalized competition index of a primitive digraph, Linear Algebra and its Applications 436 (2012) 86-98.

[44] S. Lang. Algebra, 3rd edition, Springer-Verlag, New York (2002).

[45] C. Lautemann, Linear transformations on matrices: rank preservers and determinant preservers (note), Linear and Multilinear Algebra, 10(4) (1981), 343-345.

[46] B. Liu, Y. Huang. The scrambling index of primitive digraphs, Computers and Mathematics with Applications 60 (2010) 706-721.

[47] Mulyono, S. Suwilo. The scrambling index of two-colored Wielandt digraph, Universal Journal of Applied Mathematics 2(6) 250-255, 2014.

[48] J. Okniñski, Semigroups of Matrices, Series in Algebra, 6, World Scientific, 1998.

[49] D. D. Olesky, B. Shader, P. van den Driessche. Exponents of tuples of nonnegative matrices, Linear Algebra and its Applications 356 (2002) 123-134.

[50] A. Paz. Introduction to Probabilistic Automata, Academic Press, New York, 1971.

[51] S. Pierce and others, A survey of linear preserver problems, Linear and Multilinear Algebra, 33 (1992), 1-119.

[52] U. G. Rothblum, C. P. Tan. Upper bounds on the maximum modulus of subdominant eigenvalues of nonnegative matrices, Linear Algebra Appl. 66 (1985) 45-86.

[53] C. de Seguins Pazzis, The singular linear preservers of non-singular matrices, Linear Algebra and its Applications, 433 (2010), 483-490.

[54] E. Seneta. Nonnegative Matrices and Markov Chains, Springer-Verlag, New York, 1981.

[55] B. L. Shader, S. Suwilo. Exponents of nonnegative matrix pairs, Linear Algebra and its Applications 363 (2003) 275-293.

[56] B. Swan. Competition Digraphs, Master Thesis, Auburn University, 2012.

[57] V. Tan, F. Wang, On determinant preserver problems, Linear Algebra Appl., 369 (2003), pp. 311-317.

[58] R. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), (1972) 146-160.

[59] I. Tomon. On the chromatic number of regular graphs of matrix algebras, Linear Algebra Appl, 475 (2015) 154-162.

[60] M. V. Volkov. Synchronizing Automata and the Cerny Conjecture, Language and Automata Theory and Applications, Lect. Notes Comput. Sci. 5196(2008), 11-27.

[61] J. Zhou, D. Wong, X. Ma, Automorphism group of the total graph over a matrix ring, Linear and Multilinear Algebra 65(3) (2017), 572-581.

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

Статьи в рецензируемых научных изданиях, рекомендованных для защиты в диссертационном совете МГУ по специальности

[62] A. E. Guterman, A. M. Maksaev. Maps preserving scrambling index, Linear and Multilinear Algebra, 66(4), 840-859 (2018). А.М. Максаевым доказаны теоремы 3.2 и 4.10.

DOI: 10.1080/03081087.2017.1329814

Журнал индексируется в WoS, Scopus. IF: SJR 0.688.

[63] A. E. Guterman, A. M. Maksaev. Maps preserving matrices of extremal scrambling index, Special Matrices, 6, 166-179 (2018). А.М. Максаевым доказаны теоремы 2.7 и 3.9.

DOI: 10.1515/spma-2018-0014

Журнал индексируется в WoS, Scopus. IF: SJR 0.647.

[64] A. E. Guterman, A. M. Maksaev. Additive maps preserving scrambling index are bijective, Acta Sci. Math (Szeged), 84, 19-38 (2018). А.М. Максаевым доказаны теоремы 2.1 и 3.6.

DOI: 10.14232/actasm-017-092-2

Журнал индексируется в Scopus. IF: SJR 0.39.

[65] A. E. Guterman, A. M. Maksaev. Preserving A-scrambling matrices, Fundamenta Informaticae, 162, 119-141 (2018). А.М. Максаевым доказаны теоремы 2.20, 3.6 и 4.9.

DOI: 10.3233/FI-2018-1717

Журнал индексируется в WoS, Scopus. IF: SJR 0.311.

[66] A. E. Guterman, A. M. Maksaev. Upper bounds on scrambling index for non-primitive digraphs, Linear and Multilinear Algebra, 69(11), 2143-2168 (2021). А.М. Максаевым доказаны теоремы 4.1, 5.1, 5.4, 5.7, 6.1 и 6.5.

DOI: 10.1080/03081087.2019.1663139

Журнал индексируется в WoS, Scopus. IF: SJR 0.

[67] A. Guterman, M. Johnson, M. Kambites, A. Maksaev. Linear functions preserving Green's relations over fields, Linear Algebra Appl., 611, 310-333 (2021). А.М. Максаевым доказаны теоремы 3.16, 3.17 и 5.3. Также им доказана теорема 5.2 при n ^ 3.

DOI: 10.1016/j.laa.2020.10.033

Журнал индексируется в WoS, Scopus. IF: WoS 1.401, SJR 0.951.

[68] А. М. Максаев. Отображения, строго сохраняющие А-скрамблинг матрицы, Зап. научн. сем. ПОМИ, 482, 231-243 (2019);

English transl.: J. Math. Sc., 249(2), 263-270 (2020).

DOI: 10.1007/s10958-020-04940-9

Журнал индексируется в Scopus, RSCI. IF: SJR 0.330.

[69] A.E. Guterman, A.M. Maksaev, V.V. Promyslov. Pairs of maps preserving singularity on subsets of matrix algebras, Linear Algebra Appl., 644, 1-27 (2022). А.М. Максаевым доказаны теоремы 2.6 и 4.13.

DOI: 10.1016/j.laa.2022.02.035

Журнал индексируется в WoS, Scopus. IF: WoS 1.401, SJR 0.951.

Другие публикации

[70] A. E. Guterman, A. M. Maksaev. On the scrambling index of non-negative matrices, Proceedings of the Fourth Russian Finnish Symposium on Discrete Mathematics, 57-59 (2017).

https://www.utupub.fi/bitstream/handle/10024/143322/TUCSLN26.pdf

[71] А.М. Максаев, В.В. Промыслов. О тотальном и регулярном графах многочлена, Фундаментальная и прикладная математика, 23(4), 113—142 (2021). А.М. Максаевым доказаны теоремы 4.2, 6.7 и 6.10. Результаты раздела 2, а также теорема 4.8 получены совместно с В.В. Промысловым.

http://www.mathnet.ru/links/7cfd2bdb14f39af07b3394067b51b1a9/fpm1913.pdf Журнал индексируется в RSCI.