О конвертации перманента и определителя тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Будревич, Михаил Вячеславович АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Москва МЕСТО ЗАЩИТЫ
2014 ГОД ЗАЩИТЫ
   
01.01.06 КОД ВАК РФ
Автореферат по математике на тему «О конвертации перманента и определителя»
 
Автореферат диссертации на тему "О конвертации перманента и определителя"

ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова»

На правах рукописи

Будревич Михаил Вячеславович

О КОНВЕРТАЦИИ ПЕРМАНЕНТА И ОПРЕДЕЛИТЕЛЯ

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

г О НОЯ 2014

Москва — 2014

005555523

Работа выполнена на кафедре высшей алгебры Механико-математического факультета ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова».

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Гутерман Александр Эмилевич,

доктор физико-математических наук, профессор.

Кожухов Игорь Борисович,

доктор физико-математических наук, профессор (ФГАОУ ВПО Национальный исследовательский университет «МИЭТ», кафедра высшей математики №1); Богданов Илья Игоревич, кандидат физико-математических наук, доцент (ФГАОУ ВПО Московский физико-технический институт (государственный университет), кафедра высшей математики).

ФГБОУ ВПО Московский педагогический государственный университет.

Защита диссертации состоится 05 декабря 2014 г. в 16 ч. 45 м. на заседании диссертационного совета Д 501.001.84, созданного на базе ФГБОУ ВПО «Московский государственный университет имени М.В.Ломоносова», по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, ФГБОУ ВПО МГУ имени М.В.Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВПО МГУ имени М.В.Ломоносова по адресу: Москва, Ломоносовский проспект, д.27, сектор А.

Автореферат разослан 05 ноября 2014 г.

Ученый секретарь диссертационного совета Д 501.001.84, созданного на базе ФГБОУ ВПО МГУ имени М.В.Ломоносова, доктор физико-математических наук,

профессор Иванов Александр Олегович

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

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

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

Впервые перманент, как класс симметрических функций, был независимо введен Коши1 и Бине2. Термин "перманент" для квадратных патриц был введен Мюиром3. Кроме того, Мюир доказал базовые свойства перманента по аналогии с определителем, впервые исследуя эти понятия как родственные. В работах Литлвуда4 и Литлвуда, Ричардсона5 понятия перманента и определителя были обобщены до иммананта, в котором слагаемые берутся с коэффициентом, равным значению фиксированного характера на соответствующей перестановке.

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

Конвертируемость наиболее хорошо изучена для (ОД)-матрнц. В работах Сеге7, Гибсона8 получены примеры конвертируемых и неконвертируемых матриц и доказаны некоторые условия, запрещающие конвертацию. Кроме того, в работах целого ряда авторов9 10 11 матричными методами получены некоторые достаточные условия конвертируемости (ОД)-матриц.

M. L. Caur.hy. Mémorire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes conraires par suite des transpositions opérées entre, les variables qu'elles renferment. // Л. de l'Éc. Polyt., 10:29-119, 1812.

ï.J.P.M. Binet. Mémoire sur un système de formules analytiques, et. leur application .1 des considérations géométriques. // ,1. de l'Éc. Polyt., 10:29-119, 1812.

-1 T. Muir. On a class of symmetric permanent functions. // Proc. Roy. Soc. Edirburg, 11:409418, 1882.

*D.E. Littlewood. The Theory of Group Characters and Matrix Representations of Groups

(2nd ed.). // Oxford Univ. Press, 1950.

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

6G. Pölya. Aufgabe 424. // Arch. Math. Phys., 20(3):271, 1913.

nG. Szegö. Lösungzu. // Arch. Math. Phys., 21:291-292, 1913.

8P. M. Gibson. Conversion of the Permanent into the Determinant. // Proc.Amer.Math.Soc., 27:471-476, 1976.

9B.E. Тараканов, P.A. Заторский. О связи детерминантов с перманентами. // Мат. заметки, 85(2):292-299, 2009.

