TOEPLITZ MATRICES
1-,2- AND 4-TOEPLITZ ORTHOGONAL MATRIСES


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

Hadamard-type matrix catalogue and on-line algorithms


Balonin N. A., Djocovich D. Z. Negaperiodic Golay pairs and Hadamard matrices. // Informatsionno-upravliaiushchie sistemy [Information and Control Systems], 2015, no. 5, pp. 2–17. doi:10.15217/issn1684-8853.2015.5.2

MENU OF CATALOGUES

NUMERICAL ALGORITHMS

    

GALOIS FIELD ALGORITHMS

PALEY MATRICES

    

WEIGHING MATRICES

GOETHAL-SEIDEL MATRICES

    

WILLAMSON MATRICES



АЛГОРИТМЫ РАСЧЕТА НЕГАЦИКЛИЧЕСКИХ МАТРИЦ В GF(2s)


Расчет в конечном поле GF(2s). Компоненты вектора состояния определены в GF(2), s – порядок динамической системы: порядок характеристического полинома фробениусовой матрицы A модели пространства состояний xk=Axk–1, A=[0 1 0 ..0; 0 0 1.. 0; .....; a0, a1, ... as–1].

В данном случае, для формирования бинегациклической матрицы Адамара элементы бинарных последовательностей a, b рассматриваются как выходы ak=Cxk, bk=Cxk, C=[0, 0, ..., 0, 1], компактных, в сравнении с ними, динамических систем. На опорных порядках n = 2s=1, 2, 4, 8, 16, 32, .. резонанс (ортогональность) достигается гарантированно применением одной и тоже системы для обоих плеч матрицы расчетом A и начального условия x0, но для матриц циклических и с двойной каймой.

В более общем случает необходимо назначать парные отличные между собой начальные условия или даже парные значения матрицы A, отвечающих генерации отличающихся между собой последовательностей a, b.

Отклонение матрицы Адамара уходом ли ее структуры (например, отказ от двойной каймы) или изменением порядка n от опорных значений 1, 2, 4, 8, 16, 32, .. приводит к необходимости повышать порядок s динамической системы, причем близость желаемого значения n к опорному порядку (из указанных) не означает близости к опорным значениям выбираемого s. Труднее всего вместить близкое, а не далекое (то есть, иногда s берется для порядков заметно больших).



Hadamard matrix H32 n=32, s=5 and H28 n=n–4=28, s=s+2=7 (!)


Много этим занимался физик акустик Манфред Шредер, он же предложил называть решения a, b для опорных порядков последовательностями Галуа. Матрица напоминает свисток (глиняная свистулька), с двумя отделениями. Свистулька ушла совсем на немного, от "идеальной" формы, но вот дуть в нее приходится "заковыристее". И все потому, что мы отказываемся от каймы и меняем форму с циклической на негациклическую.

АЛГОРИТМЫ РАСЧЕТА НЕГАЦИКЛИЧЕСКИХ МАТРИЦ В GF(p2)

Для начала, вспомним, как мы вычисляем матрицу Якобсталя (или Мерсенна), порядок 7. Берется цепочка чисел W={0,1,2,3,4,5,6} и вычисляется вторая цепочка U квадратов от них по модулю 7. Если число первой цепочки есть во второй цепочке, ставим 1, нет, ставим –1 (или –b) за исключением первого нейтрального элемента. У матриц Якобсталя ставим 0, у ортогональных матриц Мерсенна этот элемент переопределен в 1. Перед нами вырисовывается строка 0,1,1,–b,1,–b,–b циклической матрицы, ортогональной для Мерсеннов.


Элементы цепочек W и U отображены цветными полосками


В арифметике полей Галуа, возьмем для конкретности GF(p2), p=2v–1, v – половинный размер синтезируемой последовательности длины n, та же идея выглядит следующим образом. Берутся не число и его квадрат, а две соседние степени примитивного элемента x вида w=xL–1 и u=xL, т.е. заведомые "нечет" и "чет". Выбрав две точки опоры, путешествие ускоряем. Оба числа возводятся в степени W={w0, w1, w2, ..., , wn–1} и U={u0, u1, u2, ..., un/2–2}, экспоненты образуют элементы циклических подгрупп, второй цепочка примерно вдвое короче. В примере, с которого мы начинали, часть квадратов тоже совпадают между собой – конечное поле, оно тесное.



Две осциллирующие зависимости, аналоги W* и U


Для поля GF(p2) характерна арифметика, близкая к арифметике комплексных чисел. Степенные функции W и U ведут себя как синусоиды. Двумерные элементы-точки обоих можно весьма условно, конечно, отобразить осциллирующими кривыми на плоскости (выглядят кривые, на деле, более хаотично, разумеется). После предустановки "начальных условий", мы запускаем процесс из двух соседних точек, далее экспоненты "осциллируют", образуя наложения. Чем выше порядок задачи, тем ближе дискретная картинка к непрерывной.

