TWO CIRCULANT HADAMARD MATRICES



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

Hadamard matrix catalogue and on-line algorithms




Matrices H68, algorithm has found

PAF of 100



GOLAY SEQUENCES


Основания бициклов порядков 2, 20, 52 дают три базовые семейства Марка Голея кратных двум порядков.

Существует много орнаментов ортогональных матриц. Моноцикл, бицикл, трицикл (Пропус), тетрацикл, многоциклические матрицы. Видимое противоречие в том, что для матриц порядка 4p2, p=3, 7, 11, .. минимум сложности – Пропус, трехцикл, тогда как SDS указывает на бицикл (дихотомию). Выход в том, что многоциклические матрицы, будучи не бициклами, дихотомичны. Их узор содержит много блоков, не два, но разваливается на два конгломерата, делится на два. По вертикали и горизонтали. SDS указывает параметры этих сложных блоков. Коме того, дихотомия разрешима тривиальным бициклом при увеличении размера матрицы более чем в p раз, Арасу и Янг толкуют, что коэффициент увеличения должен быть не меньшим p и взаимно простым с p, не иметь общих делителей.

Представление ортогональных массивов (матриц Адамара) блочными матрицами является иллюстрацией теоремы Эйлера-Ферма для чисел p=n/4=x2+y2 (буквальная визуализация представления матрицы двумя квадратами).

В отличие от циклических матриц, для описания которых годится SBIBD(n,k,λ), бициклы описываются SDS(n=2p;k1,k2;λ) – "парным" дифференциальным набором. За основу параметров SDS берутся расчеты количеств для тех элементы (1 или –1), которых меньше, λ – параметр (число сходных элементов в двух соседних строках). Суммы r=λ+x, s=λ+y описывают число 1 или –1 матриц бицикла (проверьте, по картинкам), при n/4=x+y+λ.



Бициклические матрицы порядков n=20 и 52: p=5 и 13


Параметры SDS связаны соотношением λ(v–1)=k1(k1–1)+k2(k2–1), где k1, k2 – число элементов одного знака пары бинарных векторов размера v, задающих бицик, а λ – общее число попарно совпадающих (пересекающихся) элементов первой и второй строк бицикла. Выбором переменных, оно сводится к уравнению круга, разрешимого в целых числах, и сказывается на уравнении для уровней, разрешимого в вещественных и иррациональных числах.

Для p=n/4=1 (mod 4) иллюстрация работает без осложнений. Для простого числа p=1 (mod 4) иллюстративным является бицикл размера 4p (например, p=5=4+1, H20). То же самое касается степеней, для четной степени 2 простого числа p=1 (mod 4) иллюстративным является бицикл 4p2. Например, p2=25, есть регулярная матрица H100.

Для простого числа p=3 (mod 4) бицикла 4p нет, число не разложимо на сумму двух квадратов. Для четной степени 2 простого числа p=3 (mod 4) иллюстративным является бицикл размера, заметно большего 4p2. Некоторое противоречие состоит в том, что SDS(n=4p2; r,s; λ) существует, но соответствующего ему бицикла нет. Матрица Пропус 36, p=9=3×3, она A, B, C-трициклическая. Версии орнаментов учитывают и иные разложения порядка, например, для 36=1+5×7.

REGULAR HADAMARD PROPUS-CONSTRUCTION


P=
A
 B=С 
 C=B 
D
C
 –D 
 –A 
B
B
 –A 
D
 –C 
D
C
 –B 
 –A 




Propus three-cycle H36 and symmetric H for 36=1+5×7


Противоречие снимается тем, что орнаменты регулярных матриц (в частности, матриц Буша) дихотомичны. Помимо трициклов размера 36 есть легко делимые на два по вертикали и горизонали сложные субблоки с параметрами, отвечающими SDS. Например, для n=36, p2=n/4=9=32+02, при λ=6 имеем r=λ+x=9, s=λ+y=6. Эти параметры блоков размера 18×18 видны на рисунке.



