EQUIVALENCE CLASSES

ДЕФЕКТ СИММЕТРИИ МАТРИЦЫ


© Nickolay A. Balonin,Dragomir Z. Djokovic 10.01.2015

MATRICES H16 | MATRICES H20 | MATRICES H32 | MATRICES H40



Круговая диаграмма количества классов эквивалентности orders 2, 4, 8, 10, 16, 20


PERIODIC GOLAY PAIRS (A,B)




Классы вложенные



Dragomir has done the classification of PerGol of different lengths. Length 2 and 4, only 1 equivalence class. Length 8, 2 equivalence classes. Length 10, only 1 equivalence class. Length 16, 11 equivalence classes. Length 20, there are 34 equivalence classes. Only two of the classes contain pairs with symmetry (8,8). There is no pair having at lest one of the sequences with symmetry >8. For v=26 there are 53 classes and for v=32 there are 838 classes. Length 34, there are 256 equivalence classes. Only 5 of them have a periodic Golay pair with Hamming distance 2. Length 40, there are 9301 equivalence classes.


INDEX OF SYMMETRY



Matrix H80 with minimal distance 1


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 Hamming index HIS: the number of integers j in {1,2,...,[v/2]} such that A[1,j]=A[j,1]. We will use a Hamming distance to characterise the symmetruc structure: difference between v/2 and number HIS of symmetric situated entries.

PerGol v=74: p=37=1+36, x=1, y=6: r=px=36, r=py=31. Let us note: p=v/2=r+s–λ=37, so it has parameters (74; 36,31; 30). It has subsequences J = {1,4,6,7,9,12,22,23,28,29,34,42}, K = {1,2,4,6,9,12,17,21,22,37,55} that being taken with multipliers {1,47,63} mod 74 give sequences A,B. This and other examples are gathered below.

PHENOMENON





Matrices H32 and A'A


The phenomenon: some SDSs for two periodic Golay pairs [A,B]=[[0,1,2,3,6,7,10,12,14],[0,1,4,5,7,10,12]]; and [C,D]=[[2,3,4,5,7,9,13,16,17],[1,5,6,9,11,12,14]] lead to corresponding binary sequences (which we denote by the same letters) A and C have the same periodic autocorrelation function: A and C have the same periodic autocorrelation function (upper string of A'A and C'C): [20,0,0,–4,0,–4,0,0,0,0,0,0,0,0,0,–4,0,–4,0,0], and B and D also the same periodic autocorrelation function: [20,0,0,4,0,4,0,0,0,0,0,0,0,0,0,4,0,4,0,0]. However, we can easily verify that A and C are NOT equivalent (under rotations and flips) and B and D also are NOT equivalent. This makes the computation tricky.

MAXIMUM SYMMETRY MATRIX



Matrices H40 with index symmetry 8,8


When v=20, in addition to Nick's example: A={0,4,6,7,9,12,13,14,16},B={2,7,8,9,10,13,18} with symmetry (8,8), there is one more equivalence class which contains such a pair. This other pair is: A={0,4,6,7,8,9,13,14,16},B={2,7,9,10,12,13,18}.



Matrices H40 with index symmetry 5,5


The following periodic Golay pair (for v=20) A={0,1,2,3,6,9,11,13,17},B={4,5,6,9,11,12,16} has the symmetry type (5,5) and this is true for ALL pairs in its equivalence class. This is a unique class with this property.

MATRICES ORDER 64




Matrices H64: IS=10,7; DIS=2,2



Matrices H64: IS=9,12; DIS=3,1

MATRICES ORDER 68



Matrices H68: IS=12,6; DIS=2,5 and IS=7,7; DIS=3,3



There was checking the relationship between Golay pairs and PerGol pairs. For lengths 2, 4, 8, 10 all equivalence classes of PerGol have a representative which is a Golay pair. In that sense, there is nothing new in these lengths. There are 8 equivalence classes of Golay pairs of length 8, but as periodic Golay pairs there are only 2 equivalence classes. In fact 7 of the Golay equiv. classes are contained in a single PerGol class. For length 16 there are 36 equiv. classes of Golay, but they give only 11 equiv classes of PerGol.

1. Dragomir Z. Djokovic, Equivalence classes and representatives of Golay sequences, Discrete Mathematics 189 (1998) pp. 79-93 (PDF).
2. 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

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


Rambler's Top100