Значения функции перманента (0,1)-матриц и (-1,1)-матриц тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Таранин Константин Александрович

• Таранин Константин Александрович
• кандидат наук
• 2022

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

1.2.1 Оценка снизу

1.2.1.1 Похожие матрицы и свойства их перманента

1.2.1.2 Вычисление перманентов некоторых последовательностей похожих матриц

1.2.1.3 Доказательство основного результата

1.2.2 Значения перманента, близкие к максимальному

2 (-1,1)-матрицы

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

2.1.1 Проблема обращения перманента в

2.1.2 Использование перманента (-1,1)-матриц

2.2Обращение перманента в

2.2.1 Делимость значений

2.2.1.1 Формула для перманента ±1-матрицы

2.2.1.2 Вспомогательные факты

2.2.1.3 Делимость перманентов на степени двойки

2.2.1.4 Примеры

2.2.2 Матрицы с нулевым перманентом

2.2.2.1 Общий случай

2.2.2.2 Матрицы порядка п <

2.2.2.3 Матрицы порядка

Заключение

Введение

Введение диссертации (часть автореферата) на тему «Значения функции перманента (0,1)-матриц и (-1,1)-матриц»

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

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

Определение (1.1.1)1. Пусть А - матрица порядка п над полем действительных чисел. Функция, сопоставляющая матрице А число

где - группа перестановок на м ножестве {1, 2,...,п}, называется функцией

А

Функция перманента была впервые введена Бине [5] и Коши [10], а её современное название ей дал Мюир [27], который также доказал для перманента аналоги некоторых базовых свойств детерминанта. Литтлвуд и Ричардсон [23, 24] ввели понятие иммананта, обобщающее перманент и детерминант.

Важное отличие перманента от детерминанта состоит в том, что он не инвариантен по отношению к одному из преобразований Гаусса — прибавлению строки с коэффициентом к другой строке (аналогично в случае столбцов). Более общо, перманент не мультипликативен. Как следствие, к нему не применимы методы быстрого вычисления, применимые в случае детерминанта. Более того, на данный момент не найдено алгоритма вычисления перманента полиномиальной или меньшей сложности. Один из наиболее быстрых алгоритмов, вычисляющий перманент за 0(2п-1п) итераций, где п — порядок матрицы, принадлежит Райзеру (см. [30, глава 2 теорема 4.1] или [2, глава 7 пункт 2]). Напомним, что задачей класса #Р называется любая вычислительная задача, для которой соответствующая задача разрешимости лежит в классе ЖР; #Р-сложной называется любая задача, к которой за полиномиальное время сводятся все задачи классаа #Р-полной называется любая #Р-сложная задача из класса #Р (определение 1.1.10).

1 Здесь и далее во введении после названия утверждения или определения указан его номер в основном тексте диссертации, т.е. в главах 1 и 2.

Вэлиант [32] доказал, что вычисление перманента является #Р-сложной задачей, а для (0,1)-матрнц — #Р-полпой, т.е. из наличия полиномиального алгоритма вычисления перманента следовало бы равенство Р = МР. Читателя, интересующегося вопросами алгоритмической сложности в связи с вычислением перманента и смежными задачами, адресуем к работам Кука [12], Гэри и Джонсона [15], Ласло и Пламмера [25], а также Карпа [18].

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

(0, 1)

матриц с целыми неотрицательными элементами возникает в задачах теории механизмов в экономике, использующей теорию графов как один из инструментов, а (-1, 1)

(0, 1) (-1, 1) кнм образом, принимая во внимание используемость в приложениях и сложность вычисления функции перманента, можно заключить, что исследование расположения (реализации) её значений является актуальной задачей. Это исследование традиционно ведётся в двух направлениях: предложенный Полна [29] вопрос конвертации перманента и детерминанта, историю развития которого можно найти в книге [26] МакКуэйга, и вопрос непосредственного поиска значений перманента и соответствующих матриц, о котором далее пойдёт речь в диссертации.

Одним из первых результатов, относящихся к проблеме реализации значений перманента, был критерий обращения в 0 перманента неотрицательной матрицы, полученный Фробениусом [14] и Кёнигом [20]. Аналогичные критерии для неболь-