Регулярная матрица порядка 36 (Jennifer) с блоками {18,9,6,6} и матрица 144


Помимо дихотомичных регулярных матриц Адамара типа Буша (Bush type), которых известно всего три порядков 4p2=36, 100, не известен 196, 324, в рассмотрение можно ввести регулярные матрицы с каймой. Они легко строятся для 4p2=36, 100, 196, 324 и т.п. Для порядка 36 параметры λ=6, r=λ+x=9, s=λ+y=6 отвечают квадратному блоку A и прямоугольному B !


Кроме того, многоклеточное сооружение "рассасывается" до бицикла при увеличении размера. Коэффициент увеличения, взаимно простой с p, должен превышать p (Арасу, Янг [1]). Для p=3 увеличение 3 не работает (бицикла 108 нет), нужен коэффициент 4. Например, p=3, 4p2=36, 4>3, бицикл 4*36=144; p=7, 4p2=4*49=196, 8>7, бицикл 8*196=1568 !

Аналогичные упрощения структуры наблюдаются при переходе от сложных по форме матриц Белевича, например, типа Матона порядка 46, к относительно просто выглядящей четырехблочной матрице Адамара удвоенного порядка 92.

Иллюстрация имеет значение для предсказания факта существования матриц, в частности, бициклов. Так, пока не найдена, но должна существовать такая бициклическая матрица порядка 212, поскольку p=53 = 1 (mod 4). Матрица – сложнее числа в том смысле, что при знании ее параметров (числа 1 или –1), нам еще нужно найти сам узор – конкретную реализацию. Узор матрицы, это застывшая визуализация алгоритма разложения, то же самое, что и костяшки счет, иллюстрирующих суммирование.

ПРЕДСКАЗУЕМЫЕ ПОРЯДКИ БИЦИКЛОВ




Бициклы, в свою очередь, распадаются на периодические и апериодические, по типу автокорелляционной функции. Проще говоря, по возможности использовать их последовательности как ординарные пары Голея для умножения. Апериодические имеют длину, отличную от 3 (mod 4). Периодические приложимы шире, но их размер для версий 3 (mod 4) нуждается в расширении по отношению к 2pt, t – четное, в u раз, (p,u) = 1, u≥2p^t/2.

Theorem 1 (Eliahou-Kervaire-Saffari [1]) A Golay number is not divisible by any prime p≡3 (mod 4).
Theorem 2 (Arasu-Xiang [2, Corollary 3.6]) If v=ptu>1 is a periodic Golay number, p≡3(mod 4) is a prime number, and (p,u) = 1 then u≥2p^t/2.

Since v is a sum of two squares, the exponent t is an even integer. By applying this theorem to the integers in the range 1, 2, . . . , 500, we deduce that the numbers 18, 36, 98, 162, 242, 324, 392, 484, 490 are not periodic Golay although each of them is even and a sum of two squares.

[1] S. Eliahou, M. Kervaire, B. Saffari, A new restriction on the lengths of Golay complementary sequences. J. Combin. Theory A 55 (1990), 49–59.
[2] K. T. Arasu, Q. Xiang, On the existence of periodic complementary binary sequences. Des. Codes Cryptogr. 2 (1992), no. 3, 257-262


Cемейство матриц Сильвестра n=2k=2, 4, 8, 16, 32, 64, .. имеет чередующиеся SDS* с k1<k2, p=k2 и k1=k2, p=k2+2k–2: (2;0,0;0), (4;0,1;0)*, (16;2,4;2)*, (32;6,6;4), (64;12,16;12)*, (128;28,28;8), ... орбиты с t=5 отвечает симметричным решениям, более общее t=3 – асимметричным. Следующие два семейства, это семейства, порожденные еще двумя парами Голея: (20;3,4;2), (40;7,9;6), (80;16,18;14), .. и (52;10,11;8), ... И, наконец, начиная с порядка 68 ((68;13,16;12) впервые найдена Драгомиром), далее 100 и т.п., идет семейство периодических пар Голея (PerGols).

