Содержание к диссертации
Введение
1 Знаковая конвертация матриц 20
1.1 Основные определения и обозначения 20
1.1.1 Понятие конвертации перманента матрицы 20
1.1.2 Примеры использования функции перманента 22
1.2 Примеры конвертируемых и неконвертируемых матриц 24
1.3 Свойство конвертируемости и арифметические операции на матрицах 27
1.3.1 Конвертируемость суммы матриц 27
1.3.2 Максимальные конвертируемые матрицы и знаковая конвертируемость при матричном умножении 31
1.4 Кронекерово произведение матриц 38
1.4.1 Связь конвертируемости матрицы с теорией графов . 38
1.4.2 Критерий конвертируемости кронекерова произведения неотрицательных матриц 40
2 Конвертируемые и неконвертируемые (0,1)-матрицы 48
2.1 Основные определения 48
2.2 Построение симметричных неконвертируемых (0,1) матриц . 51
2.3 Нижняя граница конвертации для неразложимых и вполне неразложимых матриц 54
2.3.1 Понятие неразложимой и вполне неразложимой матриц . 54
2.3.2 Операция свертки перманента матрицы и ее свойства . 56
2.3.3 Нижняя граница конвертации 62
2.4 Описание неконвертируемых вполне неразложимых (0,1)-
матриц с числом единиц на нижней границе конвертации . 64
3 Матрицы над конечными полями 77
3.1 Введение 77
3.2 Конвертация матриц над конечным полем 78
3.2.1 Конвертация матриц над полем из 3 элементов 80
3.2.2 Построение примеров знаково конвертируемых матриц 88
3.2.3 Достаточные условия знаковой конвертации матрицы над конечным полем 97
3.3 Тензор перманента и его свойства 105
3.4 Биективная конвертация 109
3.4.1 Оценка числа матриц с нулевым перманентом 109
3.4.2 Отсутствие биективного отображения, конвертирующего перманент в определитель 116
- Примеры использования функции перманента
- Максимальные конвертируемые матрицы и знаковая конвертируемость при матричном умножении
- Нижняя граница конвертации для неразложимых и вполне неразложимых матриц
- Построение примеров знаково конвертируемых матриц
Примеры использования функции перманента
Теорема (1.4.17) Пусть А Є Мп(0,1) и В Є Мто(0,1), и перманент матриц А и В отличен от нуля. Тогда кронекерово произведение А (g)В конвертируемо в том и только в том случае, когда одна из матриц содержит единственную обобщенную диагональ без нулевых элементов, а вторая матрица конвертируема.
В главе 2 изучается вопрос построения конвертируемых и неконвертируемых (ОД)-матриц при различных ограничениях. Через SMn С Мп будем обозначать подмножество симметричных матриц. Определение (2.1.8) Матрица А Є SMn(0,1) называется симметрично конвертируемой, если существует матрица X Є 5 МП(=Ы) такая, что per (А) = det (А о X). Матрица А Є SMn(0,1) называется слабо симметрично конвертируемой, если существует симметричная матрица X Є SMn(±l) такая, что per (А) = ±det (А о X).
Каждой матрице А Є Мп(0,1) сопоставим пару чисел (п,г), где первое число — порядок матриц, а второе — количество единиц в матрице. Число Г2П, называемое верхней границей конвертации, равно такому максимальному количеству единиц в (ОД)-матрице с положительным перманентом, при котором она может быть конвертируемой. Число ujn, называемое нижней границей конвертации, равно такому минимальному количеству единиц в (0,1)-матрице, при котором матрице может быть неконвертируемой. В разделе 2.2 изучался вопрос о существовании слабо симметрично неконвертируемых (ОД)-матриц порядка п 3 для различных значений параметра г Є [ х п,Г2п], равного числу единиц в матрице.
Теорема (2.2.4) Для любого п 3 и для любого г Є [a;n,f2n] существует слабо симметрично неконвертируемая симметричная (ОД)-матрица типа (п,г).
В разделе 2.3 исследован вопрос о числе ненулевых элементов (0,1)-матрицы, при котором вполне неразложимая матрица всегда конвертируема.
Матрица А называется частично разложимой, если существуют матрицы перестановок Р, Q такие, что PAQ — блочная верхнетреугольная матрица. В противном случае будем говорить, что матрица А вполне неразложима. Если существует матрица перестановок Р, такая, что РгАР — блочная верхнетреугольная матрица, то матрица называется разложимой, и неразложимой, если такой Р не существует.
Для доказательства основного результата этого раздела введено понятие свертки матрицы, которое в некоторых случаях позволяет перейти к исследованию проблемы Полна для матриц меньшего порядка:
Определение (2.3.12) Пусть в первой строке неотрицательной матрицы только два ненулевых элемента 2ц, а\2- Сверткой матрицы А по первой строке назовем неотрицательную матрицу &(А) следующего вида: Определение свертки очевидно обобщается на произвольную строку с двумя ненулевыми элементами. Доказаны следующие свойства операции сверт ки: Лемма (2.3.14) Пусть А Є Мп(Ш+) и существует ее свертка по первой строке, равная матрице &(А). Если матрица &(А) конвертируема, то конвертируема и матрица А. Лемма (2.3.15) Пусть А Є Мп(Ш+) и существует ее свертка по первой строке, равная матрице &(А). Тогда, если матрица А конвертируема, то конвертируема и матрица &(А). Для А Є Мп(0,1) через ь {А) обозначим число единиц в матрице А. Основным результатом раздела 2.3 является теорема: Теорема (2.3.26) Пусть А Є Мп(0,1) и А — вполне неразложимая матрица. Если v(A) 2п + 3, то матрица А конвертируема.
Также рассмотрен вопрос конвертируемости неразложимых матриц. Построен пример (2.3.28), показывающий, что последняя теорема не обобщается на неразложимые матрицы. В разделе 2.4 рассмотрена операция расширения матрицы. Определение (2.4.5) Расширением (ОД)-матрицы А по і-тому столбцу будем называть множество матриц 91( 4) такое, что для каждой В Є 91( 4) имеем В Є Mn+i(0,1), Ъ\;ь = &ііг+і = 1 и 6(B) = А.
Операция расширения является удобным инструментом для описания вполне неразложимых неконвертируемых (ОД)-матриц порядка п с 2п + 3 единицами. В частности, имеет место следующее полезное свойство, которое говорит о том, что любую вполне неразложимую неконвертируемую (0,1)-матрицу порядка п с 2п + 3 единицами можно построить как последовательность расширений.
Лемма (2.4.7) Пусть Y — множество вполне неразложимых неконвертируемых (0,1)-матриц порядка п с (2п + 3) ненулевыми элементами. Тогда любая вполне неразложимая неконвертируемая матрица Л порядка (п + 1) с 2(п + 1)+3 элементами перестановочно эквивалентна одной из матриц из множества ивеуУ (В), где в объединении берутся расширения по всем столбцам матриц В.
Последняя лемма позволяет описать все вполне неразложимые неконвертируемые (ОД)-матрицы с (2п + 3) ненулевыми элементами. Через Rn обозначим матрицу порядка п, определенную по правилу: Определение (2.4.10) Будем говорить, что выполнена операция расширения (ОД)-матрицы А с выбором, если выбрана одна из матриц из множества ПА).
Лемма (2.4.11) Пусть дана матрица размера 3 на 1 (вектор-столбец размера 3), заполненная единицами. К этой матрице ; раз применили операцию расширения с выбором, и получили матрицу В размера (к + 3) х (к + 1). Пусть после каждого шага в каждом столбце полученной матрицы не менее 2 ненулевых элементов. Тогда существуют целые неотрицательные числа к\, hi и &з, где к\ + hi + kz = к, и матрицы перестановок Р,
Максимальные конвертируемые матрицы и знаковая конвертируемость при матричном умножении
Обозначение 1.3.1. Пусть А — неотрицательная матрица. Через ф(А) обозначим матрицу, полученную из А заменой всех ненулевых элементов на единицы.
Определение 1.3.2. Пусть А Є Мп(Ж) — вещественная матрица. Знаковой схемой матрицы А называется матрица sign(А) полученная заменой всех положительных элементов на 1 и всех отрицательных элементов на —1.
Определение 1.3.3. Матрица А Є Мп(0, ±1) называется знаково невырожденной, если любая вещественная матрица с такой же знаковой схемой невырождена.
Теорема 1.3.4 (Бруалди, Шейдер, [14]). Невырожденная вещественная матрица А знаково невырождена тогда и только тогда, когда все диагональные произведения матрицы А, умноженные на знак соответствующей перестановки, неотрицательны (неположительны), и существует как минимум одно ненулевое диагональное произведение.
Для вещественной матрицы А = (dij) через \А\ обозначим матрицу вида (К"1) Теорема 1.3.5 (Бруалди, Шейдер, [14]). Пусть А Є Мп(Ж). Тогда матрица Л знаково невырождена в том и только в том случае, когда per (\А\) = det (А)\.
Следствие 1.3.6. Неотрицательная матрица А конвертируема тогда и только тогда, когда конвертируема матрица ф(А). ДОКАЗАТЕЛЬСТВО. ЕСЛИ per (А) = О, то все диагональные произведения в А равны нулю и per (А) = 0 = det (А). Это свойство очевидно сохраняется при замене положительных элементов матрицы А на единицы. Следовательно per (ф(А)) = 0 = det (ф(А)).
Пусть per (А) 0. Если неотрицательная матрица А конвертируема, то существует матрица X Є МП(=Ы) такая, что имеет место равенство per (А) = det (А о X) 0. Очевидно, что \А о Х\ = А. Получаем равенство per (\А о Х\) = det (А о Х)\. По теореме 1.3.5 матрица А о X знаково невырождена. Так как det (А о X) 0, то по теореме 1.3.4 все диагональные произведения матрицы А о X, умноженные на знак перестановки, неотрицательны. Таким образом, в перманент А и определитель АоХ входят одни и те же диагональные произведения с одинаковыми знаками. Очевидно, что это свойство сохраняется при замене положительных элементов в Л на другие положительные элементы, что доказывает нашу лемму. per (А) = 0, то в матрице А нет ненулевых диагональных произведений. При умножении А о В в матрице не появиться новых ненулевых элементов, а значит все диагональные произведения для матрицы А о В будут нулевыми. Получаем равенство per (А о В) = 0 = det {АоВоХ).
Пусть per (А) 0. Так как матрица А конвертируется матрицей X, то по теореме 1.3.5 матрица А о X знаково невырождена. Так как det (А о X) = per (А) = 0, то по теореме 1.3.4 все диагональные произведения матрицы АоХ, умноженные на знак перестановки, неотрицательны. Так как — неотрицательная матрица, то все диагональные произведения матрицы А оХоВ, умноженные на знак перестановки, неотрицательны. В силу неотрицательности матрицы А о В получаем равенство per (А о В) = det (Ао В о X). Таким образом, матрица А о В конвертируема с помощью матрицы X. Следствие доказано.
Следствие 1.3.8. Пусть А — неотрицательная матрица. Тогда для любой X Є МП(=Ы) имеет место неравенство per (А) det (АоХ)\. Равенство возможно только для конвертируемой матрицы А.
При вычислении перманента неотрицательной матрицы все диагональные произведения неотрицательны. При вычислении определителя матрицы А о X диагональные произведения, умноженные на знак перестановки, имеют тот же модуль, что и для перманента матрицы А, но могут иметь разные знаки. Таким образом, получили требуемое неравенство.
Неравенство per (А) det (А о Х)\ обращается в равенство только в том случае, если при вычислении определителя матрицы АоХ диагональные произведения, умноженные на знак соответствующей перестановки, имеют один знак. Раскроем модуль. Если per (А) = det (А о X), то матрица А конвертируема. Пусть per (А) = —det (А о X). Возьмем матрицу X , которая отличается от матрицы X умножением первой строки на минус один. Получаем равенство per (А) = det (А о X ). Следовательно, матрица А конвертируема. Следствие доказано.
Пусть А — неотрицательная блочная верхнетреугольная матрица с диагональными блоками А\,... ,Аь и per (А) 0. Тогда имеют место следующие утверждения:
В силу формулы Лапласа для перманента имеет место равенство: per (А) = per (Ai)per (А2)... per (Ak). Если каждая из подматриц А{ конвертируется с помощью матрицы Xj, то выберем матрицу X Є МП(=Ы), где блоки Х{ стоят на главной диагонали. Получаем равенства:
Матрицы Л, В конвертируемы, так как per (А) = det (А) и per (В) det (В). Матрица J3 = (А + Б) неконвертируема (см. пример 1.2.4). Пример 1.3.11. Пусть А — конвертируемая неотрицательная матрица. Тогда матрица (А + А) конвертируема. Действительно, ф(А + А) = ф(А). По следствию 1.3.6 матрица (А + А) конвертируема.
Обозначение 1.3.12. Пусть А, В — неотрицательные матрицы. Будем говорить, что А , если dij bij для любой допустимой пары индексов.
Теорема 1.3.13. Пусть А, В — вещественные неотрицательные квадратные матрицы с положительным перманентом. Тогда матрица {А + В) конвертируема в том и только в том случае, когда существует конвертируемая матрица С Є Мп(0,1) такая, что ф(А) С и ф(В) С.
Если существует конвертируемая матрица С є Мп(0,1) такая, что ф(А) С и ф(В) С, то в силу неотрицательности матриц А, В, имеем ф{А + В) С. Это означает, что существует матрица D Є Мп(0,1) такая, что ф{А+В) = (CoD). По следствию 1.3.7 матрица CoD конвертируема, а значит по следствию 1.3.6 матрица (А + В) конвертируема.
Докажем обратное. Пусть матрица {А + В) конвертируема. Тогда положим С = ф{А + В). Тогда матрица С конвертируема по следствию 1.3.6, а из неотрицательности матриц Л, В получаем неравенства ф(А) С и ф(В) С. Что и требовалось доказать.
Следствие 1.3.14. Пусть А, В — неотрицательные матрицы и матрица А неконвертируема. Тогда матрица (А + В) неконвертируема.
Максимальные конвертируемые матрицы и знаковая конвертируемость при матричном умножении
Произведение конвертируемых матриц может быть, как конвертируемой, так и неконвертируемой матрицей. Пример 1.3.15. Матрица конвертируема: неконвертируема. Действительно, по следствию 1.3.6 матрица А конвертируема тогда и только тогда, когда конвертируема матрица ф(А ) = J3. В примере 1.2.4 было показано, что матрица J3 неконвертируема.
Пример 1.3.16. Пусть А — конвертируемая (ОД)-матрица. Умножение А на матрицу перестановки дает конвертируемую матрицу.
Как видно из примера 1.3.15 в общем случае сказать что-либо о конвертируемости произведения неотрицательных матриц нельзя. Поэтому мы рассмотрим следующее подмножество (0,1)-матриц.
Определение 1.3.17. Максимальной конвертируемой матрицей называется конвертируемая (ОД)-матрица, в которой замена любого нулевого элемента на единицу дает неконвертируемую матрицу.
Для максимальных конвертируемых матриц удается доказать необходимое условие конвертируемости произведения АВ, где одна из матриц мак симальная конвертируемая, а вторая неотрицательная. Для начала докажем следующую вспомогательную лемму.
Нижняя граница конвертации для неразложимых и вполне неразложимых матриц
Очевидно, что при п 4 в построенной матрице п + б единичных элементов. Действительно, пункты 1 и 2 дают п ненулевых элементов. По пункту 3 имеем подматрицу с 9 ненулевыми элементами, из которых 3 уже были посчитаны как стоящие над главной диагональю. Данная матрица является матрицей смежности сильно связного графа, что следует из пунктов 1 и 2, а значит является неразложимой. Положим а = {4,.. . , п} и (3 = {1, 5,. .. , п}. Подматрица Л[а/3] с точностью до перестановки последней строки на первое место совпадает с матрицей /п_з, следовательно per (Л[а/3]) 0. Подматрица Л(а/3) = .]% — неконвертируемая. По лемме 1.3.18 матрица А неконвертируема.
Замечание 2.3.29. Последний пример показывает, что для конвертируемости неразложимой матрицы верна только оценка в иоп = (п + 6) элементов, общая для всех (0,1) матриц.
Описание неконвертируемых вполне неразложимых (0,1)-матриц с числом единиц на нижней границе конвертации Лемма 2.4.1. Операция свертки вполне неразложимой (ОД)-матрицы дает вполне неразложимую матрицу. ДОКАЗАТЕЛЬСТВО. В силу леммы 2.3.18 можно считать, что дана матрица А Є Мп(0,1) такая, что ац = а\і = 1 и ац = 0 для г 2. Пусть Б = 6(A).
Докажем утверждение от противного. Предположим, что матрица В частично разложима. Тогда в матрице В существует подматрица С размера к х (п — к — 1), состоящая из нулевых элементов. Возможны два случая.
1. Подматрица С не пересекается с первым столбцом матрицы В. Тогда в А подматрица С не будет пересекаться с 1 и 2 столбцами и первой строкой. Расширим подматрицу С в исходной матрице А путем добавления элементов первой строки. Получим нулевую подматрицу С порядка (к + 1) х (п — к — 1). По определению это означает частичную разложимость матрицы Л, что невозможно.
2. Подматрица С пересекается с первым столбцом матрицы В. По построению матрицы В каждому нулевому элементу подматрицы С, лежащему в первом столбце В, соответствует два нулевых элемента матрицы А, которые лежат в соответствующей строке и первом и втором столбцах. Таким образом, подматрицу С можно расширить до нулевой подматрицы С в матрице А порядка кх(п — к). По определению это означает частичную разложимость матрицы А, что невозможно.
Действительно, если выполнено равенство amk = а ті = 1 при каком-то m / г, то при операции свертки эти единичные элементы будут заменены на один элемент, а значит количество ненулевых элементов в матрице уменьшится минимум на три, что противоречит результату леммы 2.4.2.
Для доказательства второй половины утверждения достаточно рассмотреть матрицу At и применить уже полученный результат к строкам матрицы. Последнее утверждение напрямую следует из первых двух, так как не существует пары (amk,ami) = (1,1), где тфг.П
Следствие 2.4.4. Любую вполне неразложимую неконвертируемую матрицу Л Є Мп(0,1) с 2п + 3 единичными элементами можно привести к матрице .]% последовательным применением операции свертки. лемме 2.4.2 операция свертки при п 3 возможна. По лемме 2.4.1 результатом операции свертки будет вполне неразложимая матрица. По следствию 2.4.3 результатом операции свертки будет (ОД)-матрица. Таким образом, имеет место равенство ь {А) = v(&(A)) + 2, а матрица &(А) является вполне неразложимой неконвертируемой матрицей порядка (п — 1) с 2(п — 1) +3 ненулевыми элементами. Таким образом, к матрице &(А) можно повторить операцию свертки. Продолжим, пока п 3. В случае если п = 3, то мы получим вполне неразложимую неконвертируемую (ОД)-матрицу с 9 элементами, которая совпадает с J3. П
Определение 2.4.5. Расширением (0,1)-матрицы А по і-тому столбцу будем называть множество матриц 91(A) такое, что для каждой В Є 91(A) имеем В є Мп+1(0,1), 6М = 61 і+1 = 1 и 6(B) = А.
Замечание 2.4.6. Непосредственно из определения операций свертки и расширения следует, что если В Є 91(A) и Ьц = &І;Ї+І = 1, то в каждой паре (&іг?&і,г+і) не менее одного нулевого элемента.
Лемма 2.4.7. Пусть Y — множество вполне неразложимых неконвертируемых (ОД)-матриц порядка п с (2п + 3) ненулевыми элементами. Тогда любая вполне неразложимая неконвертируемая матрица А порядка (п + 1) с 2(п + 1) + 3 элементами перестановочно эквивалентна одной из матриц из множества Usy9t( ), где в объединении берутся расширения по всем столбцам матриц В. ДОКАЗАТЕЛЬСТВО. ПО лемме 2.3.18 строки и столбцы матрицы можно переставить таким образом, что свертка осуществляется по первой строке и в первой строке два соседних элемента равны единицам. При этом результирующая матрица будет перестановочна эквивалентна той матрице, которая получается в результате свертки до перестановки строк. Таким образом, без ограничения общности, можно считать, что ац = 2i,«+i = 1, а остальные элементы первой строки А равны нулям. По пункту 1 следствия 2.4.3 для каждой пары ( 2то,ь am,«+i); где і 2, известно, что как минимум один элемент равен нулю. По лемме 2.4.1 получаем, что &(А) Є У, а значит согласно определению расширения имеем А Є 9\(&(А)). Лемма доказана. Матрица Rk является основным блоком при описании неконвертируемых (0,1)-матриц с 2п + 3 единичными элементами. Поэтому начнем доказательство со следующей леммы.
Лемма 2.4.9. Пусть Rn Є Mn(0,1) и В Є tR(Rn), где расширение взято не по последнему столбцу и в каждом столбце В не более двух ненулевых элементов. Тогда существуют матрицы перестановки Р, Q такие, что Rn+i = PBQ. Более того, матрицы Р и Q оставляют неподвижными последнюю строку и последний столбец матрицы В.
Пусть расширение выполнено по столбцу с номером к п на столбцы с номерами к и к + 1. При этом столбцы с номером меньше к остаются на месте, а столбцы с номером больше к сдвигаются на один вправо. Новая строка в матрице В ставится на первое место.
Построение примеров знаково конвертируемых матриц
Неравенства (3.11) и (3.12) противоречат друг другу, а значит существует элемент в N не менее чем с (р — 2) ненулевыми координатами. В силу построения множества N это означает, что в N существует вектор, который выражается минимум через (р — 2) вектора Выберем вектор, выражающийся не менее чем через (р — 2) вектора. Обозначим его через Ь = а\ о v. Выберем матрицу X такую, что первая строка без первого элемента совпадают си, а остальные элементы единичные. Далее рассмотрим матрицу С = А о X. Обозначим через С\ первую вектор-строку в матрице С(1). Для матрицы С известно следующее:
Так как Сц 0, і = 1,... , п, то в последнем равенстве не менее (р — 1) отличных от 0 слагаемых, а значит по лемме 3.2.26 можно так умножить некоторые из слагаемых на минус один, что будет получен любой элемент из Fp, в частности, число, равное перманенту исходной матрицы. Пусть эти множители образуют первый столбец матрицы U, остальные элементы которой равны единицам. Тогда будем иметь равенство per (А) = det (С о JJ) = det (А о X о U) = det (А о Z). Построили матрицу Z Є МП(=Ы), которая конвертирует матрицу А. Теорема доказана.
Замечание 3.2.30. Вполне неразложимость матрицы Л является существенным условием в теореме 3.2.29. Действительно, пусть р 3 и п достаточно большое, чтобы п (р — 3) log(n — 1)(р — 1) + 2. Возьмем в качестве матрицы А полученную из матрицы J% 0 /п_з заменой всех элементов выше главной диагонали на единицы. Последовательно применяя формулу Лапласа разложения по последней строке к полученной матрице, получим, что per (А) = per (J3) = б ф 0, так как характеристика поля равна р 3. Таким образом, выполнены все условия теоремы 3.2.29, кроме вполне неразложимости матрицы А. Построенная матрица А будет конвертируема тогда и только тогда, когда конвертируема матрица J3. Из леммы 3.2.13 следует, что матрица .]% неконвертируема для любого поля характеристики р 3, а значит неконвертируема построенная матрица А.
Пример 3.2.31. Теорема 3.2.29 позволяет доказать конвертируемость некоторых матриц. Например, дана вполне неразложимая матрица Л Є Mi Fs), в которой существует строка и столбец без нулевых элементов. Так как М = 21og(13 4) + 2 14, то по теореме 3.2.29 матрица А конвертируема.
Это означает, что выполнены все условия теоремы 3.2.29 и матрица А конвертируема. Следствие 3.2.33. Пусть А Є Мп(р) — частично разложимая матрица, перестановочно эквивалентная блочной верхнетреугольной матрице с вполне неразложимыми блоками А\,... , Ak на главной диагонали, один из которых удовлетворяет условиям теоремы 3.2.29. Тогда матрица Л конвертируема.
Без ограничения общности, можно считать, что блок А\ удовлетворяет требованиям теоремы 3.2.29. Тогда, согласно доказательству теоремы 3.2.29, для любого г Є р существует матрица Хг Є М ДіІ) такая, что det (А\ оХг) = г. Так как блоки А{ вполне неразложимы, то в каждом из них существует ненулевая обобщенная диагональ. По следствию 3.2.27 для каждого из блоков А2,.. . ,Аь существует матрица Y{ Є М (=Ы) такая, что det (АІ о У ) ф 0 при і = 2,... , к. Остается заметить, что определитель мож;ет принимать любое значение, так как первый сомножитель может принимать любое значение в поле, а остальные сомножители не равны нулю. Остается подобрать требуемое значение параметра г.
Если среди блоков есть нулевой, то в матрице не существует обобщенной диагонали без нулевых элементов, а значит per (А) = det (А) = 0.
Рассмотрим еще одно достаточное условие конвертации матрицы над конечным полем с точки зрения существенных элементов. Теорема 3.2.34. Пусть А Є Мп(р), где р — простое число. Пусть в какой-либо строке матрицы А содержится не менее (р— 1)-го существенно ненулевых в смысле определителя элементов. Тогда матрица А конвертируема.
Без ограничения общности, можно считать, что в первой строке содержится не менее {р—\) существенно ненулевых в смысле определителя элементов. Разложим определитель матрицы А по первой строке:
В сумме (3.13) не менее (р— 1)-го ненулевого слагаемого. По следствию 3.2.22 в правой части (3.13) можно умножить часть слагаемых на минус один так, чтобы получить любой наперед заданное число из р, в частности Р = per (А). Рассмотрим теперь матрицу X Є МП(=Ы), где минус единицы стоят только в первой строке на местах с теми номерами, для которых необходимо поменять знак в сумме (3.13). Получим равенство:
Замечание 3.2.35. Требование существования (р — 1)-го элемента существенно не равного нулю в смысле опеределителя вероятно является излишним и может быть заменено на существование (р — 1)-го существенного элемента в одном строке (столбце) матрицы А Є