(0, 1)

Моцкином и Уэлчем [16]. Бруальди и Ньюмен [6] получили следующую нижнюю оценку на границу значений перманента, принимаемых последовательно: все целые числа от 0 до 2П-1 включительно являются значениями функции перманента на множестве (0,1)-матриц порядка п (теорема 1.1.16). (-1, 1)

лизации значений перманента является проверка обращения перманента в 0, что

продиктовано спецификой использования этого класса матриц: например, в квантовой физике нулевой перманент знакового портрета системы уравнений, описывающей некоторую квантовую систему, означает отсутствие ненулевого решения этой системы уравнений, что в свою очередь гарантирует квантовую запутанность системы (подробнее см. пример 2.1.6). Достаточным условием того, что перманент целочисленной матрицы не обращается в ноль, является отсутствие делимости на натуральное число. Классическими результатами в этом направлении являются результаты Кройтера и Сейфтера о делимости на степени 2 [22, предложение 4 и лемма 5], см. предложения 2.2.12-2.2.14 в разделе 2.2.1 диссертации, а одним из наиболее современных результатов является классификация всех(—1,1)-матриц

(-1)

и их перестановки, полученная Кимом, Кэ и На [19, теорема 3.6] в 2015 году. Альтернативная формулировка последнего результата, учитывающая также эквивалентность с точностью до транспонирования, приведена с доказательством в разделе 2.2.2 диссертации (теорема 2.2.29).

Полученные в диссертации результаты относятся к направлениям исследований, заданным теоремой 1.1.16 Бруальди и Ньюмена и предложениями 2.2.122.2.14 Кройтера и Сейфтера, т.е. непосредственно к реализации значений перманента (0,1)-матриц и к делимости па степени 2 и обращению в 0 перманента (-1, 1)

и Ньюмена, сформулирован и доказан критерий делимости перманента на более высокую степень 2, чем у Кройтера и Сейфтера, а также классифицированы все (-1, 1)

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

Целью диссертации является исследование реализации значений функции пер-

(0, 1) (-1, 1) исследование вопроса последовательной реализации значений перманента для(0,1)-матриц, а также обращения перманента в 0 и делимости па степени 2 для (-1,1)-матриц.

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

Следующие результаты диссертации выносятся на защиту:

• Улучшение оценки Бруальди-Ньюмена границы последовательных значений перманента (0,1)-матриц более чем в 2 раза.

• Вычисление наибольшего нечётного и наибольшего не делящегося на 3 значения перманента. Предъявление для всех простых р < п и натуральных

2 < ] < п, матриц, па которых функция перманента достигает наибольшего не делящегося на р значения и наибольшего не делящегося на ]! значения соответственно. Оценка количества значений перманента на множестве (0,1)-матриц порядка п, превосходящих наибольший нечётный перманент.

(-1, 1)

позволяющей вычислять степень вхождения 2 как простого сомножителя в значение перманента. Прямые доказательства предложений Кройтера и Сейфтера о делимости перманента на степени 2. Предъявление и доказательство критерия делимости перманента (-1,1)-матрпц на 2п—°£2п\+1.

• Классификация (-1,1)-матриц порядка не более 5 с перманентом 0 с точностью до эквивалентности.

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

(0, 1)

ка п, (-1,1)-матриц порядка п и соответствующие множества значений функции перманента, где п € N.

Предметом исследования является функция перманента на множествах квадратных (0,1)-матриц и (-1,1)-матриц и её свойства.

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

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

• Оценка Бруальдн-Ньюмена границы последовательных значений перманен-

(0, 1) 2

• Получена оценка количества значений перманента па Ап, превосходящих

г(п+1)!п о

Р пе ]• ^ качестве промежуточных результатов:

— Найдены наибольшее нечётное значение перманента и наибольшее не делящееся на 3 значение перманента на Ап.

— Для всех простых р < п найдены матрицы, перманенты которых являются наибольшими на Ап среди те делящихся па р.

— Для всех натуральных 2 < ] < п найдены матрицы, перманенты которых являются наибольшими на Ап среди не делящихся на ]!.

