Page 1 - Разбиения семейства матриц Адамара
Basic HTML Version
ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
1
УДК519.142.6
Разбиения семейства матриц Адамара
В.А. Дегтярь
1
, Т. Э. Кренкель
2
, А. П. Скотников
3
, А. В. Сукк
4
1
ООО «Aveva», Москва, 105066, Россия
2
МТУСИ, Москва, 111024, Россия
3
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
4
МГУ им. М.В. Ломоносова, Москва, 119991, Россия
Предложены и исследованы разбиения семейства матриц Адамара по
его конструктивным особенностям и модель таких разбиений.
E-mail:
Ключевые слова:
матрица Адамара, разбиение.
Проблема матриц Адамара заключается в поиске их числа и
свойств — красивейшая и сложнейшая задача перечислительной ком-
бинаторики, безуспешно решаемая более полувека [1]. Понятно, что
работать с семействами таких мощностей без их разбиения невозмож-
но: две матрицы на 1-м порядке; восемь — на 2-м; 768 — на 4-м;
5
⋅
10
9
— на 8-м; 2
⋅
10
19
— на 12-м; 8,9
⋅
10
31
— на 16-м; 1,5
⋅
10
21
— на
20-м; 8,9
⋅
10
30
— на 24-м; 1,1
⋅
10
40
— на 28-м; 6,3
⋅
10
96
— на 32-м; … .
Семейство — всевозможные матрицы, различные, без пропусков,
без повторов, удовлетворяющие определенным свойствам.
Матрица
H
Адамара из (±1) имеет ортогональные строки, столб-
цы:
H
т
H
=
nE
, где т — транспонирование;
E
— единичная матрица;
порядок
n
= 1, 2, 4
k
при натуральном
k
.
Условие эквивалентности
H
i
=
PH
j
Q
, где
P
,
Q
— мономиальные
матрицы с одним ненулевым элементом в любой строке, столбце, рав-
ном ±1, оговаривает свойство семейства эквивалентных матриц, но не
определяет их число, так как неизвестны количества матриц
P
и
Q
.
Известен подход к нахождению числа матриц, при котором инди-
видуально для исследуемого порядка ищут с помощью переборного
алгоритма по одному представителю в каждом из классов эквива-
лентности, тем самым перечисляют эти классы. Затем, например, с
помощью алгоритма «nauty» поиска автоморфизмов [2] по имеюще-
муся представителю эквивалентного класса определяют его мощ-
ность. Сумма мощностей всех неэквивалентных классов и есть мощ-
ность всего семейства. Например, для
n
= 16 (табл. 1) число матриц
определено и по эквивалентности, и через разбиения этого семейства.
В результатах, полученных исследователями для порядков
n
= 16, 20
в [3, 4], для
n
= 24, 28 в [5, 6], для
n
= 32 в [7], используют классы эк-
вивалентности в качестве основы.