Порядки бициклов n=4, 8, 16, 20, 32, 40, 52, 64, 68, 80, 100, 104, 116, 128, 136, 144, 148, 160, 164, 200, 212?, 244.. Пока не найдена, но должна существовать такая бициклическая матрица порядка 212, поскольку p=53=1 (mod 4) допускает разложение на квадраты. Матрица – сложнее числа в том смысле, что при знании ее параметров (числа 1 или –1), нам еще нужно найти сам узор – конкретную реализацию. Узор матрицы, это застывшая визуализация алгоритма разложения, то же самое, что и костяшки счет, иллюстрирующих суммирование.

Балонин Н. А., Сергеев М. Б. Матрицы Мерсенна и Адамара // Информационно-управляющие системы. 2016. № 1. С. 2–15.
Балонин Н. А., Джокович Д. Ж. Симметрия двуциклических матриц Адамара и периодические пары Голея. // Информационно-управляющие системы. 2015. № 3. С. 2–16.
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 (негациклические бициклы)
Dragomir Z. Djokovic, Ilias Kotsireas, Daniel Recoskie, and Joe Sawada Charm bracelets and their application to the construction of periodic Golay pairs. arXiv:1405.7328.
Dragomir Z. Djokovic, Cyclic (v; r, s; λ) difference families with two base blocks and v ≤ 50. Ann. Comb. 15 (2011), no. 2, 233–254.
Dragomir Z. Djokovic, Note on periodic complementary sets of binary sequences, Des. Codes, Cryptogr. 13 (1998), 251–256.


MATRICES H16 | MATRICES H20 | MATRICES H32 | MATRICES H40


DRAGOMIR'S SDS-LIBRARY

DIRECT SEARCH


Прямой поиск эффективен для матриц низких порядков, особенно, если он оптимизирован тестами на пригодность случайных последовательностей. Недостаток его состоит в том, что он не может свернуть к нужному решению, даже если нашел почти пригодную пару, что оправдывает применение оптимизационных процедур. Ниже проверяются суммы последовательностей и проверка ортогональности снабжена досрочным ее завершением по первой встреченной невязке. Первый проблемный порядок – 68.

При поиске бициклов порядка n последовательности a, b длины v=n/2 вычисляются впрок, также, как и произведения их на циклические матрицы Aa, Bb, где A=circ(a), B=circ(b). Для вычисления произведений вычислять циклические матрицы в явном виде не обязательно, причем проверка ортогональности Aa+Bb=[n,0,0,....]' востребует только часть z=(v+2)/2 компонент Aa, Bb. Количество отрицательных элементов строк k1, k2 задается заранее.

Метод оптимизации детерминанта

OPTIMIZATION PROCEDURE


Процедура ниже использует то свойство, что сжатие строчек a, b попарным суммированием соседних элементов дает взвешенную матрицу вдвое меньшего порядка с весом, отвечающим p=n/4 (Драгомир). Ее (взвешенную) и предполагается изначально искать, что уменьшает размерность задачи вдвое. Получается громоздко, практический выигрыш ниже сомнителен. Процедура имеет иллюстративное значение того, как разделить расчеты между компьютерами на самостоятельные этапы, если дойдет до настоятельной потребности ускорить поиск.

Ниже версии алгоритмов с предустановленными наперед индексами симметрии и с генерацией, во втором алгоритме, a, b динамической системой в поле GF(2). Оптимизатор сам по себе, не опирающийся на метод орбит, уступает по скорости вычисления матриц порядков 52, 64 составной процедуре с орбитами.

МЕТОД ОРБИТ



К сожалению, на 68 и 100 тривиальные подгруппы дают короткие орбиты, это бициклы хорошо скрытые. При том, негациклические версии тех же матриц находятся быстро и хлопот не составляют. Гроссет бициклов больших порядков найден Драгомиром в совместной работе 2012 года (148, 164, 244, и т.п.), см. абзацами ниже при осуждении PerGol-пар.