• Получена формула для перманента (-1,1)-матриц, позволяющая вычислять степень вхождения 2 как простого сомножителя в значение перманента. Получены прямые доказательства предложений Кройтера и Сейфтера о делимости перманента на степени 2. Найден критерий делимости перманента (-1,1)-матриц па 2п~^1оё2п]+1.

(-1, 1)

ка не более 5 с перманентом 0.

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

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

Теоретическая и практическая

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

значимость

Полученные результаты могут быть ис-комбинаторики, теории графов, теории

сложности вычислений, экономики, генетики, квантовой механики.

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

Результаты опубликованы в 4 работах автора [37, 38, 39, 40] в журналах, нндек-сируемых Web of Science, Scopus и RSCI. Автор выступал с докладами по результатам работы на научно-исследовательском семинаре кафедры высшей алгебры механико-математического факультета МГУ и на семинаре «Кольца, модули и матрицы» кафедры высшей алгебры.

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

• XXI международная конференция студентов, аспирантов и молодых учёных «Ломоносов-2014», Москва, 2014.

• XXII международная конференция студентов, аспирантов и молодых учёных «Ломоносов-2015», Москва, 2015.

• 4th International Conference on Matrix Methods in Mathematics and Applications (MMMA-2015), Москва, Сколково, 2015.

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

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

• XXV международная конференция студентов, аспирантов и молодых учёных «Ломоносов-2018», Москва, 2018.

• Международная алгебраическая конференция, посвящённая 110-летию со дня рождения профессора А. Г. Куроша (1908-1971), Москва, 2018.

• XXVII международная конференция студентов, аспирантов и молодых учёных «Ломоносов-2020», Москва, 2020.

Структура работы

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

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

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

Глава 1. В главе 1 исследуются два вопроса, относящиеся к теме реализации значений перманента (0,1)-матриц:

1. Поиск границы подряд идущих значений перманента.

2. Описание и оценка количества значений, превосходящих наибольшее нечётное значение перманента.

В разделе 1.1.1 введены основные определения и обозначения, а в разделе 1.1.2 приведены примеры использования перманента (0,1)-матриц.

Пусть An обозначает множество (0,1)-матриц порядка n (обозначение 1.1.3). Граница подряд идущих значений перманента определяется следующим образом. Определение (1.1.17). Число Bn назовём границей подряд идущих значений перманента на An, если Bn — наименьшее натуральное число с тем свойством, что не существует A е An с per (A) = Bn + 1.

Из теоремы Бруальди-Ньюмена (1.1.16) следует, что Bn > 2n-1. Однако, как показано в разделе 1.2.1, этот результат может быть улучшен более чем в 2 раза. Теорема (1.2.23). При n > 6 Bn > f 2n.

Всюду далее строки и столбцы матриц называются линиями (определение 1.1.2). В разделе 1.2.2 исследуются значения перманента, превосходящие наибольшее нечётное значение. Для этого сначала доказываются следующие два свойства де-

(0, 1)

Следствие (1.2.31). Пусть р — простое чиело, 2 < p < n. Матрица с наибольшим на ^ не делящимся нар значением перманента имеет в точности n — p +1 нулевых

элементов, причем никакие два из них не расположены на одной линии. Следствие (1.2.32). Пусть ] — целое чиело, 2 < ^ < п. Матрица с наибольшим на Ап не делящимся на ]! значением перманента имеет в точности п - ] + 1 нулей, причём никакие два из них не расположены на одной линии.

После этого вычисляются наибольший нечётный перманент и наибольший не кратный 3 перманент, [х] обозначает ближайшее к числу х целое число, а {х}/ = |х — [х] | (определение 1.1.5).

Теорема (1.2.33). Наибольшее нечётное значение функции перманета наАп равно г(п+1)И •• г(п+1)И ^

| V-ПрИчем ) V->_ I, <

L пе J' 1 пе J 1 —

пе J' * ^ пе -> 1 — п(п+2) '

Теорема (1.2.34). Если п > 1, то наибольшее не делящееся на 3 значение функции перманента па Ап равно [(п-2)! (п2 + п - 1)], причём {(п-2)! (п2 + п - 1)}/ < ^ззп• Далее эти результаты используются для получения оценки на количество значений перманента, превосходящих наибольшее нечётное значение. Теорема (1.2.35). При п > 4 на промежутке