Степень L=4v*) равна удвоенному размеру первой цепочки для приведения цепочек в "резонанс": нам важно, чтобы они не ходили рядом друг с другом вхолостую, а пересекались. Перед сравнением элементов цепочек первую еще "проецируют", берут не W, а степенную функцию (trace map) от нее W*=αW+(αW)p, α=xv. Коррекция, выводимая из условий ортогональности. Далее сравниваем W* и U. Если число первой цепочки есть во второй цепочке, ставим 1, нет, ставим –1 (за исключением первого элемента). Перед нами строка элементов 0,1,–1,1,–1, ..., теперь уже, ортогональной негациклической матрицы.

*) Показатель степени для "нечета" можно сократить вдвое или вчетверо w=x2v–1 или w=xv–1, на разрешимости задачи это не отразится. То же самое можно делать с "четом" (но, увеличивать u=x8v или u=x16v).



Циклическая 1C-матрица Q7 и негациклическая 1N-типа, порядка 12


Циклические 1C-матрицы Якобсталя или ортогональная Мерсенна Mn – моноциклы, нечетного порядка, и негациклическая 1N-матрица – тоже моноцикл, но четного. Отметим, что при проецировании можно менять значение α, если нам не нужна ортогональная матрица, например, когда это блок более крупной матрицы, которая ортогональна, но в целом. Наиболее доходчиво реализация алгоритма (его предложил Драгомир) выглядит в системе Visual MatLab. Интернет исполнение, впрочем, немногим сложнее и работает оперативнее, с листа.

VISUAL MATLAB

БИНЕГАЦИКЛИЧЕСКИЕ МАТРИЦЫ


Бицикл (при потребности) получается искусственно, разнесением нечетных и четных по порядку элементов (a, b) моноцикла. При этом появляется некоторая дополнительная "степень свободы" в назначении первого элемента, который можно теперь не переопределять в 0. Содержательная сторона расчета (комментируется тот же самый расчет, но с других позиций) состоит в том, что рассчитываются "шкала" U и положение пары "стрелок" W1, W2 (двух соседних элементов W*) – вращаемых возведением в степень гиперкомплексных чисел, элементов поля Галуа. Когда "стрелки" W1, W2 указывают деления "шкалы" U, ставим 1 (или –1) в двух отчетах: последовательностях (a, b), порождающих двунегациклическую матрицу 2N-типа. Другой метод состоит в том, что ищутся две матрицы A, B отдельно, варьируя (опять же, при потребности) множитель α (нам не нужны, в общем, два ортогональных блока).



Hadamard matrices 2N H12 and 1N H12



Реверсной сборкой мы видим матрицу Адамара 1N c зиппер-диагональю diag(–1,1,..), случай вовсе не исключительный, поскольку на 16-м порядке их будет три (особый порядок). Ровно таковы же и неразрешимые для С-матриц решения порядков 22, 34, и т.п. Естественно возникает вопрос, а почему бы их сразу не находить в таком виде? Зиппер-диагонали пока мало распространены.



1N-матрицы порядков 16, 22


МАТРИЦЫ В ЧЕТЫРЕ БЛОКА


Разделение четных и нечетных элементов можно продолжить и далее, переходя к 4N-матрице, сходной с массивом Вильямсона, но устроенной несколько проще ее. Преемственность с двуциклической конструкцией сохраняет массив*), в котором инверсия –B, –D заменена соответствующим типу клетки циклическим или нега-циклическим сдвигом B, D. Рабочая гипотеза состоит в том, что обе формы 2N и 4N обладают специфическими видами симметрии, которыми можно пользоваться, для ускорения вычислений их тогда, когда получить простое поле не получается, причем лидерство в симметриях переходит от одной формы к другой.

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 (негациклически сдвинуты)


Не стоит путать внешне похожие 4N массивы между собой. Дело в симметрии. Для конструкции Вильямсона она входит в противоречие с условием ортогональности массива на порядке 140. Для нового массива понятие симметрии отнесено к последовательностям, проблем с ним на отмеченном порядке не возникает. Однако если массив Вильямсона имел бы проблемы, но строго в противофазе с всегда разрешимыми относительно 2N моноциклами, то услуги нового массива могли и не потребоваться. Для порядка 47 (ситуация, когда моноцикл 188 отсутствует), судя по таблице от 2007 года, матриц Вильямсона таки нет.

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

ЛЮБИТ, НЕ ЛЮБИТ


