Abstract
In this work, we propose an optimization approach for constructing various classes of circulant combinatorial designs that can be defined in terms of autocorrelation. The problem is formulated as a so-called feasibility problem having three sets, to which the Douglas–Rachford projection algorithm is applied. The approach is illustrated on three different classes of circulant combinatorial designs: circulant weighing matrices, D-optimal matrices of circulant type, and Hadamard matrices with two circulant cores. Furthermore, we explicitly construct two new circulant weighing matrices, a CW(126, 64) and a CW(198, 100), whose existence was previously marked as unresolved in the most recent version of Strassler’s table.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The support of \(c=(c_0,c_1,\ldots ,c_{n-1})\in {\mathbb {R}}^n\) is the set \(\{i\in \{0,\ldots ,n-1\}: c_i\ne 0\}\).
References
Aragón Artacho FJ, Borwein JM, Tam MK (2014a) Recent results on Douglas-Rachford methods for combinatorial optimization problems. J Optim Theory Appl 163(1):1–30
Aragón Artacho FJ, Borwein JM, Tam MK (2014b) Douglas-Rachford feasibility methods for matrix completion problems. ANZIAM J 55(4):299–326
Aragón Artacho FJ, Borwein JM, Tam MK (2016) Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem. J Glob Optim 65(2):309–327
Aragón Artacho FJ, Campoy R (accepted Nov. 2017) Solving graph coloring problems with the Douglas–Rachford algorithm. Set-Valued Var. Anal., p 27. https://doi.org/10.1007/s11228-017-0461-4
Arasu KT, Dillon JF (1999) Difference sets. Sequences and their correlation properties. In: Pott A, Kumar PV, Helleseth T, Jungnickel D (eds) Perfect ternary arrays. Springer, Dordrecht, pp 1–15
Arasu KT, Gulliver TA (2001) Self-dual codes over \({\mathbb{F}}_p\) and weighing matrices. IEEE Trans Inf Theory 47(5):2051–2055
Arasu KT, Gutman AJ (2010) Circulant weighing matrices. Cryptogr Commun 2:155–171
Arasu KT, Kotsireas IS, Koukouvinos C, Seberry J (2010) On circulant and two-circulant weighing matrices. Australas J Combin 48:43–51
Arasu KT, Leung KH, Ma SL, Nabavi A, Ray-Chaudhuri DK (2006a) Circulant weighing matrices of weight \(2^{2t}\). Des Codes Cryptogr 41(1):111–123
Arasu KT, Leung KH, Ma SL, Nabavi A, Ray-Chaudhuri DK (2006b) Determination of all possible orders of weight 16 circulant weighing matrices. Finite Fields Appl 12(4):498–538
Bauschke HH, Combettes PL (2011) Convex analysis and monotone operator theory in hilbert spaces. Springer, New York
Bauschke HH, Combettes PL, Luke DR (2004) Finding best approximation pairs relative to two closed convex sets in Hilbert space. J Approx Theory 127(2):178–192
Bauschke HH, Dao MN (2017) On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces. SIAM J Optim 27:207–537
Borwein JM, Lewis AS (2006) Convex analysis and nonlinear optimization. Springer, New York
Brent RP (2013) Finding D-optimal design by randomised decomposition and switching. Australas J Combin 55:15–30
Briggs WL, Henson VE (1995) DFT. An owner’s manual for the discrete Fourier transform, SIAM, Philadelphia
Cohn JHE (1989) On determinants with elements \(\pm \)1. Bull Lond Math Soc 21(1):36–42
Colbourn CJ, Dinitz JH (2007) Handbook of combinatorial designs, 2nd edn. Chapman & Hall, Boca Raton
Đoković DZ̆, Kotsireas IS (2012) New results on D-pptimal matrices. J Combin Des 20(6):278–289
Đoković DZ̆, Kotsireas IS (2015a) Compression of periodic complementary sequences and applications. Des Codes Cryptogr 74(2):365–377
Đoković DZ̆, Kotsireas IS (2015b) D-optimal matrices of orders 118, 138, 150, 154 and 174. In: Colbourn CJ (ed) Algebraic design theory and Hadamard matrices. Springer, Basel, pp 71–82
Ehlich H (1964) Determinantenabschätzungen für binäre Matrizen. Math Zeitschr 83:123–132
Elser V, Rankenburg I, Thibault P (2007) Searching with iterated maps. Proc Natl Acad Sci 104(2):418–426
Flammia ST, Severini S (2009) Weighing matrices and optical quantum computing. J Phys A 42(6):065302
Golomb SW, Gong G (2004) Signal design for good correlation. Cambridge University Press, New York
Gravel S, Elser V (2008) Divide and concur: a general approach to constraint satisfaction. Phys Rev E 78(3):036706
Gutman AJ (2009) Circulant weighing matrices. Master’s Thesis, Wright State University. http://rave.ohiolink.edu/etdc/view?acc_num=wright1244468669
Hesse R (2014) Fixed point algorithms for nonconvex feasibility with applications. Ph.D. thesis, University of Göttingen. http://hdl.handle.net/11858/00-1735-0000-0022-5F3F-E
Horadam KJ (2012) Hadamard matrices and their applications. Princeton University Press, New Jersey
Kotsireas IS (2013) Algorithms and metaheuristics for combinatorial matrices. In: Pardalos PM, Du D-Z, Graham RL (eds) Handbook of combinatorial optimization. Springer, New York, pp 283–309
Kotsireas IS, Koukouvinos C, Seberry J (2006) Hadamard ideals and Hadamard matrices with two circulant cores. Eur J Combin 27(5):658–668
Pierra G (1984) Decomposition through formalization in a product space. Math Program 28:96–115
Sala M, Sakata S, Mora T, Traverso C, Perret L (2009) Gröbner bases, coding, and cryptography. Springer, Berlin
Seberry JR (2017) Orthogonal designs: hadamard matrices, quadratic forms and algebras. Springer, Berlin
Seberry J, Yamada M (1992) Hadamard matrices, sequences, and block designs. In: Dintz JH, Stinson DR (eds) Contemporary design theory: a collection of surveys. Wiley, Hoboken, pp 431–560
Strassler Y (1997) The Classification of Circulant Weighing Matrices of Weight 9. Ph.D. thesis, Bar-Ilan University (Israel)
Stinson DR (2004) Combinatorial designs. Constructions and analysis. Springer, New York
Sturmfels B (2008) Algorithms in Invariant theory. Springer, Vienna
Tan MM (2016) Group invariant weighing matrices. arXiv:1610.01914
Tan MM (2014) Relative difference sets and circulant weighing matrices. Ph.D. thesis, Nanyang Technological University. https://repository.ntu.edu.sg/handle/10356/62325
van Dam W (2002) Quantum algorithms for weighing matrices and quadratic residues. Algorithmica 34(4):413–428
Acknowledgements
We would like to thank an anonymous referee for their careful reading and suggestions, which helped us to improve the manuscript. We would also like to thank Yossi Strassler for sending us a scan of his original table. This research was enabled, in part, thanks to support provided by Compute Canada and their Graham petascale supercomputer.
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to Jonathan M. Borwein.
This work is dedicated to the late Jonathan M. Borwein who suggested this project during his 2016 sabbatical in Canada. FJAA and RC were partially supported by Ministerio de Economía, Industria y Competitividad (MINECO) and European Regional Development Fund (ERDF), Grant MTM2014-59179-C2-1-P. FJAA was supported by the Ramón y Cajal program by MINECO and ERDF (RYC-2013-13327) and RC was supported by MINECO and European Social Fund (BES-2015-073360) under the program “Ayudas para contratos predoctorales para la formación de doctores 2015”. IK is supported by an Natural Sciences and Engineering Research Council Grant. MKT was supported by Deutsche Forschungsgemeinschaft RTG2088 and by a Postdoctoral Fellowship from the Alexander von Humboldt Foundation.
Appendix: Detailed results for CW matrices
Appendix: Detailed results for CW matrices
Rights and permissions
About this article
Cite this article
Aragón Artacho, F.J., Campoy, R., Kotsireas, I. et al. A feasibility approach for constructing combinatorial designs of circulant type. J Comb Optim 35, 1061–1085 (2018). https://doi.org/10.1007/s10878-018-0250-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-018-0250-5