О конвертации перманента и определителя

• Автор: Будревич, Михаил Вячеславович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 122 с.

Оглавление
Введение

1 Знаковая конвертация матриц

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

1.1.1 Понятие конвертации перманента матрицы

1.1.2 Примеры использования функции перманента

1.2 Примеры конвертируемых и неконвертируемых матриц

1.3 Свойство конвертируемости и арифметические операции иа

матрицах

1.3.1 Конвертируемость суммы матриц

1.3.2 Максимальные конвертируемые матрицы и знаковая конвертируемость при матричном умножении
1.4 Кронекерово произведение матриц
1.4.1 Связь конвертируемости матрицы с теорией графов
1.4.2 Критерий конвертируемости кронекерова произведения неотрицательных матриц
2 Конвертируемые и неконвертируемые (ОД)-матрицы
2.1 Основные определения
2.2 Построение симметричных неконвертируемых (ОД) матриц

2.3 Нижняя граница конвертации для неразложимых и вполне
неразложимых матриц
2.3.1 Понятие неразложимой и вполне неразложимой матриц .
2.3.2 Операция свертки перманента матрицы и ее свойства . .
2.3.3 Нижняя граница конвертации
2.4 Описание неконвертируемых вполне неразложимых (0,1)-матриц с числом единиц на нижней границе конвертации
Матрицы над конечными полями
3.1 Введение
3.2 Конвертация матриц над конечным полем
3.2.1 Конвертация матриц над полем из 3 элементов
3.2.2 Построение примеров знаково конвертируемых матриц .
3.2.3 Достаточные условия знаковой конвертации матрицы
над конечным полем
3.3 Тензор перманента и его свойства
3.4 Биективная конвертация
3.4.1 Оценка числа матриц с нулевым перманентом
3.4.2 Отсутствие биективного отображения, конвертирующего перманент в определитель
Введение
Общая характеристика работы
Актуальность темы исследования
Перманент квадратной матрицы А = (aÿ) порядка та определяется следующим образом:

per (А) = ЕП
oESn г—
где Sn это группа перестановок порядка та.
Формула перманента матрицы отличается от определителя матрицы отсутствием умножения на знак перестановки, поэтому его иногда называют “определителем без знака”.
Впервые перманент, как класс симметрических функций, был независимо введен Коши [16] и Вине [10]. Термин “перманент” для квадратных матриц был введен Мюиром [34]. Кроме того, Мюир доказал базовые свойства перманента по аналогии с определителем, впервые исследуя эти понятия как родственные. В работах Литлвуда и Ричардсона 127, 28] понятия перманента и определителя были обобщены до имманаита, в котором слагаемые берутся с коэффициентом, равным значению фиксированного характера на соответствующей перестановке.
Полиа предложил другой подход, связывающий вычисление перманента и определителя матрицы [36]. Например, для матриц порядка та = 2 имеет место равенство:
ац <Х2 | / ац
= det
Ü21 0*22 J >

В неравенстве (1.7) рассмотрим только первые т строк матриц. Из определения матрицы игП'П получаем цепочку неравенств:
Ф{а) > Ф{а2) > ... > ф(ат) > ф{а1), (1.8)
здесь а,..., ат — первые т векторов строк матрицы А.
Получаем, что в (1.8) имеют место равенства.
Таким образом, первые т строк можно разбить на две подматрицы. Первая из этих подматриц А[ 1,..., тг1,... , Д] не содержит нулевых элементов. Вторая подматрица А[1,т|Д, ..., где {Д, ..., г*,} и {Д, ..., Д-д} = {1,... ,п} и {гь... ,Д} П {Д,... Бп-к} = 0, является нулевой.
В матрице существует обобщенная диагональ {а,ст(1), • ■ •, ап,ст(п)} из ненулевых элементов. В силу общего вида матрицы, подматрица Б = А[1,..., т|<т(1),..., ст(т) не содержит нулевых элементов. По следствию 1.3.6 подматрица Б конвертируема тогда и только тогда, когда конвертируема матрица ,7т = ф(Б). По теореме 2 матрица Jrn неконвертируема при т > 3. Таким образом, подматрица Б неконвертируема. Кроме того, в силу существования указанной обобщенной диагонали и неотрицательности матрицы А, имеет место неравенство
рег (Л(1,..., т|<т(1),.. ., а(т))) > 0.
Таким образом, если а — т} и /3 = {сг(1)5..., а(т)}, то по лемме
1.3.18 матрица А неконвертируема. Это противоречит условию леммы. Таким образом, сделанное предположение неверно и матрицаБЛ неконвертируемая.
Для доказательства леммы относительно произведения АВ достаточно заменить перестановку строк на перестановку столбцов. □
Следствие 1.3.21. Пусть А, В — неотрицательные матрицы, где А — максимальная конвертируемая матрица, и существуют матрицы перестановок