Подведем некоторый итог. Теоретико-групповой подход (поля Галуа, мультипликативные группы) привлекает относительной легкостью формулировки решений некоторых достаточно запутанных проблем. Проблемные для построения массива Вильямсона порядка 140 матрицы, например, несложно найти, используя алгоритм поиска негациклических матриц 1N/2N в полях Галуа GF(p2). Отметим, что так как есть порядки, в принципе недоступные негациклическим матрицам 1N, начиная с 16-го (см. наш каталог), матрицы 2N могут быть производными от матриц 4N (что ценно, для порядка 92, например), включая преобразованные из массивов Вильямсона с их симметричными клетками, но не только от них. Последнее (симметрия) интересно в связи с обозначенными Драгомиром и Хади пробелами порядков 35, 47, 53, 59 у симметричных матриц типа Вильямсона, причем если для 35, 53 есть формы 1N (порядки Пэли), то для 47, 59 актуальна гипотеза о наличии симметричной матрицы 4N в форме, получаемой двойным разделением четных и нечетных строк и столбцов (это не массив Вильямсона).



Негациклические матрицы 4N (Вильямсона) и 2N порядка 92



Негациклические матрицы 1N (зиппер диагональ) и 2N порядка 140

TABLE 2007: WILLAMSON MATRICES UP TO ORDER 59

2N-ПРОЕКЦИИ СЛОЖНЫХ 4N-МАССИВОВ



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


С помощью пары и более моноциклов можно находить массивы Гетхальса-Зейделя. Проблем с ними не возникает, но и найти их можно, таким именно способом, не для всякого проблемного порядка.

ALGEBRAIC SUMS OF TWO SQUARES

a2+b2

a2+2b2

0
2
8
 18 
 32 
 50 
 72 
 98 
 128 
 162 
 200 
 242 
1
3
9
 19 
 33 
 51 
 73 
 99 
 129 
 163 
 201 
 243 
4
6
 12 
 22 
 36 
 54 
 76 
 102 
 132 
 166 
 204 
 246 
9
 11 
 17 
 27 
 41 
 59 
 81 
 107 
 137 
 171 
 209 
 251 
 16 
 18 
 24 
 34 
 48 
 66 
 88 
 114 
 144 
 178 
 216 
 258 
 25 
 27 
 33 
 43 
 57 
 75 
 97 
 123 
 153 
 187 
 225 
 267 
 36 
 38 
 44 
 54 
 68 
 86 
 108 
 134 
 164 
 198 
 236 
 278 
 49 
 51 
 57 
 67 
 81 
 99 
 121 
 147 
 177 
 211 
 249 
 291 
 64 
 66 
 72 
 82 
 96 
 114 
 136 
 162 
 192 
 226 
 264 
 306 
 81 
 83 
 89 
 99 
 113 
 131 
 153 
 179 
 209 
 243 
 281 
 323 
 100 
 102 
 108 
 118 
 132 
 150 
 172 
 198 
 228 
 262 
 300 
 342 
 121 
 123 
 129 
 139 
 153 
 171 
 193 
 219 
 249 
 283 
 321 
 363 


GALOIS FIELD PROCEDURE

GOLAY PAIRS MULTIPLIER

WEIHGHING MATRIX W(46,45)





Block-cyclic C46 and block-negacyclic C46

PAINTER C46


WEIHGHING MATRIX W(66,62.477118)



Weight=5(985+4sqrt(46))/81=62.477118.., W'*W=62.477118*I, a=1, b=0.864703, c=0




W(66,55.51505) and W(86,77.71217)


SKEW N2-TOEPLITZ MATRICES WITH B-SYMMETRY

Skew-type 4k-[A B; –B' A] matrices with a=[1 code ±1 flip(code)], b=[1 code ±flip(code) ±1] matrices, symbol * notes skew-matrix with a free b. Algorithms and all other matrices: here.



Hadamard matrices H8 and H12



Hadamard matrices H16 and H20



Hadamard matrices H24 and H28



Hadamard matrix H32



Hadamard matrices H40* and H44



Hadamard matrices H48 and H52*



Hadamard matrices H56* and H60



Hadamard matrices H64* and H68



Hadamard matrix H72



Hadamard matrices H80 and H84

HIDDEN SYMMETRIC N2-TOEPLITZ MATRICES ON 4-BLOCKS CODES


4k-[A B; B' –A'] block-matrices with A=A(a,b), B=B(c,d) N2-matrices bazed on the four permutated sequences a=[1 code –flip(code)], b=[code ±1 flip(code)], c=[1 code –flip(code)], d=[code ±1 flip(code)]; (a,b), (c,d) transformed to N1 due odd/even-rows permutations. Algorithms and all other matrices: here.



Hadamard matrices H12



Hadamard matrices H20



Hadamard matrices H28



Hadamard matrices H36



Hadamard matrices H44



Hadamard matrices H52



Hadamard matrices H60



Hadamard matrices H68



Hadamard matrices H76



Hadamard matrices H84



Hadamard matrices H92



Hadamard matrices H100 (H50 N1-multiplication)



VITOLD (NEGA-CYCLIC C-MATRICES) | JANKO (BLOCKS OF BUSH-TYPE HM)

Rambler's Top100