Ускорение алгоритма оптимизатором детерминанта (используется экстремальное свойство искомого решения): недостроенные орбиты выводят оптимизатор на удачное начальное состояние. Матрицу 68 хорошо настроенный оптимизатор ищет в лоб примерно за час (при неудаче, до суток). Выбор орбиты неоднозначен, иногда (матрицы порядков 40, 64) ее выгодно вычислять по модулю n, а не v.

Например, для n=52 псевдоорбита x=[1,2], умножаем ее по модулю v=52/2=26 на случайные числа <n/2; для n=68 орбита [1,21], умножаем ее по модулю v=68/2=34 на случайные числа <n/2: 0*{1,21}={0,0}={0}, 6*{1,21}={6,24} и тому подобное.

Строки a, b – адреса –1 в строках a, b бицикла, игра чисел.

Так как случайных чисел 0, 6, 7, 15, 18, 23, 30, 31 заметно меньше 34, сгенерить {0}{6,24}{7,11}{15,9}{18,4}{23,7}{30,18}{31,5} теоретически легче, чем строку размером 34 в лоб, но на практике быстрее решение дала сцепка метода орбит и корректора в виде оптимизатора детерминанта (использует орбиты как начальное условие). Сцепка нашла матрицу 68 по ошибочной последовательности случайных чисел. Потом, взяв верно найденную вторую строку, компьютер нашел уже верную первую строку. Вывод такой, что для коротких орбит (особенно) сцепка работает заметно быстрее, так как не ждет у моря погоды. Ускорить процессы можно учетом дополнительной информации о симметриях решения, PSD-тест последовательностей, и т.п.

Ниже в последнем примере орбиты {1,21} кривенький генератор дал, как видно, ошибочное 12×{1,21}={12,14!}, значения 14 нет в коде, ошибку и аналогичные ошибки исправил акселератор в процессе оптимизации.

NEGACIRCULANT VERSION

NICK'S-DRAGOMIR'S SYMMETRY INDEXES ESTIMATION


The possible matrices with both symmetric A=B are matrices of order ≤8. There are no starting two circulant matrices of orders 12, 24, 28, 36, 44.. (the resolvence x2+y2=v/2, v – order of A, B, dictates the existence of two-circulant matrices). Matrix H64 demonstrates partially equal and partially symmetric A, B.



H16 IS=4,4 and H20 IS=4,3



Two versions of symmetric H32, index of symmetry 8,8



Dragomir's H40, index of symmetry 8,8 and 8,7



Nick's H52, index of symmetry 9,8 and 7,7



Nick's H64, index of symmetry 11,11 and 10,10



Dragomir's H68 IS=15,5 and Nick's H80 IS=8,5



Dragomir's H100, SDS(50;22,21;18) IS=8,6 and 7,7



Dragomir's H100, SDS(50;22,21;18) IS=7,6 and 5,5



Dragomir's two circulant H136 (16,8) and H144 (7,13)




ALGORITHMS ON LINE



SOME STARTING MATRICES



EQUIVALENCE CLASSES



DRAGOMIR'S PROPUSI



HADAMARD MATRICES H16



HADAMARD MATRICES H20



HADAMARD MATRICES H32



HADAMARD MATRICES H40

RYSER MATRIX

The Ryser's (Herbert John Ryser) conjecture (see [1], page 134): There are no circulant Hadamard matrices of order n > 4. The fact (Newman, Brualdi [2], look PDF | PDF2): there are no symmetric circulant Hadamard matrices of size n>4. It is followed from the transposed form of a circulant matrix with positive entries and parameters of Hadamard matrix cannot be symmetry.

So now we are interested in Hadamard matrices formed using two circulant or circulant and back-circulant blocks

A
B
 BT 
 –AT 
A
 BR 
 BR 
 –A 


where R – reversed identity matrix (flip). The first example gives the circulant diagonal matrix called Ryser's 4×4 and its Sylvester's double: H8.

INDEX OF SYMMETRY