"(п+1)!' , п!

пе

количество значении

функции перманента на множестве матриц Ап не превосходит

е-2

((п - 1)! + (п - 3)!)+ 2 +(-1)п-1 Е

п /

(-1)'

к

к=2

Глава 2 посвящена вопросам обращения в 0 и делимости значений перманента (-1, 1)

1. Зависимость делимости перманента на степени двойки от порядка матрицы.

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

(-1)

В разделе 2.1.1 введены основные определения и обозначения, а в разделе 2.1.2

(-1, 1)

физике, связывающий перманент с понятием квантовой запутанности.

Множество (-1,1)-матриц порядка п обозначим через (обозначение 2.1.1). Для данной матрицы А € количество всевозможных различиых наборов (-1) мощности ^ таких, что никакие два элемента (-1) из набора не расположены па одной линии, обозначим через к (определение 2.2.1 и обозначение 2.2.2). В

разделе 2.2.1 получены следующие результаты. Сначала доказана формула для

(—1, 1)

Лемма (2.2.3). Пусть A е Тогда

n

per (A) = £(—2)j • kj • (n — j)!. j=0

Далее эта формула использована для получения прямого доказательства предложений 2.2.12-2.2.14, а также для получения нового результата, заключаещегося в теореме ниже, где через M = M(n) обозначено множество таких целых неотрицательных чисел m, меньших n, что n — m в своём двоичном представлении имеет ровно t — 1 единиц, где t определяется неравенствами 2t—1 < n < 2t — 1 (определение 2.2.15).

Теорема (2.2.16). Рассмотрим n е N 2t—1 < n < 2t — 1 и M(n). Для любой A е верно, что

per (A) : 2n—i+2 ^^^да и только тогда, когда ^^ km : 2.

mem

В том же разделе выведено несколько следствий теоремы 2.2.16.

В разделе 2.2.2 с помощью ряда вспомогательных утверждений (леммы 2.2.232.2.26, 2.2.28 и 2.2.30, следствие 2.2.27) с точностью до перестановок линий, домно-(—1) (—1, 1) порядка n = 5 с перманентом 0 (теорема 2.2.31), а также приведён результат для n = 4 (теорема 2.2.29).

Заключение. В заключении перечислены основные результаты работы.

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

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

Глава 1

(ОД)-матрицы

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

1.1.1 Проблема расположения значений перманента на действительной оси

Ап А

реГ (А) = ^ Й1СТ(1) а2а(2) • • • апа(п),

где 5п - группа перестановок на м ножестве {1, 2,...,п}, называется функцией

А

Определение 1.1.2. Линиями называют строки и столбцы матриц.

Обозначение 1.1.3. Вслед за Бруальди и Ньюменом [6] через Ап обозначим подмножество (0,1)-матриц из Мп, то есть матриц с элементами из множества {0,1} С К.

Заметим, что перманентами матриц из Ап являются целые неотрицательные числа со стандартным отношением порядка.

п

чим </п.

х

частью ж, назовём такое целое число [ж], та о |ж - [х]| < Для чисел вида ^кт1, к € Ж, целая часть не определена. Если целая часть определена, то число {ж}/ = |ж - [ж] | мы будем называть меньшей дробной частью ж. Нижняя целая часть ж — это такое целое число [ж], что [ж] < ж < [ж] +1. Дробной частью вещественного числа ж называется число {ж} = ж - [ж].

Пример 1.1.6. Непосредственно проверяется, что при фиксированном п € N наибольшим значением перманента как функции на Ап является п!. Это значение достигается на матрице </п.

Пример 1.1.7. Значения 0 и 1 также достигаются - на нулевой и единичной матрице соответственно.

Пример 1.1.8. Число п! — 1 не является перманентом ни для какой (0,1)-матрицы п

Утверждение 1.1.9. Наибольший перманент на Ап\{</п} равен п! — (п — 1)!.

