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

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013 8
обнуление первой строки не исключает перестановок столбцов в
матрице, и поэтому необходимо, по аналогии с исключением
строчных перестановок, наложить еще условие неперестановочно-
сти столбцов в матрице.
Реализация описанных ограничений и условий формирует матрицу
8-го порядка (0, 15, 51, 60, 85, 90, 102, 105 — строки). Всего на 8-м по-
рядке имеем 28 ⋅ 8! ⋅ 23 ⋅ 2 ⋅ 3 ⋅ (5 + 4 + 1) = 220 ⋅ 33 ⋅ 52 ⋅ 7 = 4 954 521 600
матриц, где 2 8 — строчно-инверсное, 8! — строчно-перестановочное;
23 — столбцово-инверсное, (22 − 1) — столбцово-перестановочное се-
мейство алгоритмичесткого формирования, а именно: 2 ⋅ 3 ⋅ (5 + 4 + 1) =
= 30 + 24 + 6 = 60, каждое из которых включает 2 ⋅ 3 соответствующих
ортогональных дополнений.
Формируя и анализируя в принятых условиях и ограничениях се-
мейства 12, 16, 20, …, n-го, легко заметить, что на компактных запи-
сях их семейств (табл. 5) появляются в них, помимо описанных выше
семейств, семейства новых столбцовых наборов.
Действительно, если порядки 4-й и 8-й имели соответственно
единственные наборы столбцов (0, 3, 5, 6 ) и (0, 15, 51, 60 , 85, 90 ,
102 , 105 ), часть которых (черта сверху) могла участвовать еще и в ин-
версном виде, то на порядке 12-м получаем 16 столбцовых наборов
(табл. 6).
Эти 16 столбцовых наборов порождены условием формирования
семейства из 2n−1 неинверсных, в естественном порядке строк. Пере-
становка столбцов в наборах может привести к нарушению есте-
ственного порядка следования строк. Алгоритм, восстанавливая есте-
ственный порядок строк, исказит тем самым набор столбцов.
Понимая это, легко «возвратить» эти 16 столбцовых наборов к двум
начальным (см. табл. 6, столбцовые наборы 1 и 2).
Этот же результат может быть получен при переходе к алгорит-
му построения левой половины матрицы из 2
5 C = 10 полустрок,
а правой — из 3
6 C = 20.
Итак, на 12-м порядке в принятых нами условиях и ограничениях
формируются 10 321 920 матриц, что в компактной записи выглядит
как 2 ⋅ 4 ⋅ 9 ⋅ 4480 ⋅ 32 = 10 321 920, а для нулевой первой строки
2 ⋅ 4 ⋅ 9 ⋅ 840 = 60 480 матриц (см. табл. 5).
Объемы столбцово-перестановочных семейств 840, 820, 720,
700, 420, 400, 300, 280 соответствуют значениям n/2 − 2 разрядов
0000, 0001, 0100, 0101, 0111. Для определения всех объемов доста-
точно знать максимальный объем на значении 0000 и его уменьше-
ние по каждому значащему разряду: 0001 сокращает на 20
(840 − 20), 0010 — на 120 (840−120), 0100 — на 420 (840−420). По-
следняя старшая максимально возможная матрица соответствует
значению 0111, хотя в n ⁄2−2 для n = 12 имеется еще и четвертый
разряд, но на значении 1000 матрица не формируется 2 4 – 8 = 2 3.