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

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013

4

Разбить строчно-перестановочное семейство можно многими спо-

собами, выбрав в нем любую из матриц и приняв ее «неперестановоч-

ной». Тогда остальные

n

! − 1 «перестановочных» матрицы будут отли-

чаться от нее перестановками двух, трех, четырех, …,

n

ее строк. В

качестве «неперестановочной» удобно выбрать матрицу с естествен-

ным, или лексикографическим, порядком следования ее строк. Тогда

любая из

n

! − 1 «перестановочных» матриц будет иметь нарушенный

перестановками порядок следования строк, что и будет служить инди-

катором перестановки (или неперестановки) строк в матрице. Порядок

строк в матрице естественный — матрица неперестановочная, нару-

шен естественный порядок — перестановочная. Такое разбиение

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

ных строк на строки в естественном порядке следования или в нару-

шенном, неестественном. Наложив ограничение естественности по-

рядка следования исходных 2

n

−1

неинверсных строк легко исключить

все матрицы строчно-перестановочного семейства из перебора, кроме

одной — с естественным порядком следования строк, а исключенные

учесть коэффициентом

n

!. Формируемое с такими ограничениями се-

мейство будет содержать и строчно-неинверсные и строчно-

неперстановочные матрицы с естественным порядком следования и

неинверсных строк в них, и самих матриц в семействе, т. е. будут ис-

ключены и 2

n

строчно-инверсные, и

n

! строчно-перестановочные.

Формируя и анализируя семейства порядков 4, 8, 12, …,

n-

го из

2

n

−1

неинверсных («0» в старшем разряде) естественно упорядочен-

ных строк имеем на 4-м порядке две матрицы: они строчно-

неинверсные и строчно-неперестановочные, но отличаются инверси-

ями своих последних столбцов 6 = 9, 9 = 6 (черта сверху) — они

столбцово-инверсные. Нижняя строка (1 1 1 2) является компактной

записью семейства 4-го порядка с исключенным строчно-инверсным

и строчно-перестановочным семействами. При нумерации строк его

матриц снизу вверх (1, 2, 3, 4) (табл. 2) единица в строках 1, 2, 3

(

n –

1) означает число ортогональных дополнений или наборов строк,

дополняющих все имеющиеся верхние до полной матрицы Адамара,

двойка в строке 4 означает возможное число строк или столбцовых

инверсий в принятых ограничениях.

Отметим также, что на порядках 4, 8, 12, ...,

n

столбцово-

инверсное семейство будет содержать соответственно 2

1

, 2

3

, 2

5

, ...,

2

n

⁄2−1

столбцово-инверсных матриц, в которых все

n

/2−1 младших

разрядов принимают значения 0, 1, 2, …, 2

n

/2

− 1. Перестановки

столбцов в таких матрицах от действия 2

n

/2−1

различных возможных

столбцовых инверсий в

n

/2 − 1 младших разрядах не происходят. В

семействах матриц на порядках 4, 8, 12, …,

n

первые три столбца в

таких матрицах слева (на 4-м порядке это столбцы 0, 3, 5) будут

всегда сохранять свой вид и не изменяться с точностью до порядка.

Первый — из

n

нулей, второй — из

n

/2 нулей сверху и

n

/2 единиц

снизу; третий — из

n

/4 нулей сверху,

n

/4 единиц снизу, затем

n

/4