Доказательство. Из определения перманента следует, что перманент (0,1)-матрицы не увеличивается при замене на ноль любого элемента, равного единице, при условии, что другие элементы остаются неизменны: в сумме а^^^о-^) • • • апа(п) каждое слагаемое равно либо нулю, либо единице, и при замене некоторого элемента 1 в матрице на 0 количество нулевых слагаемых в сумме не убывает. Следовательно, перманент любой матрицы с 2 и более нулевыми элементами не превосходит перманента матрицы с одним нулевым элементом, равногоп! — (п — 1)!. □

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

Определение 1.1.10. Задача вида «вычислить /(ж)», где / - функция из множества {0,1}* конечных последовательностей 0 и 1 в натуральный ряд N5 принадлежит классу сложности #Р, если существует такая недетерминированная машина Тьюринга М, что /(ж) совпадает с количеством допускающих состояний М на ж для любого ж € {0,1}*. Задача называется #Р-сложной, если к ней за полиномиальное время сводится любая задача класса #Р. Если #Р-сложная задача находится в классе #Р, то она называется #Р-полной.

Иначе говоря, вычислительная задача принадлежит классу #Р, если соответствующая ей задача разрешимости принадлежит классу ЖР. Вэлиант [32] показал, что задача вычисления перманента (0,1)-матрпц является #Р-полной и,

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

Проблема 1.1.11. Какие целые числа из отрезка [0,п!] являются перманентами матриц из Ап? На каких матрицах эти значения достигаются?

Один из первых содержательных результатов в этом направлении был получен ещё в начале XX века Фробениусом [14] и Кёнигом [20], доказательство в современной терминологии см. в монографии [2] Минка.

Предложение 1.1.12. (Фробениус, 1917, Кёниг, 1936, [2, теорема 2.2]).

Перманент, матрицы А € Ап равен нулю если и толь ко если А содержит нулевую подматрицу размера г х в с г + в > п.

Аналогичные критерии были позже получены для значений 1, 2 и 3.

Теорема 1.1.13. (Гордон, Моцкин, Уэлч, 1974, [16, теорема 1 ]). Перманент матрицы А € Ап равен 1 тогда и только тог да, когда А равна, с точностью до перестановки строк, столбцов и транспонирования, следующей матрице:

1.

0 '1_

Теорема 1.1.14. (Гордон, Моцкин, Уэлч, 1974, [16, теорема 2]). Перманент матрицы А € Ап равен 2 тогда и только тог да, когда А равна, с точностью до

перестановки строк, столбцов и транспонирования, следующей матрице:

1 1 0 1

0 0 10

0 1

0

0 0

0

1

