Keywords
Goethals-Seidel theorem
Hadamard matrices
simulated annealing
combinatorial optimization
secuencias tipo Turyn
teorema de Goethals-Seidal
matrices de Hadamard
recocido simulado
optimización combinatoria
How to Cite
Abstract
In this paper we study the so called Turyn type sequences and some heuristics algorithms to generate them. The importance of these sequences lies, at least, in the fact that they can be used to construct some Hadamard matrices of order 4(3m - 1), where m is the length of the Turyn type sequence through the theorem of Goethals-Seidal. We simplify the proof of Turyn’s theorem (see Theorem 3). In addition, we find some interesting theoretical results (see Theorem 5). Finally, we develop several efficient heuristic algorithms, comparable to the algorithms already known, that generate Turyn type sequences of sizes less than or equal to 40.
References
E. Aarts, J. Korst, Simulated Annealing and Boltzmann Machines. A Stochastic Approach to Combinatorial Optimization and Computing. John Wiley & Sons Inc, Chichester, 1990.
S. Agaian, H. Sarukhanyan, K. Egiazarian, J. Astola, Applications of Hadamard matrices in communication systems, in: Hadamard Transforms, SPIE Press, Washington, 2001, pp. 419–448.
D. Best, D.Z. Ðokovi´c, H. Kharaghani, H. Ramp, Turyn type sequences: classification, enumeration and construction, Journal of Combinatorial Designs 21 (2013), no. 1, 24–35.
R. P. Brent, J. H. Osborn, On minors of maximal determinant matrices, Journal of Integer Sequences 16 (2013), article 13.4.2.
W. A. Coppel, Number Theory: An Introduction to Mathematics, 2nd edition, Springer, Heidelberg, 2009.
H. Evangelaras, C. Koukouvinos, J. Seberry, Applications of Hadamard matrices, Journal of Telecommunications and Information Technology (2003), no. 2, 3–10.
H. Evangelaras, C. Koukouvinos, On the use of Hadamard matrices in factorial designs, Utilitas Mathematica 64 (2003).
W. de Launey, On the asymptotic existence of Hadamard matrices, J. Combin. Theory Ser. A 116 (2009), no. 4, 1002–1008.
D. Z. Ðokovi´c, Williamson matrices of order 4n for n = 33, 35, 39, Discrete Math. 115 (1993), no. 1-3, 267–271.
D. Z. Ðokovi´c, Hadamard matrices of order 764 exist, Combinatorica 28 (2008), no. 4, 487–489.
D. Z. Ðokovi´c, Supplementary difference sets with symmetry for Hadamard matrices, Operators and Matrices 3 (2009), no. 4, 557–569.
D. K. Faddeev, I. S. Sominskii, Problems in higher algebra, W.H. Freeman, San Francisco, 1965, p. 331.
J. M. Goethals, J. J. Seidel, Orthogonal matrices with zero diagonal, Canadian Journal of Mathematics 19 (1967), 1001–1010.
J. Hadamard, Résolution d’une question relative aux déterminants, Bull. Sci. Math. 2 (1893), 240–246.
J. Horton, C. Koukouvinos, J. Seberry, A search for Hadamard matrices constructed from Williamson matrices, Bulletin Institute of Combinatorics and its Applications 35 (2002), 75–88.
W. M. Kantor, Automorphism groups of Hadamard matrices, Journal of Combinatorial Theory 6 (1969), no. 3, 279–281.
H. Kharaghani, B. Tayfeh-Rezaie, A Hadamard Matrix of Order 428, Journal of Combinatorial Designs 13 (2005), no. 6, 435–440.
H. Kharaghani, B. Tayfeh-Rezaie, Hadamard matrices of order 32, Journal of Combinatorial Designs 21 (2012), no. 5, 212-221.
E. Kikianty, Hermite-Hadamard inequality in the geometry of Banach spaces, Ph.D. Thesis, University of Pretoria, 2010.
C. Koukouvinos, S. Kounias, J. Seberry, C. H. Yang, J. Yang, On sequences with zero autocorrelation, Designs, Codes and Criptography 4 (1994), no. 3, 327–340.
C. Koukouvinos, D. E. Simos, Encryption schemes based on Hadamard matrices with circulant cores, Journal of Applied Mathematics & Bioinformatics 3 (2013), no. 1, 17–41.
S. London, Constructing new Turyn type sequences, T-sequences and Hadamard matrices, Ph.D. Thesis, University of Illinois at Chicago, 2013.
M. A. Miyamoto, A construction of Hadamard matrices, J. Combin. Theory Ser. A 57 (1991), no. 1, 86–108.
E. Piza, Búsqueda de matrices de Hadamard a través de secuencias de Turyn, Revista de Matemática: Teoría y Aplicaciones 18 (2011), no. 2, 193–214.
R. Paley, On orthogonal matrices, Journal Math. Phys. 12 (1933), no. 1-4, 311–320.
J. Seberry, M. Yamada, Hadamard matrices, sequences, and block designs, Contemporary Design Theory: A Collection of Surveys, John Wiley & Sons Inc, New York, 1992, pp. 431–560.
J. Wallis, On supplementary difference sets, Aequationes Mathematicae 8 (1972), no. 3, 242–257.
N. J. Sloane, Multiplexing methods in spectroscopy, Mathematics Magazine 52 (1979), no. 2 ,71–80.
R. J. Turyn, Hadamard matrices, Baumert-Hall units, four-symbols sequences, pulse compression, and surface wave enconding, J. Combin. Theory Ser. A 16 (1974), no. 3, 313–333.
Comments
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright (c) 2019 Revista de Matemática: Teoría y Aplicaciones