,0Л. Гутерман, Г. Долинар, Б. Кульма. Барьеры Гибсона для проблемы Полна. // Фундамент. и прикл. матем., 16(8):73-76, 2010.

" А. Гутерман, Г. Долинар, Б. Кузьма. Проблема Полиа о конвертируемости для симметрических матриц. // Мат. заметки, 92(5):684-698, 2012. \ \

Знаковой схемой матрицы А называется матрица sign(A), в которой все элементы заменены на их знак. Матрица А называется знаково невырожденной, если любая матрица с аналогичной знаковой схемой обратима. Бруалди и Шейдер12 доказали, что вопрос о конвертации (ОД)-матрицы А эквивалентен вопросу о существовании знаково невырожденной матрицы с тем же расположением ненулевых элементов. В частности, из этого следует, что неотрицательная матрица А конвертируема тогда и только тогда, когда конвертируема матрица А', полученная из А заменой всех ненулевых элементов на единичные. Знаковая невырожденность связана с понятием знаковой разрешимости систем линейных уравнений, которое применимо в задачах статистики и прогнозирования13.

По (ОД)-матрице А построим двудольный граф G = {U,V) такой, что ребро (Ui,Vj) принадлежит G тогда и только тогда, когда ay = 1. Литтл14 установил, что проблема Полиа о конвертации (ОД)-матрицы А алгоритмически эквивалента задаче о существовании пфаффианновой ориентации двудольного графа G-

Вазирани и Янакакис15 доказали, что проблема Полиа для (ОД)-матриц эквивалентна задаче поиска цикла четной длины в ориентированном графе и задаче о проверке равенства per {А) = det (А) для неотрицательных матриц. Развитие теории графов привело к построению полиномиальных алгоритмов для проверки существования пфаффианновой ориентации16 17 двудольного графа G, и, как следствие, проверки конвертируемости (0, 1)-матриц.

Важную роль перманент играет и в теории сложности, так как реализует число решений многих комбинаторных задач. Одним из минимальных по сложности (из известных) является алгоритм вычисления перманента, предложенный Райзером18. Алгоритм Райзера имеет экспоненциальную сложность. Более того, классическим является результат Валианта19, который показал, что вычисление перманента (ОД)-матрицы лежит в классе #-Р сложных задач20.

12R. A. Brualdi, В. L. Shader. On Sing-Nonsigular Matrices and the Conversion of the Permanent into the Determinant. // DIMACS Ser. in Discrete Math, and Theoret. Comput. Sci., 4:117-134, 1991.

"R- A. Brualdi, B. L. Shader. Matrices of sing-solvable linear systems. // Cambridge Univ. Press, 1995.

UC. H. C. Little. A characterization of convertible (0; l)-raatrices. // J. Combin. Theorv Ser. B, 18:187-208, 1975.

15 V. V. Vazirani and M. Yannakakis. Pfaffian orientations, 0-1 permanent,s, and even cycles in directed graphs. // Discrete Appl. Math., 25:179-190, 1989.

!6Ж McCuaig. Polya's permanent problem. // Elec. J. of Comb., 11:1-83, 2004.

,7JV. Robertson, P. D. Seymour, R. Thomas. Permanents, Pfaffian orientations, and even derected circuits. // Anals of Mathematics, 150:925-975, 1999.

nX. Мин к. Перманенты. // Мир, М., 1982. (глава 7, пункт 2)

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

5nL. Lovasz, M. D. Plummer. Matching Theory. // Elsevier, Amsterdam, 1986.

Цель работы

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

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

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

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

• Решен ряд проблем конвертируемости перманента (ОД)-матриц с некоторыми специальными условиями. В том числе:

- Решена проблема о существовании конвертируемых и неконвертируемых (ОД)-матриц с числом единиц между границами конвертации.

- Найдено минимальное количество единиц во вполне неразложимой неконвертируемой (ОД)-матрице.