Аналогичный результат для значения 3 функции перманента [16, теорема 3 как и доказательства двух теорем выше, можно найти в работе [16] Гордона, Моц-кина и Уэлча.

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

Теорема 1.1.15. (Гордон, Моцкин, Уэлч, 1974, [16, теорема 5]). Пусть r(k) := min{n : ЗА £ An | per (A) = k}. Тогда r(k) < |_log2(k — 1)J + 2 для любого k > 2.

Т.е. для всякого числа k > 2 существует (0,1)-матрица порядка n < |log2(k — 1)J + 2 с перманентом k.

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

Теорема 1.1.16. (Бруальди, Ньюмен, 1965, [6, теорема 2.1 и следствие

2.2]). Для любого n £ N и любого целого неотрицательного j < 2n—1 существует такая матрица А £ An, что per (А) = j.

1

1

1

1

Введём следующее определение.

Определение 1.1.17. Пусть n € N. Число Bn назовём границей подряд идущих значений перманента матриц из An, если Bn — наименьшее натуральное число с тем свойством, что не существует такой матрицы A € An, что per (A) = Bn + 1.

Таким образом, теорема 1.1.16 даёт нижнюю оценку дляВп: Bn > 2n-1. В главе 1 мы улучшим эту оценку, показав, что, начиная с n = 6 Bn > Ц2n. Поскольку Ц > 1, то отсюда следует, что Bn > 2n. Также мы оцепим количество значений функции перманента в правой части отрезка [0,nl], подробнее см. в разделе 1.2.2.

1.1.2 Использование перманента (0,1)-матриц

Ниже приведены классические примеры использования функции перманента, которые можно найти, например, в главах 1 и 7 книги [7] Бруальди и Райзера.

п

причём у каждого учителя ровно один ученик, а у каждого ученика ровно один учитель, и требуется рассадить все п пар за круглым сто лом с 2п стульями так, чтобы никто не оказался рядом со своим напарником и любые два соседа имели разный статус (один - ученик, другой - учитель). Обозначим число всех таких рассадок через Мп. Любая такая рассадка однозначно определяется рассадкой учеников на места 1,3,..., 2п — 1 и последующей рассадкой учителей па оставшиеся места, с запретом сажать учителя справа или слева от его ученика. Следовательно, Мп = 2 • (п!) • ип, где ип есть количество разрешённых рассадок учителей, не зависящее от выбранной рассадки учеников. Пронумеруем отдельно учительские

п

стулья с номером % были соседними. Тогда при любой рассадке учеников множество разрешённых рассадок учителей определяется условием, что учитель не может сидеть па учительских стульях с номерами % и % + 1, если его ученик сидит на ученическом стуле с номером % (полагая п + 1 = 1). Таким образом, количество

разрешённых рассадок учителей равно перманенту per (Vn) следующей матрицы

/0 0 1 ... 1 1 1 \

10 0 1 ... 11

110 0 1 ... 1

vn =

1

1 0

1 1 1

1

0 1

0 0 1

1 0 0

/

и, следовательно, Mn = 2 • (n!) • per (Vn).

nn

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

(0, 1) А n

аj = 1 тогда и только тогда, когда соответствующая кандидату i вершина соединена ребром с соответствующей вакансии j вершиной. Тогда перманент per (А)

А

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

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

Определение 1.1.20. Пусть А - М-матрица размера m х n, где без ограничения общности m < n. Тогда

per(^= Yl per ^jV-jn-m

1 < jl <j2 <...<jn-m <n

где А^...^^ обозначает квадратную подматрицу, по лученную из А вычёркиванием столбцов j1, j2,... , jn—m.

1

Такое обобщение определения перманента приводит к следующему обобщению примера 1.1.19.

Пример 1.1.21. Пусть X = {1, 2,..., п}, а XI, ..., X™, - набор подмножеств X, не обязательно различных. Элемент a € X назовём представителем множества X,, если a € X,;. Системой различных представителей упорядоченного набора множеств ,..., X™) называется такой упорядоченный набор элементов ..., am), что ai € X, при всех % от 1 до ш и ai = aj при г = Построим матрицу инцидентности набора ^1^2,... , X™), т.е. такую (0,1)-матрицу А размера ш х п, что aij = 1 тогда и только тогда, когда] € X,. Тогда, согласно теореме 1.2.3 [7], количество систем различных представителей набора ..., X™) равно

А

1.2 Граница подряд идущих значений как функция размера матрицы

1.2.1 Оценка снизу

1.2.1.1 Похожие матрицы и свойства их перманента

Нижеследующая конструкция применима для построения матриц с заданным значением перманента.

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

Пример 1.2.2. Примеры пар похожих матриц:

1 0 1 1 0 1 111 и 0 10

1 1 1 1 1 1

