ПОСЛЕДОВАТЕЛЬНОСТИ ТЮРИНА

W=
A
B
C
D
 –B 
A
 –D 
C
 –C 
D
A
 –B 
 –D 
 –C 
B
A
G=
A
 BR 
 CR 
 DR 
 –BR 
A
 D'R 
 –C'R 
 –CR 
 –D'R 
A
 B'R 
 –DR 
 C'R 
 –B'R 
A


Массив Вильямсона W требует для своего построения симметричные циклические матрицы, удовлетворяющие условию ортогональности столбцов массива: A2+B2+C2+D2=4wI, w – порядок матриц Вильямсона. Эта идея была развита двумя авторами (Goethals and Seidel) массивом G, когда симметричность не требуется, остается условие AA'+BB'+CC'+DD'=4wI, R – матрица флипа (обратная диагональной). С симметричными блоками оба типа конструкций W и G тождественны друг-другу, различие касается несимметричных матриц. Целесообразность нововведения поясняется тем, что на порядке 35 матриц Вильямсона A, B, C, D полный компьютерный перебор не дал решения, и такие матрицы неизвестны для порядков 35, 155, 171, 203, 227, 291, 323, 371, 395, 467, 483, 563, 587, 603, 635, 771, 875, 915, 923, 963, 1131, 1307, 1331, 1355, 1467, 1523, 1595, 1643, 1691, 1715, 1803, 1923, 1971, согласно работе Тсиа и Себерри.

Тюрин предложил к этой идее разложение матриц Гетхальса-Зейделя в базисе из четырех матриц c элементами {0, ±1}, построенных при помощи T-последовательностей, ненулевые части которых получены попарным сложением и вычитанием базовых последовательностей. Базовые последовательности строятся, в свою очередь, объединением четырех последовательностей Тюрина порядков n, n, n, n–1, так что порядок матриц Адамара равен 4(3n−1). Тюрин рассмотрел случаи n = 4, 6, 8, компьютерный поиск n = 10, ... , 34 (Jennifer, Koukouvinos, both Yangs, Kounias, Sotirakoglou). Альтернатива: Cooper and Wallis (1972).

Для того, чтобы не заниматься полным перебором, из ограничений на вид последовательностей извлекается часть их предположительных элементов, что и дало нужный результат Хади с соавторами для n = 36 (матрица 428-го порядка). Из ограничений используется то, что автокорреляционная функция первой базовой последовательности апериодическая, т.е. имеет протяженный нулевой хвост, кроме того, подправляемые претендентные фрагменты кода генерируются по корням из –1 (дань дальнего родства разложениям функций по базису Фурье).

ТАБЛИЦА


ПРОЦЕДУРА ПОИСКА


ЧЕТЫРЕ КВАТЕРНИОНА МАТРИЦЫ ГЕТХАЛЬСА-ЗЕЙДЕЛЯ


Из сумм кватернионов T1, T2, T3, T4 состоят четыре блока A, B, C, D матрицы Гетхальса-Зейделя, слагающие матрицу Адамара H44. Синие элементы матричных портретов – это нули.




ПРИМЕР АППРОКСИМАЦИИ МАТРИЦАМИ МЕРСЕННА


Массив Гетхальса-Зейделя может использоваться для вычисления аппроксимаций матриц Адамара четверкой матриц Мерсенна A, B, C, D, коэффициенты B, C, D сведены к {1,–1}. Очевидно, этот способ годится также для варьируемой четырехуровневой аппроксимации матриц Адамара. Возникет также чисто теоретический вопрос у существовании для матриц Мерсенна комплиментарных матриц, способных порождать матрицы Адамара. Для малых порядков такие матрицы находятся итерациями оптимизации детерминанта.


КОМПЛИМЕНТАРНАЯ ПАРА ДЛЯ МАТРИЦЫ МЕРСЕННА




Матрица Мерсенна M7 и комплиментарная ей матрица


Литература

Goethals, J.M., and Seidel, J.J. (1967), Orthogonal matrices with zero diagonal. Canadian Journal of Mathematics, vol. 19, pp. 1001–1010.

ТЮРИН | ГОЛЕЙ | КУКУВИНОС и Ко | БАЗОВЫЕ | ХАДИ

Rambler's Top100