Nick's conjecture: the Ryser's bound for the symmetric two-circulant Hadamard matrices is 32. There are no symmetric circulant Hadamard matrices of order n > 32 (max v = 42, v – size of A, B).

There are at least two possible definitions of index of symmetry IS: the largest d (≤v/2) such that A[1,j]=A[j,1] for j=1,2,...,d and the number of integers j in {1,2,...,[v/2]} such that A[1,j]=A[j,1].

We are both using the definition 1). However the definition 2) is also meaningful (and useful) and also has a nice property that it is invariant under multiplication of both sequences by k mod v (k relatively prime to v). Besides we can use a Hamming distance to symmetruc structure: difference between v and number of symmetric situated entries.



Symmetric H8 and partially symmetric H64, index of symmetry 10, 10


Jennifer Seberry, Centre for Computer Security Research, University of Wollongong, NSW, has been working with Nickolay Balonin, Saint Petersburg State University of Aerospace Instrumentation, Russia, on visualisation of Hadamard and other similar matrices CMSA.

Index of symmetry – the number of entries ≤v/2, equal in the first row and column of A, matrix H32 is the last with the bound v/2=8 (H4, H8, H16 look also below, in catalogue). The resolvence x2+y2=v/2, v – order of A, B, dictate the existence of two-circulant matrices; r=v/2–x, s=v/2–y – numbers of 1s (–1s) inside blocks; λ=v/2–xy is parameter of SDS(v;r,s;λ) [3–7]. Procedure uses subroutine giving a fixed numbers r and s of –1 of partial symmetry code.

The grain symmetry has two important classes: "odd" {a, ±1, flip(a)..} and "even" {a, flip(a).. } types. We use "odd" type, it allows to note a diagonal entry. We note especially inversed {a, ±1, flip(–a)..} and "even" {a, flip(–a).. } types, these usual for two border solutions: A has "odd" symmetry, B has "even" inversed symmetry and it is a main difference between two circulant and two border two circulant matrics (C74 hard to find or absent? while two circulant version we have).

The non symmetric two-circulant Hadamard matrices can be built by periodic Golay pairs [3–6]. Golay pair [also] is also a periodic Golay pair (PerGol).

Williamson matrices catalogue up to orders v=59, n=4v, mentions the first (found by Dragomir) problem order v=35. These A, B, C, D matrices have non symmetric placement of B and C, symmetric form with symmetric A and B=C is good Propus resolved by Dragomir for case v=35.

ORDERS


Theorem 1 (Fermat-Euler). Prime p=1 mod 4 is presented as sum of two squares p=x2+y2.

Seems, PerGol exists for all cases p=v/2=1 mod 4, does not exists for p=v/2=3 mod 4, but v/2 can be proportional, for example, to square. Integer having multiplier 3 mod 4 can be presented if it has an even power: v=72, p=36=9x4.



All numbers in the range 1, 2, . . . , 300 for which the question whether they are periodic Golay numbers remains open: 90, 106, 130, 146, 170, 178, 180, 194, 212, 218, 234, 250, 274, 290, 292, 298 [2]. Let us note, we use x, y as numbers r=px, s=py of 1 or –1 in (A,B). So existence of solution with v=2p=106 follows from Fermat-Euler theorem – if we take two circulant matrices as an illustration. For v=106: p=53=49+4, x=7, y=2, r=53–7=46, s=53–2=51. More complicated case: v=90 (p=3x3x5), parameters p=45=36+9, x=6, y=3, r=45–6=39, s=45–3=42. Number p=v/2 is used also in definition of index of symmetry.


CLASSES OF EQUIVALENCE



Near symmetry, order 64


The definition of equivalence, in addition to rotations and flips, uses multiplication by k (which is relatively prime to v), modulo v and also the "alternation" by which one mean to change the sign of each second term in both A and B (all these operations preserve the set of periodic Golay pairs of fixed even length v). However, in general the symmetry index is not preserved under these operations.