• Доказано достаточное условие знаковой конвертируемости матрицы над конечным полем.

• Исследован вопрос о биективной конвертации для матриц над конечным полем, в том числе получены следующие результаты:

- Введен и исследован тензор перманента и его свойства.

- Доказано, что матриц над конечным полем F с char (F) > 2 порядка п > 3 с нулевым определителем больше, чем матриц с нулевым перманентом.

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

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

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

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

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

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

Апробация результатов

Результаты диссертации неоднократно докладывались на научно-исследовательских семинарах: научно-исследовательские семинары по алгебре кафедры Высшей алгебры МГУ, "Кольца и модули", "Теория матриц", семинары кафедр Математической теории интеллектуальных систем и Дифференциальной геометрии и приложений в 2011-2014 годах.

Так же результаты докладывались на следующих всероссийских и международных конференциях:

• XIX международной конференции студентов, аспирантов и молодых ученых "Ломоносов-2012", Москва, 2012.

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

• 7ой симпозиум по линейной алгебре, Любляна, Словения, 4-12 июня 2014.

• 10ая международная конференция по конечным полям и их приложениям, Гент, Бельгия, 11-15 июля 2011.

Публикации

Результаты автора по теме диссертации опубликованы в семи работах, список которых приводится в конце автореферата [1-7].

Структура диссертации

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

Краткое содержание работы

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

4 I

Глава 1 посвящена изучению вопроса сохранения свойства конвертируемости матриц при выполнении различных операций над ними. Под конвертируемостью понимается:

Определение. Квадратная матрица А 6 Мп порядка п называется конвертируемой, если существует матрица X 6 М„(± 1) такая, что выполнено равенство рег (Л) = с1е! (ЛоХ).

Операция "о" означает поэлементное умножение матриц.

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

Теорема (1.3.12) Пусть А,В — вещественные неотрицательные квадратные матрицы с положительным, перманентом. Тогда матрица [А + В) конвертируема в том и только в том случае, когда существует конвертируемая матрица С € Мп(0,1) такая, что ф{А) < С и ф(В) < С.

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

Следствие (1.3.22) Пусть А, В — неотрицательные м,ат,рицы, где А — максимальная конвертируемая матрица, и существуют матрицы перестановок Р, такие, что ф(В) > Р(ит<п + 1п)Я, т > 3. Тогда матрицы В А и АВ — неконвертируемые.

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

/

1, если 2< .7=1 + 1 < т 1, если г = т, э = 1 О, иначе.

В разделе 1.4 изучается кронекерово произведение неотрицательных матриц. Кронекеровым произведением матриц А = (ау) и В = (Ьу) называется блочная матрица

(апВ ... а1пВ^ ........

ап\В ... аппВ)

Доказано необходимое и достаточное условие конвертируемости кронекеро-вого произведения.

Теорема (1.4.17) Пусть А е Мп(0,1) и В е Мт(0,1), и перманент матриц А и В отличен от нуля. Тогда кронекерово произведение А ® В

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

В главе 2 изучается вопрос построения конвертируемых и неконвертируемых (ОД)-матриц при различных ограничениях.

Через SMn С М„ будем обозначать подмножество симметричных матриц.

Определение (2.1.8) Матрица Л € SMn(0,1) называется симметрично конвертируемой, если существует матрица X е SMn(± 1) такая, что per (Л) = det (А о X). Матрица А £ SMn(0,1) называется слабо симметрично конвертируемой, если существует симметричная матрица^ € SMn(±l) такая, что per (Л) = ±det (Л о X).

Каждой матрице Л 6 М„(0,1) сопоставим пару чисел (п, г), где первое число — порядок матриц, а второе — количество единиц в матрице. Число Пп, называемое верхней границей конвертации, равно такому максимальному количеству единиц в (0,1)-матрице с положительным перманентом, при котором она может быть конвертируемой. Числом,,, называемое нижней границей конвертации, равно такому минимальному количеству единиц в (0,1)-матрице. при котором матрице может быть неконвертируемой.