(1 о о И 1110 iiii 1111

\

/

и

1111 10 11 110 1 110 1

\

/

Пример 1.2.3. Примеры пар непохожих матриц:

11 11

и

01 10

1001 1110 1111 1111

1 0 1 1 0 1

1 1 1 и 0 1 0

1 1 1 1 0 1

и

1111 1011 1110 1101

Лемма 1.2.4. Пусть матрицы A1,A2 G An похожи, и пусть per (A1) = x7 per (A2) = y. Тогда, существуют такие X,Y,Z G An+1? что per (X) = 2x, per (Y) = 2y per (Z) = x + y и матрица Z похожа и на X, и на Y.

Доказательство. Заметим, что перманент не меняется при перестановках линий и транспонировании.

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

/ ^ a \ / ^ a \

Ai =

«и

a in

«n— 1 1 ... an— 1

и

A2 =

a11

an 1 1

у an1 . . . ann У У an1

Рассмотрим следующие три матрицы из An+1: /0 an ... a1^ /0

a1n

an-1 n J

a

nn

/

X=

0 an

V

n- 1 n

an1

an1

a1n

an-1 n ann ann

/

Y=

V

0 1 1

a11

an-1 n J

a

a

n1 f

n1

a1n

an-1 n

nn f

nn

/

/ 0 «11 . . a1n

0 an—1n . . an—1n

1 an1 . . ann

V 1 an1 . a' nn

Z =

/

Видно, что по построению Z похожа как на X, так и на Y. Согласно формуле разложения перманента по столбцу, имеем per (X) = per (A) + per(Ai) = 2x, per (Y) = per (A2) + per (A2) = 2y, per (Z) = per (A1) + per (A2) = x + y. □

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

Следствие 1.2.5. Пусть (n,Z) £ N2, и для каждого целого x в промежутке 0 < x < Z — 1 существует такая пара похожих матриц Ax,Bx £ An, что per (Ax) = x, per (Bx) = x + 1. Тогда, для всякого целого z в промежутке 0 < z < 2Z — 1 существует пара таких похож их матриц Cz, Dz £ An+1? чт о per (Cz) = z, per (Dz) = z + 1.

Доказательство. Для всех таких x, что 0 < x < Z — 1, применим лемму 1.2.4 к матрицам Ax, Bx, и получим две пары похожих матриц (X, Z) и (Z, Y) £ A2n+1) где per (X) = 2x, per (Z) = 2x + 1 per (Y) = 2x + 2. Далее, для всякой пары (z, z + 1) последовательных целых чисел в промежутке [0, 2Z — 1] верно, что одно из этих чисел чётно. Если чётно z, то, взяв x = 2z, получим, что искомая пара — это X, Z £ An+1. Если же чётно z + 1, то, полагая x = 1 (z + 1), получаем, что искомой парой похожих матриц с перманентами z и z + 1 являются соответственно Z, Y £ An+1, и, таким образом, следствие 1.2.5 доказано. □

Следствие 1.2.6. Если, выполнены условия, предыдущего следствия, то для любого натурального k > 0 границ a Bn+k подряд идущих значении, перманента матриц из An+k превосходит 2kZ — 1.

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

Список литературы

(-1, 1) п

нентом. Дискретн. анализ и исслед. опер., 3(1):23 42, 1996.

[2] X. Минк. Перманенты. Мир, М., 1982.

[3] Д.К. Фаддеев, И.С. Соминский. Сборник задач по высшей алгебре. Наука, М., 1968.

[4] R.B. Bapat. Recent developments and open problems in the theory of permanents. Math. Student, 76(1^4):55-69, 2007.

[5] J.P.M. Binet. Mémoire sur un systeme de formules analytiques, et leur application a des considerations géométriques. J. École Polytechnique, 9:280-302, 1812.

[6] R.A. Brualdi, M. Newman. Some theorems on permanent. J. Res. Natl. Bur. Stand., 69B(3):159-163, 1965.

[7] R.A. Brualdi, H.J. Ryser. Combinatorial Matrix Theory. Cambridge Univ. Press, 1991.

[8] R.A. Brualdi, B.L. Shader. Matrices of Sign-Solvable Linear Systems. Cambridge Univ. Press, 1995.

[9] M.V. Budrevich, A.E. Guterman. Krâuter conjecture on permanents is true. J. Comb. Theory, Ser. A, 162:306-343, 2019.

[10] A.L. Cauchy. Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu'elles renferment. J. École Polytechnique, 10:91-169, 1815.

[11] G.-S. Cheon, I.M. Wanless. An update on Mine's survey of open problems involving permanents. Linear Algebra Appl. 403:314-342, 2005.

[12] S.A. Cook. The complexity of theorem proving procedures. Proc. 3rd Ann. ACM Symp. Theory of Computing, 151-158, 1971.

[13] N. Fine. Binomial coefficients modulo a prime. American Mathematical Monthly, 54:589-592, 1947.

[14] G. Frobenius. Uber zerlegbare Determinanten. Sitzungsber. Preuss. Akad. Wiss., 274-277, 1917.