PERIODIC GOLAY PAIRS


The first periodic Golay pair whose length, 34, is not a Golay number has been found in 1998 by Dragomir [3]. (In fact two non-equivalent such pairs were found.) Periodic Golay pairs of length 50 have been found by Djokovic [4] and Kotsireas and Koukouvinos [5]. Four pictures H100 built by SDS (50;22,21;18) taken from the paper of Djokovic and Kotsireas [6].

Since all Golay numbers in the range 1, 2, . . . , 100 are known, we deduce that 34, 50, 58, 68, 72, 74, 82 are the only periodic Golay numbers for which we are presently sure that they are not Golay numbers. The parameters for the periodic Golay pairs of length 50 (one of them) for regular matrix are (50;25,20;20). Thus, one of the circulant blocks has 0 row sum. Consequently we get regular H100 with s=10. This SDS is given in Dragomir's paper in Annals of Comb (2011). There is another example in a paper of Kotsireas and Koukouvinos.

A year ago there was written an article [7] with 31 non-equivalent periodic Golay pairs of length 68. By checking their index of symmetry, Dragomir found one with index 10. Among the 8 periodic Golay pairs, paper [6], there are 8 non-equivalent periodic Golay pairs of length 72. Here the List from Dragomir: first parameter v – the length of the sequences. Second – the symmetry index of the first sequence A. Third – the symmetry index of the second sequence B. Fourth – this is just the number of the solution in Dragomir's list of the SDS. For v=68 and v=72 the lists are given in the two papers posted on arXiv.

МАТРИЦЫ С ОРБИТАМИ 148, 164, 244, 328


1. H. J. Ryser, Combinatorial mathematics. The Carus Mathematical Monographs, No. 14, Published by The Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York 1963.
2. R.A. Brualdi, A note on multipliers of difference sets, J. Res. Nat. Bur. Standards Sect. Vol. 69B (1965), pp. 87–89 (October 29, 1964). Journal of Research of the National Bureau of Standards (Vol. 69B) PDF | PDF2
3. Dragomir Z. Djokovic, Note on periodic complementary sets of binary sequences, Des. Codes, Cryptogr. 13 (1998), 251–256.
4. Dragomir Z. Djokovic, Cyclic (v; r, s; λ) difference families with two base blocks and v ≤ 50. Ann. Comb. 15 (2011), no. 2, 233–254.
5. I. S. Kotsireas, C. Koukouvinos, Periodic complementary binary sequences of length 50. Int. J. Appl. Math. 21 (2008), 509–514.
6. Dragomir Z. Djokovic, I. S. Kotsireas, Some new periodic Golay pairs. arXiv:1310.5773v2 [math.CO] 27 Aug 2014 AND arXiv:1409.5969v2 [math.CO] 27 Jan 2015
7. Dragomir Z. Djokovic, Ilias Kotsireas, Daniel Recoskie, and Joe Sawada, Charm bracelets and their application to the construction of periodic Golay pairs. arXiv:1405.7328. PDF

RYSER HERBERT JOHN AND MARSHAL HALL IN RUSSIAN


Райзер Г. Дж. Комбинаторная математика. / Пер. с англ. Пер. Рыбникова К.А. –М.: Мир, 1965. 154 с. [PDF]

Холл М. Комбинаторика. / Пер. с англ. под ред. Гельфонда А.О., Тараканова В.Е. –М.: Мир, 1970. 448 с. [djvu]

Холл М. Комбинаторика. / Пер. с англ. под ред. Гельфонда А.О., Тараканова В.Е. –М.: Мир, 1970. 448 с. [pdf]

SYMMETRY PROPERTY


Балонин Н. А., Джокович Д. Ж. Симметрия двуциклических матриц Адамара и периодические пары Голея. // Информационно-управляющие системы. 2015. № 3. С. 2–16.

WILLIAMSON MATRICES | SKEW HADAMARD MATRICES
TWO-CIRCULANT C-MATRICES


OLD PROCEDURES



Rambler's Top100