Palabras clave
Goethals-Seidel theorem
Hadamard matrices
simulated annealing
combinatorial optimization
secuencias tipo Turyn
teorema de Goethals-Seidal
matrices de Hadamard
recocido simulado
optimización combinatoria
Cómo citar
Resumen
En este artículo estudiamos fundamentalmente las denominadas secuencias tipo Turyn y algunos algoritmos heurísticos para generarlas. La importancia de estas secuencias estriba, al menos, en el hecho de que pueden ser empleadas en la construcción de algunas matrices de Hadamard de órdenes 4(3m - 1), donde m es el largo de la secuencia tipo Turyn a través del uso del teorema de Goethals-Seidal. Simplificamos la demostración del teorema de Turyn (ver Teorema 3). Además, hallamos algunos resultados teóricos interesantes (ver Teorema 5). Finalmente, desarrollamos varios algoritmos heurísticos eficientes, comparables a los algoritmos ya conocidos, que generan secuencias tipo Turyn de tamaños
menores o iguales a 40.
Citas
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.
Comentarios
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Derechos de autor 2019 Esteban Segura Ugalde, Eduardo Piza Volio