[15] M.R. Garey, D.S. Johnson. Computers and intractability: a guide to the theory of NP-completness. W.H. Freeman, San Francisco, 1979.

[16] B. Gordon, T. S. Motzkin, L. Welch. Permanents of 0,1-Matrices. J. Combin. Theor. (AJ, 17:145-155, 1974.

[17] Ph. Hall. On Representatives of Subsets. J. London Math. Soc., 10(1):26-30, 1935.

[18] R.M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, 85-103, 1972.

[19] Y.-H. Kiem, S.-H. Kye, J. Na. Product vectors in the ranges of multi-partite states with positive partial transposes and permanents of matrices. Commun. Math. Phys., 338(2):621-639, 2015.

[20] D. König. Theorie der endlichen und unendlichen Graphen. Leipzig, 1936.

[21] A.R. Kräuter. Recent results on permanents of (1, —1)-matrices. Ber. Math. Statist. Sekt. Forsch. Graz, 249:1-25, 1985.

(1, —1)

matrices. Israel J. Math. 45, No. 1 (1983), 53-62.

[23] D.E. Littlewood. The Theory of Group Characters and Matrix Representation of Groups (2nd ed.). Oxford Univ. Press, 1950.

[24] D.E. Littlewood, A.R. Richardson. Group characters and algebras. Phil. Trans. R. Soc. Lond. A, 233:99-141, 1934.

[25] L. Loväsz, M.D. Plummer. Matching Theory. Elsevier, 1986.

[26] W. McCuaig. Pölya's permanent problem. Electron. J. Combin., 11:R79, 2004.

[27] T. Muir. On a class of permanent symmetric functions. Proc. Roy. Soc. Edinburgh, 11:409-418, 1882.

[28] H. Perfect. Positive diagonals of ±1-matrices. Monatsh. Math., 77:225-240, 1973.

[29] G. Polya. Aufgabe 424. Arch. Math. Phys., 20(3):271, 1913.

[30] H.J. Ryser. Combinatorial Mathematics. Math. Assoc. Amer., 1963.

[31] R. Simion, F.W. Schmidt. On (+1, —1)-matrices with vanishing permanent. Discrete Mathematics, 46:107-108, 1983.

[32] L.G. Valiant. The complexity of computing the permanent. Theoret. Comput. Sci., 8:189-201, 1979.

(1, —1)

1974.

[34] I.M. Wanless. Permanents of matrices of signed ones. Linear Multilinear Algebra, 53(6):427 433. 2005.

[35] T.-C. Wei, S. Severini. Matrix permanent and quantum entanglement of permutation invariant states. J. Math. Phys., 51(9), 2010.

[36] F. Zhang. An update on a few permanent conjectures. Spec. Matrices, 4:305-316, 2016.

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

[37] М.В. Будревич, А.Э. Гутерман, К.А. Таранин. О делимости парманента (±1)-матриц. Зап. научи, сем. ПОМИ, 439:26-37, 2015. М. V. Budrevich, А. Е. Guterman, К. A. Taranin. On the divisibility of permanents for (±1)-matrices. J. Math. Sc., 216(6):738-745, 2016. Scopus, RSCI. IF SJR 0.330 (2020).

[38] М.В. Будревич, А.Э. Гутерман, К.А. Таранин. К теореме Кройтера-Сейфтера о делимости перманентов. Зап. научн. сем. ПОМИ, 463:25-35, 2017.

М. V. Budrevich, А. Е. Guterman, К. A. Taranin. On the Krauter-Seifter theorem on permanent divisibility. J. Math. Sc., 232(6) :760-767, 2018. Scopus, RSCI. IF SJR 0.330 (2020).

[39] K.A. Таранин. О ±1-матрицах с нулевым перманентом. Зап. научн. сем. ПОМИ, 482:244-258, 2019.

К. A. Taranin. ±l-matrices with vanishing permanent. J. Math. Sc., 249(2):271-280, 2020.

Scopus, RSCI. IF SJR 0.330 (2020).

[40] A.E. Guterman, K.A. Taranin. On the values of the permanent of (0,1)-matrices. Linear Algebra Appl, 552:256-276, 2018.

Scopus, RSCI. IF SJR 0.330 (2020).