В разделе 2.2 изучался вопрос о существовании слабо симметрично неконвертируемых (ОД)-матриц порядка п > 3 для различных значений параметра г G [ып,0,], равного числу единиц в матрице.

Теорема (2.2.4) Для любого п > 3 и для любого г £ [ш„, П„] существует слабо симметрично неконвертируемая симметричная (0,1)-матрица т,ипа (п,г).

В разделе 2.3 исследован вопрос о числе ненулевых элементов (0,1)-матрицы," при котором вполне неразложимая матрица всегда конвертируема.

Матрица Л называется частично разложимой, если существуют матрицы перестановок Р, Q такие, что PAQ — блочная верхнетреугольная матрица. В противном случае будем говорить, что матрица Л вполне неразложима. Если существует матрица перестановок Р, такая, что Р1АР — блочная верхнетреугольная матрица, то матрица называется разложимой, и неразложимой, если такой Р не существует.

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

Определение (2.3.12) Пусть в первой строке неотрицательной матрицы только два ненулевых элемента an,<Zi2- Сверткой матрицы Л по первой строке назовем неотрицательную матрицу 6 (Л) следующего вида:

/ аца22 + £112021 Я23

6(Л) = alla32 + ^12^31 «33 а3п

\aiian2 + ai2flni апз &пп J

6

Определение свертки очевидно обобщается на произвольную строку с двумя ненулевыми элементами. Доказаны следующие свойства операции свертки:

Лемма (2.3.14) Пусть А е Мп(Е+) и существует ее свертка, по первой строке, равная матрице<5(А). Если матрица <5(А) конвертируема, то конвертируема и матрица А.

Лемма (2.3.15) Пусть А € Мп(Ж+) и существует ее свертка по первой строке, равная матрице <5(Л). Тогда, если матрица А конвертируема, то конвертируема и матрица 6(А).

Для А Е Мп(0,1) через и(А) обозначим число единиц в матрице А. Основным результатом раздела 2.3 является теорема:

Теорема (2.3.26) Пусть А е Мп(0,1) и А — вполне неразложимая матрица. Если у{А) < 2тг + 3, то матрица А конвертируема.

Также рассмотрен вопрос конвертируемости неразложимых матриц. Построен пример (2.3.28), показывающий, что последняя теорема не обобщается на неразложимые матрицы.

В разделе 2.4 рассмотрена операция расширения матрицы.

Определение (2.4.5) Расширением (ОД)-матрицы А по ¿-тому столбцу будем называть множество матриц £И(А) такое, что для каждой В е имеем В е Мп+1(0,1), Ьм = Ьи+1 = 1 и 6(В) = А.

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

Лемма (2.4.7) Пусть У — множество вполне неразложимых неконвертируемых (0,1)-матриц порядка п с (2п + 3) ненулевыми элементами. Тогда любая вполне неразложимая неконвертируемая матрица А порядка (п 4-1) с 2(п + 1) + 3 элементами перестановочно эквивалентна одной из матриц из множества игде в объединении берутся расширения по всем столбцам матриц В.

Последняя лемма позволяет описать все вполне неразложимые неконвертируемые (ОД)-матрицы с (2п + 3) ненулевыми элементами. Через Пп обозначим матрицу порядка п, определенную по правилу:

¡1, если 1 + ] = п или г + j = п+ I 0, иначе.

Определение (2.4.10) Будем говорить, что выполнена операция расширения (ОД)-матрицы А с выбором, если выбрана одна из матриц из множества т(А).

Лемма (2.4.11) Пусть дана матрица размера 3 на 1 (вектор-столбец размера 3), заполненная единицами. К этой матрице к раз применили операцию расширения с выбором, и получили матрицу В размера (к+3) х (/с+1). Пусть после каждого шага в каждом столбце полученной матрицы, не .менее 2 ненулевых элементов. Тогда существуют целые неотрицательные числа к\, /сг и кз, где к\ + + = к, и матрицы перестановок Р, <2 строк и столбцов матрицы В такие, что матрица РВС} имеет следующий вид:

Окг,к3 Окик2

Ок2,к3 Як2 УГз

\

ОкъМ

Ок3М Щ )

Ск

т

(1)

где:

1. Ук( — вектор столбец из к{ элементов с единственным единичным элементом, стоящим на последнем месте, если к^ > 0, и пустой вектор, если А;; — О.

2. \Уо — вектор столбец из трех элементов.

3. В первом столбце матрицы (1) три ненулевых элемента.

4. Каждая из подматриц И^, где г = 1,2,3, имеет размеры 3 х ^ и при к^> О имеет единственный ненулевой элемент, который находится в 1-той строке в последнем столбце.

5. В каждой строке подматрицы. И^ = (И^о Ц^ И^) содержится единственный единичный элемент.

В выражение (1) матрица разбита на блоки И4 и С*, где к означает число проделанных операций расширения с выбором, И^ включает в себя три последние строки полученной матрицы, а Ск включает все строки, кроме 3 последних. Данные блоки лежат в основе описания вполне неразложимые неконвертируемые (ОД)-матрицы с (2п + 3) ненулевыми элементами.

Теорема (2.4.13) Пусть п > 3. Для любой вполне неразложимой неконвертируемой матрицы А е Мп(0,1) с и(А) = 2п + 3 существуют неотрицательные целые числа 7711,7712,7713 такие, что т\ + тог + тз + 3 = пи матрица А с точностью до перестановки строк и столбцов имеет, вид:

( С, О,

Ш\

11X2,т 1 + 1 ^ГП2

Отз,гт+1 От3,т2+1

От1,т2+1 Фги.тпз+А Стч От2,тз+1

с„

\ щ

7П\

Ж

(2)

т2

Жлз У

где С,щ и IV1щ — блоки матрицы Т, которая задана формулой (1), а 0{ * нулевая подматрица порядка г х у.

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

В разделе 3.2 изучается аналог конвертации для матриц над конечным полем. В случае поля F, конечной характеристики понятие конвертации является содержательным при char (F?) > 3. Для минимально возможного поля F3 из 3 элементов доказано, что любая матрица А € Мп{¥з) всегда конвертируема.

Теорема (3.2.11) Пусть А е Мп(F3). Тогда существует X е М„(± 1) такая, что per (А) = det [А о X).

Доказано, что поле F3 является единственным исключением. А именно, для любого другого конечного поля Fg, где char (F9) > 3, существуют примеры неконвертируемых матриц.

Теорема (3.2.14) Для всякого поля ¥q, такого, что char (Fg) > 3 и |Fg| > 5, и для любого п > 3 существует неконвертируемая матрица А е Mn(¥q).

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

Теорема (3.2.24) Пусть ¥q — поле характеристики р > 3. Тогда для любого п > (р — 1) существует конвертируемая матрица с ненулевым перманентом,, которая не содержит нулевых элементов.

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

Теорема (3.2.29) Пусть матрица А е Мп(¥р), р>2ип>2р-6, удовлетворяет следующим условиям:

1. Один из столбцов не содержит нулевых элементов.

2. Б одной из строк не менее

М = (р - 3) log(n - 1 )(р - 1) + 2

ненулевых элементов.

3. Матрица А вполне неразложима.

Тогда матрица А конверт,ируем,а.

В разделе 3.3 введено понятие тензора перманента, доказаны его основные свойства.

Определение (3.3.1) Пусть ej,... ,е„ — стандартный базис линейного пространства Vn = F™. Пусть А € Мкхп(¥я), где к < п. Рассмотрим (п - к)-мерный контравариантный тензор ТА = Тд'""1п~к заданный на пространстве = Vn ® ■ • • <8> Vv Зададим компоненты тензора в базисе ei,..., е„ по

п-к раз

правилу:

rpiu-,in-k _ | Per • • • 1 Ч-к)), если все гь ..., ¿n_fc различны

Л 1 0 в противном случае.

Тензор Та будем называть тензором перманента матрицы Л. В случае, если к = 1, матрица может быть рассмотрена как вектор Л 6 Mi,n(Fg) = F£, и мы будем называть Та тензором вектора А.

Определение (3.3.4) Пусть а = (ai,..., ап) € — вектор с п компонентами. Пусть А € Mk,n(^q), Та обозначает тензор перманента матрицы А. Сверткой тензора Та и вектора а называется тензор Т = Та о а, компоненты которого заданы по следующему правилу:

п

Tib""<n"fc"1 = T<b~A-*-,J ■ Qj.

j=1

Одним из ключевых свойств тензора перманента является следующая теорема.

Теорема (3i.3.6) Пусть матрица А 6 Мп(¥д) представлена как набор строк ai,... ,ап. Тогда для перманента матрицы А справедлива формула:

per (Л) = (...(Т0п о an_i) о ап-2. -.) о щ.

Разработанная техника в разделе 3.4 использована для получения оценки числа матриц с нулевым перманентом в пространстве матриц над конечным полем.

Теорема (3.4.10) Пуст.ь F5 — конечное поле из q элементов, характеристика которого больше 2. Тогда имеет мест,о неравенство:

D(Mn(F,)) > Р(Мп(F,)).

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

Теорема (3.4.12) Пусть Fg — конечное поле из q элементов, char (Fg) = р > 3, Mn(¥q) — кольцо квадратных матриц, гдеп > 3. Тогда не. существует биективного отображения,

О : Mn(Fq) ->• Mn(Fq),

такого, что per (Л) = det (G(A)).

В частности, из этого следует, что даже в случае поля F3 универсальной матрицы X € Мп(± 1), которая бы конвертировала любую матрицу Л 6 Мп(¥3) не существует.

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

ю

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

Работы автора по теме диссертации

[1] М.В. Будревич. Арифметические матричные операции, сохраняющие конвертацию. Записки научн. сем. ПОМИ, 419:26-42, 2013.

[2] М.В. Будревич. Построение неконвертируемых матриц. Мат. заметки, 96(2):186-193, 2014.

[3] M. Budrevich, A. Guterman. Permanent has less zeros than determinant over finite fields. Contemporary Mathematics; Amer. Math. Soc., 579:33-42, 2012. А.Э. Гутерману принадлежат формулировки теорем, 2.16, 2.17 и утверждения 2.5 - 2.10. М.В. Будревичу принадлежат доказательства т,ео-рем 2.Ц, 2.16, 2.17 и утверждений 2.11 и 2.12.

[4] M.V. Budrevich, А.Е. Guterman. On the Gibson bounds over finite fields. Serdica Math.. 38:395-416, 2012. М.В. Будревичу принадлежат главы 1 и 3, А.Э. Гутерману принадлежат главы. 2 и 4-

[5] М.В. Будревич. О проблеме Полиа конвертации перманента в определитель для пространства матриц над конечным полем. Конференция "Ломоносов-2012". Тезисы докладов., Москва, 2012, электронное издание (http://lomonosov-msu.ru/archive/Lomonosov_2012/1795/43726_fe99.pdf).

[6] М.В. Будревич. Достаточное условие знаковой конвертируемости матрицы над конечным полем. Конференция "Ломоносов-20Ц". Тезисы докладов., Москва, 2014, электронное издание (http://lomonosov-msu.ru/uploaded/2200/2200_43726_5166b6.pdf).

[7] M. Budrevich. Matrix convertibility over finite field. 7th Linear Algebra Workshop, Ljubljana, Slovenia, 2014, электронное издание (http://www.law05.si/lawl4/abstracts/Budrevich.pdf).

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡до экз. Заказ №