About Some Properties of Quasi-hadamard Matrices Defining Bijective Transformations

Abstract

The article continues studies of bijective mapping determined by quasi-hadamard matrices started in work [8]. It is proved that for different quasi-hadamard martices there are different mappings. All quasi-hadamard matrices of orders 4 and 8 are also described.

Full Text

1. Введение Статья посвящена разработке методов компактного синтеза биективных преобразований векторных пространств. Работа продолжает исследования, начатые В.Г. Никоновым, Е.С. Сидоровым, В.С. Литвиненко в статьях [8-10]. В основу методов исследования указанных работ было положено использование матриц, порождающих биективные преобразования согласно правилу (3). Определение 1. Квазиадамаровой матрицей называется квадратная матрица над полем действительных чисел, состоящая из элементов {-1, 0, 1} с попарно ортогональными строками и имеющая четный размер, причем каждая строка и каждый столбец такой матрицы содержат хотя бы один нулевой и хотя бы один отличный от нуля элемент. В данной работе будем рассматривать квазиадамаровы матрицы, в каждой строке и в каждом столбце которых ровно по одному нулевому элементу. Матрицы подобного вида, так называемые конференц-матрицы, изучались в работах [1; 2]. Авторы сформулировали понятия нормального вида конференц-матрицы, симметричных и антисимметричных матриц, получили ограничения на размер n, при котором существуют данные виды матриц. В частности, n всегда четно. Обозначим через Vn множество двоичных векторов длины n ∈ ℕ и рассмотрим произвольное преобразование F пространства Vn, заданное системой координатных функций (f1, … , fn). В этом случае преобразование записывается в виде: (1) В связи с простотой технической реализации и большими вычислительными возможностями практический интерес вызывают преобразования, координатные функции которых являются пороговыми. Напомним [6] определение такой функции. Определение 2. Двоичная функция f: Vn → V1 называется пороговой, если существуют действительные числа a1, … , an, c такие, что (2) где суммирование ведется в действительной области. Числа a1, … , an называеются коэффициентами функции или весами, c - порогом. В данной работе описываются все квазиадамаровы матрицы размеров 4 и 8. Вопросы регулярности равновероятных функций из системы (1) рассматриваются в работах [3; 4]. Определение 3. Пусть B = (bij)n × n - квазиадамарова матрица. Будем говорить, что матрица B порождает преобразование которое задается системой координатных функций (f1, … , fn), если для любого : (3) Заметим, что в случае рассматриваемых квазиадамаровых матриц с ровно одним нулевым элементом в каждой строке сумма (3) никогда не обращается в ноль, поскольку в нее входит нечетное число равных по модулю слагаемых. В связи с этим в дальнейшем для наглядности будем использовать наравне с определением и знак строгого неравенства. Определение 4. Пусть A = (aij)n × n - квазиадамарова матрица. Под элементарными преобразованиями матрицы A будем понимать инвертирование, то есть умножение строк (столбцов) на -1, а также перестановки строк (столбцов). Определение 5. Пусть A и B - две квазиадамаровы матрицы. Будем говорить, что они принадежат одному классу K квазиадамаровых матриц, если B получена из A элементарными преобразованиями. При этом класс K будем обозначать K = 〈A〉. Изучению квазиадамаровых матриц посвящены работы [8-10]. В [10] показано, что преобразования, задаваемые квазиадамаровыми матрицами, являются четными. В работе [9] доказывается, что все квазиадамаровы матрицы размером 4, 6, 8 лежат в одном классе. Там же показано, что для этих размеров справедливо утверждение о том, что матрица, транспонированная к квазиадамаровой задает обратное отображение. Геометрический подход развивается в работе [8]. Приведем следующее утверждение, доказанное в [7] для матриц над полем из двух элементов, которые задают преобразования по правилу (3). Данное свойство играет большую роль в дальнейших рассуждениях. Утверждение 1. Пусть A = (aij)n × n - квазиадамарова матрица размером n × n и πA: GF(2)n → GF(2)n - преобразование, порожденное матрицей A. Тогда если πA(x) = y, то πA(x̅) = y̅. Доказательство. Рассмотрим πA(x) = f(x) = (f1(x), … , fn(x)) Тогда достаточно показать, что если fi(x) = yi, то fi(x̅) = y̅i для любого . Последнее следует из того, что если то для значения координатной функции на отрицании исходного вектора справедливо неравенство: При этом данная сумма всегда отлична от нуля, поскольку в нее входит нечетное число слагаемых, каждое из которых по модулю равно 1/2. 2. Единственность матрицы, задающей преобразование Утверждение 2. Различным квазиадамаровым матрицам соответствуют различные преобразования. Доказательство. Пусть A = (aij)n × n и B = (bij)n × n - квазиадамаровы матрицы размера n, где n - четно, пусть их первые строки задают равные координатные функции πA1 = πB1. Будем доказывать равенство А1 = В1. Из этого будет следовать, что разным строкам соответствуют разные координатные функции, а значит, разным квазиадамаровым матрицам соответствуют разные подстановки. Без ограничения общности будем считать (здесь и далее в доказательстве опустим индекс строки), что an = 0. Тогда последняя переменная функции πA1 фиктивна. Покажем, что остальные переменные существенны: Рассмотрим вектор β = (β1, ... , βn), первые n - 2 координаты которого определены следующим образом: если если если если Согласно определению, (4) Тогда, поскольку для вектора β сумма первых n - 2 слагаемых равна нулю, и последнее слагаемое также равно нулю, (n - 1)-я переменная существенна. Аналогичным образом несложно показать, что и все остальные переменные, не соответствующие нулевому элементу в строке, также существенны. Таким образом, если предположить, что πA1 = πB1, то получаем, что в силу единственности фиктивной переменной an = bn = 0, и все остальные координаты в этих строках равны либо 1, либо -1. Покажем, что на самом деле строки равны. На первом шаге покажем, что в строках A1 и B1 совпадают по крайней мере n/2 координат, кроме нуля. Предположим, что это не выполнено, то есть у A1 и B1 по крайней мере n/2 координат отличаются (пусть это будут первые n/2 координат). Тогда для вектора α(1) такого, что последние n/2 координат определены произвольным образом, а первые n/2 по правилу: если если будет выполнено 1 = πA1(α(1)) ≠ πB1(α(1)) = 0, то есть функции различны. Значит, у строк A1 и B1 совпадают по крайней мере n/2 координат, кроме нуля. Пусть совпдают координаты под номерами n/2, … , n - 1. Остаток доказательства проведем в n/2 - 1 шагов (от шага под номером 2 до шага n/2). К началу i-го шага имеем множество пройденных координат для которых известно, что строки A1 и B1 в них совпадают: \\Ki. На шаге под номером i покажем, что хотя бы для одной координаты k ∈ Si будет выполнено: ak = bk. Если |Si| = 1, то есть i = n/2, то в силу четности n, во множестве Kn/2 лежит четное число элементов. Напомним, что Так как |Kn/2| - четно, и строки A1 и B1 совпадают в координатах из Kn/2, можем рассмотреть вектор (α(n/2)) такой, что для него сумма слагаемых с координатами из Kn/2 в (4) равна нулю. Это означает, что значение функции на этом векторе определяется элементами a1 и b1, и если они различны, то строки A1 и B1 задают различные координатные функции, что противоречит нашему предположению. Значит, a1 = b1. Далее считаем, что |Si| > 1. Если |Ki| - четно, то рассмотрим вектор α(i) = (α1, … , αn) такой, что сумма координат с номерами из Ki в (4) равна нулю. Тогда, если все координаты строк A1 и B1 с номерами из Si различны, то вектор α(i) на координатах j ∈ Si зададим следующим образом: если (5) если Тогда, очевидно, координатные функции, задаваемые строками A1 и B1 на векторе α(i) будут принимать различные значения. Если |Ki| - нечетно, то, аналогично предыдущему, рассмотрим такой вектор α(i) = (α1, … , αn), что сумма координат с номерами из Ki в (4) равна 1/2. Координаты вектора α(i) с номерами j ∈ Si зададим также согласно правилу (5). Ясно, что координатные функции, задаваемые строками A1 и B1 на векторе α(i) будут принимать различные значения. Таким образом, мы показали, что хотя бы в одной координате s ∈ Si строки A1 и B1 совпадают. Пусть s = n/2 - i + 1, и имеем равенства \\Ki + 1. и можно перейти на следующий шаг. К исходу шага n/2 получим: то есть для всех ненулевых координат j строк A1 и B1 известно, что aj = bj, что и требовалось показать. 3. Описание квазиадамаровых матриц размером 4 и 8 В работе [9] показано, что все квазиадамаровы матрицы размером 4 и все квазиадамаровы матрицы размером 8 рассматриваемого вида эквивалентны относительно преобразований инвертирований и перестановок строк и столбцов, то есть лежат в одном классе. Покажем, чему равны мощности этих классов, и от каких преобразований можно отказаться без потери матриц в классе. Рассмотрим матрицу Сначала покажем, что все матрицы, получающиеся из исходной указанными преобразованиями, могут быть получены из нее без использования перестановок строк. Для этого потребуются некоторые предварительные рассуждения. Лемма 1. Пусть A2, A3, A4 - матрицы, полученные из A перестановкой первой и, соответственно, второй, третьей, четвертой строк. Тогда они могут быть получены из A перестановками столбцов и инвертированиями строк, столбцов. Доказательство. Приведем каждую из матриц Ai, к исходной матрице A, используя перестановки столбцов и инвертирования строк, столбцов: Здесь первое преобразование есть перестановка 3 и 4 столбцов, второе преобразование есть инвертирование 2 столбца и 4 строки. Здесь первое преобразование есть перестановка 2 и 4 столбцов, второе преобразование есть инвертирование 2, 3, 4 столбцов и 4 строки. Здесь первое преобразование есть перестановка 1 и 4 столбцов, второе преобразование есть инвертирование 3 столбца и 3 строки. Заметим, что все проведенные преобразования инволютивны, а следовательно, обратимы. Значит, матрицы A2, A3, A4 могут быть получены из A без использования перестановки строк. Утверждение 3. Пусть матрица B получена из матрицы A перестановками и инвертированиями строк и столбцов. Тогда B может быть получена из A инвертированиями строк и столбцов, перестановками только столбцов. Доказательство. Заметим, что любая перестановка ℤn есть произведение транспозиций вида (1, α), [5: 234]. Тогда B получена из A транспозициями указанного вида и инвертированиями строк и столбцов. Обозначим за D данное множество преобразований В лемме 1 было показано, что любая транспозиция строк указанного вида исходной матрицы может быть получена транспозициями столбцов, инвертированиями строк и столбцов. Последнее множество преобразований обозначим за S. Пусть g - такое преобразование, что g(A) = B, g = g1 … gt, где gi ∈ D - либо транспозиция строк или столбцов, либо инвертирование строк, столбцов, . Пусть среди g1, … , gt ровно k транспозиций строк. Индукцией по k ∈ ℕ покажем, что g = gʹ1 … gʹs, где gjʹ ∈ S - транспозиция строк, либо инвертирование строки или столбца, . 1. k = 0 - очевидно. 2. Пусть утверждение верно при k - 1 транспозиции строк. Докажем для k. Пусть l ∈ ℕ таково, что gl - транспозиция строк и - преобразование, не являющееся транспозицией строк. Пусть h ∈ S. Покажем, что h ∙ gl = gl ∙ hʹ, hʹ ∈ S. Рассмотрим возможные случаи: а) h - инвертирование строки под номером . Если gl меняет первую строку со строкой под номером , и при этом i не лежит в {1, j}, то, очевидно h ∙ gl = gl ∙ h. Если же i ∈ {1, j}, то h ∙ gl = gl ∙ hʹ, где hʹ - инвертирование строки под номером j, если i = 1 и 1, если i = j. б) h - инвертирование столбца. Тогда в любом случае h ∙ gl = gl ∙ h. в) h - транспозиция столбцов. Тогда также нетрудно видеть, что h ∙ gl = gl ∙ h. Таким образом, g = gl ∙ gʹ1 … gtʹ, и среди g1ʹ, … , gtʹ ровно k - 1 транспозиция строк. Заменяя gl по правилу из леммы 1, получаем, что g = g1ʺ … gsʺ, и среди g1ʺ, … , gsʺ ровно k - 1 транспозиций строк. Индуктивный переход осуществлен, и утверждение доказано. Действуя аналогичным образом, нетрудно показать, что возможно отказаться от перестановок столбцов, оставив только перестановки строк, при этом потерь матриц не произойдет. Покажем теперь, что из 28 возможных инвертирований ровно от половины можно отказаться. Действительно, обозначим за gi инвертирование строки с номером i, а за hi инвертирование столбца с номером i, . Тогда их произведение g1 … g4 ∙ h1 … h4 = e, где e - тождественное преобразование матрицы. Заметим, кроме того, что все gi, hi попарно перестановочны между собой и сами себе обратны. Это означает, что любому инвертированию где матрицы A однозначно соответствует его дополнение до полного произведения g1 … g4 ∙ h1 … h4 = e. Получается, все инвертирования разбиваются на пары взаимно дополняющих, причем инвертирования из одной пары одинаковым образом действуют на матрицах. Значит, чтобы получать известным способом матрицы из A, достаточно брать лишь половину, то есть 27 инвертирований. Итак, мы показали, что все матрицы могут быть получены из исходной 27 инвертированиями и 4! оставшимися перестановками, то есть всего 3072 способами. Также нетрудно показать, что от других преобразований отказаться без потери матриц нельзя. Действительно, пусть B и C - матрицы, полученные из A различными преобразованиями, и пусть B = C. Пусть в i-м столбце ноль расположен в координате под номером ki. Тогда, очевидно, для получения матриц B и C использовалась одна и та же перестановка столбцов (k1, k2, k3, k4), переводящая A в D. Значит, матрицы B и C получены из D различными инвертированиями g1 и g2, но при этом сами матрицы совпадают. При этом B получена из C одним из 27 инвертирований. Но данное инвертирование является произведением g1 ∙ g2, и не является тождественным, так как инвертирования g1 и g2 взяты из разных пар взаимно обратных. Значит, матрицы B и C различны. В дальнейшем будем считать, что 3072 матрицы получены из исходной 4! перестановками столбцов и всеми инвертированиями, не включающими умножение последней строки на -1. Обратимся теперь к квазиадамаровым матрицам размером 8. Рассмотрим матрицу Строки данной матрицы, так же как и ее столбцы, попарно ортогональны, и преобразование, порожденное матрицей B, задает подстановку (обозначим ее за h) степени 256 с цикловой стркутурой [28, 640] и со следующей второй строкой в двухстрочной записи и стандартной полубайтовой кодировке: 26 59 c 4c 35 15 4 1d 60 70 64 48 34 71 24 54 12 1a e 18 16 11 14 1c 32 50 0 58 30 10 94 90 47 43 46 4d 7 55 5 45 62 41 44 40 65 51 c4 c5 2 53 6 4a 17 13 86 95 42 52 c2 c0 92 d1 84 d0 2b 29 2c 9 25 39 2d d 20 69 28 68 21 31 a4 a9 2a 1b a 8 33 19 8c 99 22 38 a8 88 b0 b1 a0 98 23 4b f 49 27 1 85 8d 63 61 e0 c9 a1 e1 a5 c1 3 b 8a 8b 83 93 87 89 a2 c3 82 c8 a3 91 80 81 7e 7f 6e 5c 37 7d 3c 5d 76 78 6c 7c 74 75 f4 fc 3e 5a 1e 5e 36 1f 9e 9c 72 7a fe d8 b6 f0 b4 dc 67 5f 4e 4f 77 57 c7 dd 66 73 e6 cc f7 f5 e4 d5 56 5b ce de 97 d7 96 df f2 d2 c6 da f6 d3 d6 d4 2f 7b 2e 6d 3f 3d ad bd 6a 79 ec e8 b5 f9 ac fd 3a 3b ae 9a bf bb be 9d ba fa aa f8 b2 b9 bc b8 6f 6b ef cf a7 ff af cd e3 eb ee e9 e7 f1 e5 ed ab db 8e cb b7 9b 8f 9f e2 fb ea ca b3 f3 a6 d9. Перед формулировкой утверждения о мощности класса 〈B〉 введем следующие обозначения. 1. Пусть g ∈ - произвольная подстановка степени 8. Обозначим за P(g) = (pi, j)8 × 8 подстановочную матрицу, соответствующую подстановке g: pi, j = 1 тогда и только тогда, когда P(i) = j. 2. Обозначим за G группу, порождаемую тремя элементами g1 = (1, 5, 6) (2, 7, 4), g2 = (0, 1, 2) (4, 6, 5), g3 = (1, 2) (3, 7) (5, 6): 3. Обозначим за M множество представителей левых смежных классов группы по подгруппе G: M = {ε, (6 7), (5 6), (5 6 7), (5 7 6), (5 7), (4 5), (4 5)(6 7), (4 5 6), (4 5 6 7), (4 5 7 6), (4 5 7), (4 6 5), (4 6 7 5), (4 6), (4 6 7), (4 6)(5 7), (4 6 5 7), (4 7 6 5), (4 7 5), (4 7 6), (4 7), (4 7 5 6), (4 7)(5 6), (3 4), (3 4)(6 7), (3 4)(5 6), (3 4)(5 6 7), (3 4)(5 7 6), (3 4)(5 7), (3 4 5), (3 4 5)(6 7), (3 4 5 6), (3 4 5 6 7), (3 4 5 7 6), (3 4 5 7), (3 4 6 5), (3 4 6 7 5), (3 4 6), (3 4 6 7), (3 4 6)(5 7), (3 4 6 5 7), (3 4 7 6 5), (3 4 7 5), (3 4 7 6), (3 4 7), (3 4 7 5 6), (3 4 7)(5 6), (7)(3 5 4), (3 5 4)(6 7), (3 5 6 4), (3 5 6 7 4), (3 5 7 6 4), (3 5 7 4), (3 5), (3 5)(6 7), (3 5 6), (3 5 6 7), (3 5 7 6), (3 5 7), (3 5)(4 6), (3 5)(4 6 7), (3 5 4 6), (3 5 4 6 7), (3 5 7 4 6), (3 5 7)(4 6), (3 5)(4 7 6), (3 5)(4 7), (3 5 4 7 6), (3 5 4 7), (3 5 6)(4 7), (3 5 6 4 7), (3 6 5 4), (3 6 7 5 4), (3 6 4), (3 6 7 4), (3 6 4)(5 7), (3 6 5 7 4), (3 6 5), (3 6 7 5), (3 6), (3 6 7), (3 6)(5 7), (3 6 5 7), (3 6 4 5), (3 6 7 4 5), (3 6)(4 5), (3 6 7)(4 5), (3 6)(4 5 7), (3 6 4 5 7), (3 6 4 7 5), (3 6 5)(4 7), (3 6)(4 7 5), (3 6 5 4 7), (3 6)(4 7), (3 6 4 7), (3 7 6 5 4), (3 7 5 4), (3 7 6 4), (3 7 4), (3 7 5 6 4), (3 7 4)(5 6), (3 7 6 5), (3 7 5), (3 7 6), (3 7), (3 7 5 6), (3 7)(5 6), (3 7 6 4 5), (3 7 4 5), (3 7 6)(4 5), (3 7)(4 5), (3 7 4 5 6), (3 7)(4 5 6), (3 7 5)(4 6), (3 7 4 6 5), (3 7 5 4 6), (3 7)(4 6 5), (3 7 4 6), (3 7)(4 6)}. 4. Введем аналоги групп , G и множества M во множестве подстановочных матриц размером 8: 5. Инверсными матрицами будем называть диагональные матрицы с ±1 на диагонали. Утверждение 4. Класс 〈B〉 содержит ровно 120 ∙ 215 ∙ 8! элементов. При этом любая матрица C из класса 〈B〉 единственным образом представляется в виде С = Δ1 ∙ П1 ∙ В ∙ П2 ∙ Δ2, (6) где ∆1 и ∆2 - инверсные матрицы, причем в матрице ∆1 последняя строка неотрицательна, П1 и П2 - подстановочные матрицы, причем П1 ∈ Mʹ. Доказательство. Число элементов в классе <B> не превосходит 216 ∙ (8!)2. Заметим, что число инвертирований всегда можно сократить в 2 раза, при необходимости домножив матрицу C слева и справа на -E, добившись того, чтобы последняя строка в первой инверсной матрице была неотрицаетльна. Получаем оценку: |〈B〉| ≤ 215 ∙ (8!)2. Рассмотрим произвольный элемент ∆̅1 ∙ П̅1 ∙ B ∙ П̅2 ∙ ∆̅2 класса 〈B〉. Подсчитаем число таких инверсных матриц ∆̃1 и ∆̃2 и подстановочных П̃1 и П̃2, что будет выполнено равенство: ∆̅1 ∙ П̅1 ∙ B ∙ П̅̅2 ∙ ∆̅2 = ∆̃1 ∙ П̃1 ∙ B ∙ П̃2 ∙ ∆̃2. (7) Равенство (7) равносильно следующему: П̃1-1 ∙ ∆̃1 ∙ ∆̅1 ∙ П̅1 ∙ B ∙ П̅2 ∙ ∆̅2 ∙ ∆̃2 ∙ П̃2-1 = В. (8) В данном равенстве матрицы П̃1-1, i = 1, 2 подстановочные, а матрицы ∆̃1 ∙ ∆̅1 и ∆̅2 ∙ ∆̃2 - инверсные. Значит, существуют такие инверсные матрицы ∆ʹ1 и ∆ʹ2, что равенство (9) будем равносильно следующему: ∆ʹ1 ∙ П̃1-1 ∙ П̅1 ∙ B ∙ П̅2 ∙ П̃2-1 ∙ ∆ʹ2 = В. (9) Здесь матрицы П̅1 и П̅2 фиксированы, а матрицы П̃1-1 и П̃2-1 пробегают все элементы группы Sʹ. Значит, и произведения П̃1-1 ∙ П̅1-1 и П̅2 ∙ П̃2-1 также пробегают все элементы группы Sʹ. С учетом этого и того, что (7) равносильно (9) получаем, что число представлений вида (7) для произвольного элемента класса 〈B〉 равно числу представлений этого вида для матрицы B. Подсчитаем это число с помощью программы. Предварительно сделаем замечание, позволяющее существенно сократить перебор. Пусть g ∈ . Обозначим за Pʹ(g) = (pʹi, j)8 × 8 матрицу, симметричную матрице P(g) относительно побочной диагонали. Тогда Pʹ(g) - подстановочная, при этом pʹi, j = 1 тогда и только тогда, когда p7 - i, 7 - j = 1. Заметим, что равенство B = Δ1 ∙ P(g) ∙ B ∙ П ∙ Δ2, для некоторой подстановочной матрицы П и некоторых инверсных ∆1 и ∆2 может выполнять только при условии П = Pʹ(g). Подсчитаем число подстановок g ∈ , для которых существуют инверсные матрицы ∆1 и ∆2 (здесь и всюду далее в ∆1 последняя строка неотрицательна) такие, что выполнено равенство: B = Δ1 ∙ P(g) ∙ B ∙ Pʹ(g) ∙ Δ2. (10) Посчитаем это количество с помошью программы, написанной на языке Python, перебор будем вести по 215 парам (∆1, ∆2) и по 8! подстановкам g ∈ . В случае равенства программа инкрементирует переменную-счетчик и добавляет подстановку g в список подстановок, для которых возможно равенство (10). В результате выполнения программы получено, что искомое число равно 336, а список содержит 336 подстановок, замкнутых относительно умножения, то есть образующих группу G, которая порождается тремя подстановками g1, g2, g3. Покажем теперь, что произвольная матрица C ∈ 〈B〉 может быть представлена в виде (6). Пусть С = ∆ʹ1 ∙ Пʹ1 ∙ B ∙ Пʹ2 ∙ ∆ʹ1, (11) для произвольных подстановочных матриц Пʹ1 и Пʹ2 и произвольных инверсных матриц ∆ʹ1 и ∆ʹ2. Тогда существует единственная подстановка g ∈ M такая, что матрица Пʹ1 лежит в смежном классе P(g)Gʹ, то есть Пʹ1 = Индукцией по n ∈ ℕ покажем, что существуют такая подстановочная матрица Пʺ2 и инверсные матрицы ∆ʺ1 и ∆ʺ2 такие, что справедливо равенство: С = ∆ʺ1 ∙ P(g) ∙ B ∙ Пʺ2 ∙ ∆ʺ2. (12) При n = 0 доказываемое равенство выполнено. Пусть оно выполнено при n = n0. Покажем справедливость при n = n0 + 1. Непосредственной проверкой можно убедиться, что справедливы следующие равенства: Значит, в любом случае существуют такие подстановочная матрица П и инверсные ∆ и ∆ʹ такие, что справедливо равенство: gʹn0 + 1 ∙ B = Δ ∙ В ∙ П ∙ ∆ʹ. Подставляя в (11) выражение для матрицы Пʹ1 и заменяя произведение gʹn0 + 1 ∙ B, получаем: С = ∆ʹ1 ∙ P(g) ∙ gʹi1 ... gʹin0 ∙ Δ ∙ В ∙ П ∙ ∆ʹ ∙ Пʹ2 ∙ ∆ʹ2. Матрицы P(g) ∙ gʹi1 … gʹin0 и Пʹ2 - подстановочные, поэтому можно переставить матрицы ∆ и ∆ʹ соответственно влево и вправо, при этом они могут измениться, но останутся инверсными. Значит, для некоторых инверсных матриц ∆̅1 и ∆̅2 справедливо равенство: С = ∆̅1 ∙ P(g) ∙ gʹi1 ... gʹin0 ∙ В ∙ П ∙ Пʹ2 ∙ ∆ʹ2. По предположению индукции существуют инверсные матрицы ∆ʺ1 и ∆ʺ2 и подстановочная матрица Пʺ2 такие, что справедливо равенство (12). Для завершения доказательства осталось заметить, что если в матрице ∆ʺ1 последняя строка не является неотрицательной, то домножим правую часть равенства (12) слева и справа на матрицу -E, где E - единичная, и равенство примет требуемый вид. Единственность выбора подстановочных матриц следует из единственности выбора смежного класса (легко показать, что если имеется два различных представления вида (11) для матрицы C, то подстановочные матрицы должны лежать в одном смежном классе симметрической группы по подгруппе Gʹ). Единственность выбора инверсных матриц показывается аналогично рассуждениям для случая квазиадамаровых матриц размером 4.