RYSER'S CONJECTURE



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

Hadamard matrix catalogue and on-line algorithms


RYSER MATRIX


The Ryser's conjecture (see [1], page 134): There are no circulant Hadamard matrices of order n > 4. 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. The non symmetric two-circulant Hadamard matrices can be built by complementary Golay sequences, [also].

The conjecture follows (nick, 2014): the Ryser's bound for the symmetric two-circulant Hadamard matrices is 32.

The fact (proved by Richard Brualdi [2]) that there are no symmetric circulant Hadamard matrices of size n>4. The conjecture above is an analog of that theorem. In total Dragomir tested milions random circulant A blocks against all symmetric B blocks and did not find any complementary pairs. This means that nick's conjecture (symmetric two-circulant matrices is finite family, maximal order 32) survived this test. However it was used only a tiny part of the entire sample space for circulant A blocks. Thus, this is not a strong evidence that conjecture is true.

The Bruck–Ryser–Chowla theorem. It states that if a (v, b, r, k, λ)-design exists with v = b (a symmetric block design), then:

– if v is even, then k – λ is a square;
– if v is odd, then the following Diophantine equation has a nontrivial solution:
x2 – (k – λ)y2 – (–1)(v–1)/2 λ z2 = 0.

In the special case of a symmetric design with λ = 1, that is, a projective plane, the theorem (which in this case is referred to as the Bruck–Ryser theorem) can be stated as follows: If a finite projective plane of order q exists and q is congruent to 1 or 2 (mod 4), then q must be the sum of two squares. Note that for a projective plane, the design parameters are v = b = q2 + q + 1, r = k = q + 1, λ = 1. Thus, v is always odd in this case.

The theorem, for example, rules out the existence of projective planes of orders 6 and 14 but allows the existence of planes of orders 10 and 12. Since a projective plane of order 10 has been shown not to exist using a combination of coding theory and large-scale computer search, the condition of the theorem is evidently not sufficient for the existence of a design. However, no stronger general non-existence criterion is known.

The existence of a symmetric (v, b, r, k, λ)-design is equivalent to the existence of a v × v incidence matrix R with elements 0 and 1 satisfying

RRT = (k – λ)I + λJ


where I is the v × v identity matrix and J is the v × v all-1 matrix. In essence, the Bruck–Ryser–Chowla theorem is a statement of the necessary conditions for the existence of a rational v × v matrix R satisfying this equation. In fact, the conditions stated in the Bruck–Ryser–Chowla theorem are not merely necessary, but also sufficient for the existence of such a rational matrix R.

They can be derived from the Hasse–Minkowski theorem on the rational equivalence of quadratic forms.

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


RYZER HERBERT JOHN AND MARSHAL HALL IN RUSSIAN


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

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

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

TWO CIRCULAT RYSER MATRICES



Two two-circulant Ryser matrices H2 and H4



Two-circulant Ryser matrices H8



Two-circulant Ryser matrices H16 and H32



Four-circulant matrices H64 (French Parket)


The symmetric matrices are the result of computer search. The two-circulant ones were found to the 32 order. Is 32 the last order of symmetric two-circulant solution? Long time search given no resolvence of order 64.

The Visual Matlab program to calculate matrices H16 and H32.



THE GOLAY MATRICES


There are two families Ryser matrices – symmetric and non symmetric. The symmetric family can be a finite family, look above. The non symmetric two-circulant Hadamard matrices born by complementary Golay sequences, [2] have no this bound – order 32.



Two-circulant Golay matrices H4 and H8



Two-circulant Golay matrices H16 and H32



Two-circulant Golay matrices H64 and H128

PERIODIC GOLAY SEQUENCES



Dragomir's matrices H68 by SDS(34;16,13;12)





Four non regular two-circulant matrices H100


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



Regular two-circulant matrix H100 by (50; 25, 20; 20)



Regular two-circulant matrix H144 by (72;36,30;30)


This SDS for regular H100 above is given in Dragomir's paper in Annals of Comb (2011); note added in proof: Subsequent to the posting of the first version of paper on 14th July 2007, I.S. Kotsireas and C. Koukouvinos constructed by a completely different method another example of SDS with parameters (50; 25, 20; 20) [3]. The two examples are indeed nonequivalent.

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 [4]. 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.

Note that periodic Golay pairs are a generalization of the ordinary Golay pairs (so there is no need to treat Golay pairs separately). Recently several new periodic Golay pairs (of new orders) have been constructed by Ilias and Dragomir. In particular see the paper "Some new periodic Golay pairs" on arXiv:1310.5773v2 [math.CO] 27 Aug 2014 (it has been just published on-line in Numerical Algorithms).

There was also constructed periodic Golay pairs of length 72 with parameter set (72;36,30;30). This means that we also have have a regular two circulant H144. ( As today is a Sunday, the paper on periodic Golay pairs of length 72 will be posted on arXiv only on Tuesday morning, look link.) Moreover, the periodic Golay pairs can be "multiplied" with ordinary Golay pairs to produce longer periodic Golay pairs as recently proved by Georgiou et al in Biometrika (2014), pp. 17.

In view of the equivalence mentioned above, Nick's conjecture can be re-stated in terms of periodic Golay pairs: there are no periodic Golay pairs of length n>32 with (at least) one of the sequences symmetric.

Dragomir propose that all two circulant Hadamard Matrices be collected together under the heading of Periodic Golay Pairs. Another note: If we want to get regular two circulant Hadamard matrix then the corresponding periodic Golay pair must have parameters of the form (2x2; x2, x2x; x2x) where x>0 is an integer.

Some of these parameter sets have to be discarded because they do not pass the Arasu-Xiang test (necessary condition). For instance there are no periodic Golay pairs with such parameter sets for x=3, 7. However they could to be exist for infinitely many x's. The special cases of interest are x=5 which gave us regular H100 and x=6 which gives a regular H144. There have not to be matrix H196 periodic Golay pairs based.

1. Dragomir Z. Djokovic, Note on periodic complementary sets of binary sequences, Des. Codes, Cryptogr. 13 (1998), 251–256.
2. Dragomir Z. Djokovic, Cyclic (v; r, s; ) difference families with two base blocks and v ≤ 50. Ann. Comb. 15 (2011), no. 2, 233–254.
3. I. S. Kotsireas, C. Koukouvinos, Periodic complementary binary sequences of length 50. Int. J. Appl. Math. 21 (2008), 509–514.
4. Dragomir Z. Djokovic, I. S. Kotsireas, Some new periodic Golay pairs. arXiv:1310.5773v2 [math.CO] 27 Aug 2014
5. W. D. Wallis, Anne Penfold Street, and Jennifer Seberry Wallis, Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices, Springer-Verlag, Berlin 1972.
The review of Mikhail Muzychuk and Qing Xiang (PDF) is also useful.

SKEW HADAMARD MATRICES | TWO-CIRCULANT C-MATRICES

Rambler's Top100