FOUR-BLOCK HADAMARD MATRICES



© Nickolay A. Balonin, Dragomir Z. Djokovic, 22.04.2015

Hadamard-type matrix catalogue and on-line algorithms


WILLIAMSON MATRICES

W=
A
B
C
D
 –B 
A
 –D 
C
 –C 
D
A
 –B 
 –D 
 –C 
B
A
A=
 –1 
1
1
1
1
 –1 
1
1
1
1
 –1 
1
1
1
1
 –1 


Массив Вильямсона и циклическая матрица 4-го порядка


Вильямсон расширил практику блочного представления матриц Адамара, характерную для конструкций Пэли, увеличив число блоков по горизонтали и по вертикали вдвое, и назвав это массивом, блоки (матрицы Вильямсона) представлены попарно-коммутативными симметрическими подматрицами порядка w с элементами ±1, удовлетворяющими условию ортогональности матрицы в целом A2+B2+C2+D2=4ωI.

Массив Вильямсона W – по сути своей – пара бициклических (бинегациклических) конференц матриц с замещенными диагоналями. И то, и то обходится симметричными клетками, что упрощает внешний вид массива. Конструкция несколько искусственная, уже на порядке 35 матриц Вильямсона, клеток A, B, C, D, полный компьютерный перебор подтвердил отсутствие решения (Dragomir Djokovic). Между тем, оно существует в виде массива Гетхальса-Зейделя (Goethals and Seidel) для типа симметрии, общего с 1N.

GALOIS FIELD PROCEDURE



Williamson array, orders 28, and weighing matrix W(28,26)


В простейшем случае A=1, B=1, C=1, D=1, массив Вильямсона дает адамарову матрицу четвертого порядка.

Циклическая матрица Адамара известна для n=1, n=4 (Circulant Hadamard Matrices R. Stanley), порядки 2 и кратные 8 исключены. Поиск элементов блоков перебором облегчается, если предположить, что они циклические. Таким способом строится матрица 92 порядка (Baumert, Golomb и Hall, 1962): матрица первой сотни n<100, недостижимая в рамках конструкции Пэли. Позднее Baumert нашел этим методом матрицу 116-го порядка. Доказано существование матриц порядков 4w для всех w<60 (2007 г.), w=9s и w=(q+1)/2, q – простое целое из чисел, равных –l (mod 4). Если n/2–1 = 1 mod 4, то существует решение: A и B отличаются только основной диагональю и C=D. Баумерт и Холл декларировали блочный массив порядка 12 (по блокам), где каждая строка содержит по три вхождения четырех матриц типа Вильямсона: Baumert Hall Arraw, 1964. К настоящему времени неизвестны, например, матрицы порядков 668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, 1964.

МАССИВ С НЕСИММЕТРИЧНЫМИ КЛЕТКАМИ

W=
A
B
C
D
 –B 
A
 –D 
C
 –C 
D
A
 –B 
 –D 
 –C 
B
A
H=
A
B
C
D
 –B 
A
 –D 
C
 CT 
 –DT 
 –AT 
 BT 
 DT 
 CT 
 –BT 
 –AT 


Так как не все клетки несимметричны, существует две находимые одним и тем же алгоритмом разновидности массива (симметричный и кососомметричный).



Симметричная и асимметричная матрицы HM140, c=flip(d)


МАССИВ ГЕТХАЛЬСА-ЗЕЙДЕЛЯ

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




Два типа симметрии негациклических массивов Гетхальса-Зейделя, n=28


В полях Галуа реализуемы осцилляторы, дающие, как минимум, два типа симметрии 1N (аналог симметрии синуса, кососимметричная A) и 2N (аналог симметрии косинуса, симметричная A). Фиксация симметрии A нежесткая, кроме того, есть еще три клетки. Тип генератора ниже можно выбрать.

GOETHAL SEIDEL ARRAY: GALOIS FIELD PROCEDURE

FOUR-BLOCK TOEPLITZ MATRICES

W=
A
B
C
D
 –B 
A
 –D 
C
 –C 
D
A
 –B 
 –D 
 –C 
B
A
H=
A
B
C
D
 B 
A
 D 
C
 CT 
 DT 
 –AT 
 –BT 
 DT 
 CT 
 –BT 
 –AT 


Массив Вильямсона и новый массив с B, D (циклически сдвинуты)


В том случае, когда блоки – теплицевы матрицы, преемственность с двуциклической их конструкцией сохраняет массив, в котором инверсия –B, –D заменена соответствующим типу клетки циклическим или нега-циклическим сдвигом B, D. При поиске двуциклических матриц используют сопряженные формы [A B;–BT AT] ([A B;–B A], при симметрии) и [A B;BT –AT], эта практика дает нижние блоки формы Nega-4.

Массив теплицевых матриц Nega-4 позволяет попарным совмещением столбцов и строк блоков A, B и C, D переходить к двуциклическим ортогональным матрицам. Преобразование от Nega-4 к Nega-2 поясним примером с нега-циклическими матрицами. Обратим внимание, что только часть блоков формы Nega-4 симметричны и симметрия зависит от порядка матрицы.



Negacyclic 4- and 2-array for order 28, Hadamard matrix



Negacyclic 4- and 2-array for order 28, W(28,26)



Возможные порядки 2- и 4- нега-циклических матриц обширны (в библиотеке есть, например, матрица порядка 32), требование симметрии всех блоков не всегда целесообразно, ведет к усечению возможных решений. Симметрией блоков можно и нужно уметь пользоваться, это путь ведет (не всегда, как видно) к сокращенным объемам вычислений. Отметим отсутствие матриц порядков 16 для Nega1 и 12 для Nega4 (некритичныx для Nega2). Двуциклической матрицы порядка 92 не существует. В отношении нега-циклических конструкций это не так.

БИБЛИОТЕКА NEGA-4 МАТРИЦ


THE WILLIAMSON-TYPE ARRAY

W=
A
B
C
D
 –B 
A
 –D 
C
 –C 
D
A
 –B 
 –D 
 –C 
B
A
H=
A
B
C
D
 –BT 
 AT 
 –DT 
 CT 
 CT 
 –D 
 –AT 
 –B 
 DT 
C
 BT 
A


Williamson array and Williamson-type array


Two matrices [A B; –B' A'], [C D; –D' C'], inserted into the same type array, depend on 4 negacyclic matrices A, B, C, D. For n=8k array with [A B; –B' A], [C D; –D' C] and the same type matrix, to insert, gives better results. Both these Williamson-type matrices equivalent to two negacyclic matrix for some sets of symmetric codes.

ТАБЛИЦА 2007: WILLAMSON MATRICES UP TO ORDER 59
ТЮРИН | СТАТЬЯ 1981 | СТАТЬЯ 2002 | ЭРИК ТРЕССЛЕР

Rambler's Top100