Page 3 - Разбиения семейства матриц Адамара

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013 3
В данной работе предлагается подход к подсчету числа матриц и
их классификации, основанной не на использовании классов эквива-
лентности, а на разбиении семейства матриц Адамара по его кон-
структивным особенностям.
Формирование семейства матриц Адамара может быть реализо-
вано как из строк, так и из столбцов. Эти семейства будут равны (до-
казательство от противного) и будут содержать симметрические
и\или транспонированные пары матриц. Воспользуемся взаимно од-
нозначным соответствием элементов матрицы (+1 ↔ 0, −1 ↔ 1) и
формированием матриц из строк, т. е. отобразим строки матриц дво-
ичными числами от 0 до 2 n − 1.
Формируя и анализируя семейства порядков 1, 2, 4, 8, 12, ..., n-го
из 2 n исходных строк, видим, что любая матрица семейства принад-
лежит семейству из 2 1, 22, …, 2n матриц, отличающихся друг от друга
инверсиями одной, двух, трех, …, n ее строк. Такие матрицы строчно
инверсны друг другу. Всего их 2n, и они образуют строчно-инверсное
семейство. Инверсия означает замену значений «0» на «1», а «1» на
«0» в двоичном представлении числа.
Разбить строчно-инверсное семейство можно многими способа-
ми, выбрав в нем любую матрицу и приняв ее «неинверсной». Тогда
остальные 2 n − 1 «инверсных» будут отличаться от нее инверсиями
одной, двух, трех, …, n ее строк. В качестве «неинверсной» удобно
выбрать матрицу с нулевым старшим столбцом — старшими разря-
дами двоичных чисел-строк. Тогда любая из 2n − 1 «инверсных» бу-
дет содержать одну, две, три, …, n инвертированных строк. Индика-
тором строчной инверсии будет служить столбец старших разрядов:
если в нем одни нули и нет ни одной единицы — матрица неинверс-
ная; если в нем есть хоть одна единица — матрица инверсная: из-за
инверсии в ней строки с единицей находятся в левом столбце —
старшем разряде этой строки.
При таком разбиении строчно-инверсного семейства разбивается
и 2 n исходных строк — двоичных чисел, из которых это семейство
сформировано, на две части по 2 n−1 строк в каждой. Одна часть с ну-
левыми старшими разрядами (неинверсные), другая — с единичными
(инверсные).
Исключение строчно-инверсного семейства при учете его суще-
ствования с помощью коэффициента 2 n легко осуществить, исключив
из перебора 2n−1 инверсных строк, но оставив в качестве исходных
2n−1 неинверсные («0» в старшем разряде) и сформировав только не-
инверсные матрицы.
Формируя и анализируя семейства порядков 2, 4, 8, …, n-го из
2n−1 исходных неинверсных строк, видим, что любая такая матрица
принадлежит семейству из 2!, 4!, 8!, …, n! матриц, отличающихся
одна от другой перестановками двух, трех, четырех, …, n ее строк.
Такие матрицы строчно-перестановочны друг другу. Всего их n!, и
они образуют строчно-перестановочное семейство.