Orderly generation of Butson Hadamard matrices

Lampio, Pekka; Östergård, Patric; Szöllősi, Ferenc

doi:10.1090/mcom/3453

Orderly generation of Butson Hadamard matrices
HTML articles powered by AMS MathViewer

by Pekka H. J. Lampio, Patric R. J. Östergård and Ferenc Szöllősi HTML | PDF

Math. Comp. 89 (2020), 313-331 Request permission

Abstract:

In this paper Butson-type complex Hadamard matrices $\mathrm {BH}(n,q)$ of order $n$ over the complex $q$th roots of unity are classified for small parameters by computer-aided methods. The results include a classification of $\mathrm {BH}(21,3)$, $\mathrm {BH}(16,4)$, and $\mathrm {BH}(14,6)$ matrices. There are exactly $72$, $1786763$, and $167776$ such matrices, respectively, up to monomial equivalence. Additionally, an example of a $\mathrm {BH}(14,10)$ matrix is shown for the first time, and the nonexistence of $\mathrm {BH}(8,15)$, $\mathrm {BH}(11,q)$ for $q\in \{10,14,15\}$, and $\mathrm {BH}(13,15)$ matrices is proved.

References

S. S. Agaian, Hadamard matrices and their applications, Lecture Notes in Mathematics, vol. 1168, Springer-Verlag, Berlin, 1985. MR 818740, DOI 10.1007/BFb0101073
Kenzi Akiyama, Masayuki Ogawa, and Chihiro Suetake, On $\textrm {STD}_6[18,3]$’s and $\textrm {STD}_7[21,3]$’s admitting a semiregular automorphism group of order 9, Electron. J. Combin. 16 (2009), no. 1, Research Paper 148, 21. MR 2577316
Teodor Banica, Julien Bichon, and Jean-Marc Schlenker, Representations of quantum permutation algebras, J. Funct. Anal. 257 (2009), no. 9, 2864–2910. MR 2559720, DOI 10.1016/j.jfa.2009.04.013
Iliya Bouyukliev, Veerle Fack, and Joost Winne, 2-(31,15,7), 2-(35,17,8) and 2-(36,15,6) designs with automorphisms of odd prime order, and their related Hadamard matrices and codes, Des. Codes Cryptogr. 51 (2009), no. 2, 105–122. MR 2480692, DOI 10.1007/s10623-008-9247-x
Bradley W. Brock, Hermitian congruence and the existence and completion of generalized Hadamard matrices, J. Combin. Theory Ser. A 49 (1988), no. 2, 233–261. MR 964386, DOI 10.1016/0097-3165(88)90054-4
W. Bruzda, W. Tadej, K. Życzkowski, Web page for complex Hadamard matrices, http://chaos.if.uj.edu.pl/~karol/hadamard/.
A. T. Butson, Generalized Hadamard matrices, Proc. Amer. Math. Soc. 13 (1962), 894–898. MR 142557, DOI 10.1090/S0002-9939-1962-0142557-0
B. Compton, R. Craigen, and W. de Launey, Unreal $BH(n,6)$’s and Hadamard matrices, Des. Codes Cryptogr. 79 (2016), no. 2, 219–229. MR 3483942, DOI 10.1007/s10623-015-0045-y
R. Craigen, W. Holzmann, and H. Kharaghani, Complex Golay sequences: structure and applications, Discrete Math. 252 (2002), no. 1-3, 73–89. MR 1907747, DOI 10.1016/S0012-365X(01)00162-5
Warwick de Launey, On the nonexistence of generalised Hadamard matrices, J. Statist. Plann. Inference 10 (1984), no. 3, 385–396. MR 766653, DOI 10.1016/0378-3758(84)90062-4
P. Diţă, Some results on the parametrization of complex Hadamard matrices, J. Phys. A 37 (2004), no. 20, 5355–5374. MR 2065675, DOI 10.1088/0305-4470/37/20/008
Dragomir Ž. Đoković, Good matrices of orders $33,35$ and $127$ exist, J. Combin. Math. Combin. Comput. 14 (1993), 145–152. MR 1238866
Ronan Egan, Dane Flannery, and Padraig Ó Catháin, Classifying cocyclic Butson Hadamard matrices, Algebraic design theory and Hadamard matrices, Springer Proc. Math. Stat., vol. 133, Springer, Cham, 2015, pp. 93–106. MR 3440530, DOI 10.1007/978-3-319-17729-8_{8}
I. A. Faradžev, Constructive enumeration of combinatorial objects, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 131–135 (English, with French summary). MR 539959
P. B. Gibbons and R. Mathon, Enumeration of generalized Hadamard matrices of order 16 and related designs, J. Combin. Des. 17 (2009), no. 2, 119–135. MR 2489438, DOI 10.1002/jcd.20193
Uffe Haagerup, Orthogonal maximal abelian $*$-subalgebras of the $n\times n$ matrices and cyclic $n$-roots, Operator algebras and quantum field theory (Rome, 1996) Int. Press, Cambridge, MA, 1997, pp. 296–322. MR 1491124, DOI 10.1215/s0012-7094-97-09004-9
Masaaki Harada, Clement Lam, Akihiro Munemasa, and Vladimir D. Tonchev, Classification of generalized Hadamard matrices $H(6,3)$ and quaternary Hermitian self-dual codes of length 18, Electron. J. Combin. 17 (2010), no. 1, Research Paper 171, 14. MR 2769096
Masaaki Harada, Clement Lam, and Vladimir D. Tonchev, Symmetric $(4,4)$-nets and generalized Hadamard matrices over groups of order 4, Des. Codes Cryptogr. 34 (2005), no. 1, 71–87. MR 2126578, DOI 10.1007/s10623-003-4195-y
A. S. Hedayat, N. J. A. Sloane, and John Stufken, Orthogonal arrays, Springer Series in Statistics, Springer-Verlag, New York, 1999. Theory and applications; With a foreword by C. R. Rao. MR 1693498, DOI 10.1007/978-1-4612-1478-6
Gaurush Hiranandani and Jean-Marc Schlenker, Small circulant complex Hadamard matrices of Butson type, European J. Combin. 51 (2016), 306–314. MR 3398859, DOI 10.1016/j.ejc.2015.05.010
Mitsugu Hirasaka, Kyoung-Tark Kim, and Yoshihiro Mizoguchi, Uniqueness of Butson Hadamard matrices of small degrees, J. Discrete Algorithms 34 (2015), 70–77. MR 3378450, DOI 10.1016/j.jda.2015.05.009
K. J. Horadam, Hadamard matrices and their applications, Princeton University Press, Princeton, NJ, 2007. MR 2265694
Bengt R. Karlsson, BCCB complex Hadamard matrices of order 9, and MUBs, Linear Algebra Appl. 504 (2016), 309–324. MR 3502540, DOI 10.1016/j.laa.2016.04.012
Petteri Kaski and Patric R. J. Östergård, Classification algorithms for codes and designs, Algorithms and Computation in Mathematics, vol. 15, Springer-Verlag, Berlin, 2006. With 1 DVD-ROM (Windows, Macintosh and UNIX). MR 2192256
Hadi Kharaghani and Behruz Tayfeh-Rezaie, Hadamard matrices of order 32, J. Combin. Des. 21 (2013), no. 5, 212–221. MR 3037086, DOI 10.1002/jcd.21323
H. Kharaghani and B. Tayfeh-Rezaie, On the classification of Hadamard matrices of order 32, J. Combin. Des. 18 (2010), no. 5, 328–336. MR 2682517, DOI 10.1002/jcd.20245
Hiroshi Kimura, Classification of Hadamard matrices of order $28$, Discrete Math. 133 (1994), no. 1-3, 171–180. MR 1298972, DOI 10.1016/0012-365X(94)90024-8
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
Mihail N. Kolountzakis and Máté Matolcsi, Complex Hadamard matrices and the spectral set conjecture, Collect. Math. Vol. Extra (2006), 281–291. MR 2264214
A. J. LaClair, A Survey on Hadamard Matrices, Honors Thesis, University of Tennessee (2016).
Clement Lam, Sigmund Lam, and Vladimir D. Tonchev, Bounds on the number of affine, symmetric, and Hadamard designs and matrices, J. Combin. Theory Ser. A 92 (2000), no. 2, 186–196. MR 1796473, DOI 10.1006/jcta.2000.3060
T. Y. Lam and K. H. Leung, On vanishing sums of roots of unity, J. Algebra 224 (2000), no. 1, 91–109. MR 1736695, DOI 10.1006/jabr.1999.8089
P. H. J. Lampio, Classification of difference matrices and complex Hadamard matrices, PhD Thesis, Aalto University, (2015).
Pekka H. J. Lampio and Patric R. J. Östergård, Classification of difference matrices over cyclic groups, J. Statist. Plann. Inference 141 (2011), no. 3, 1194–1207. MR 2739160, DOI 10.1016/j.jspi.2010.09.023
P. H. J. Lampio, P. R. J. Östergård, F. Szöllősi, Dataset for Orderly Generation of Butson Hadamard Matrices [Dataset]. Zenodo. http://doi.org/10.5281/zenodo.2585765 (2019).
Pekka H. J. Lampio, Ferenc Szöllősi, and Patric R. J. Östergård, The quaternary complex Hadamard matrices of orders 10, 12, and 14, Discrete Math. 313 (2013), no. 2, 189–206. MR 2992490, DOI 10.1016/j.disc.2012.10.001
Daniel McNulty and Stefan Weigert, Isolated Hadamard matrices from mutually unbiased product bases, J. Math. Phys. 53 (2012), no. 12, 122202, 16. MR 3058175, DOI 10.1063/1.4764884
Remus Nicoara, Subfactors and Hadamard matrices, J. Operator Theory 64 (2010), no. 2, 453–468. MR 2718953
S. Niskanen, P.R.J. Östergård, Cliquer user’s guide, version 1.0, Technical Report T48, Communications Laboratory, Helsinki University of Technology, Espoo (2003).
William P. Orrick, Switching operations for Hadamard matrices, SIAM J. Discrete Math. 22 (2008), no. 1, 31–50. MR 2383227, DOI 10.1137/050641727
Patric R. J. Östergård, A fast algorithm for the maximum clique problem, Discrete Appl. Math. 120 (2002), no. 1-3, 197–207. Sixth Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1999). MR 1912867, DOI 10.1016/S0166-218X(01)00290-6
M. Petrescu, Existence of continuous families of complex Hadamard matrices of prime dimensions, PhD Thesis, University of California, Los Angeles (1997).
Ronald C. Read, Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations, Ann. Discrete Math. 2 (1978), 107–120. MR 491273
Jennifer Seberry, A construction for generalized Hadamard matrices, J. Statist. Plann. Inference 4 (1980), no. 4, 365–368. MR 596770, DOI 10.1016/0378-3758(80)90021-X
Jennifer Wallis, Complex Hadamard matrices, Linear and Multilinear Algebra 1 (1973), 257–272. MR 351855, DOI 10.1080/03081087308817024
Edward Spence, Classification of Hadamard matrices of order $24$ and $28$, Discrete Math. 140 (1995), no. 1-3, 185–243. MR 1333719, DOI 10.1016/0012-365X(93)E0169-5
Ferenc Szöllősi, A note on the existence of $\textrm {BH}(19,6)$ matrices, Australas. J. Combin. 55 (2013), 31–34. MR 3053196
F. Szöllősi, Mutually Unbiased Bases, Gauss sums, and the asymptotic existence of Butson Hadamard matrices, RIMS Kokyuroku 1872 (2014), 39–48.
Ferenc Szöllősi, On quaternary complex Hadamard matrices of small orders, Adv. Math. Commun. 5 (2011), no. 2, 309–315. MR 2801596, DOI 10.3934/amc.2011.5.309
Ferenc Szöllősi, Parametrizing complex Hadamard matrices, European J. Combin. 29 (2008), no. 5, 1219–1234. MR 2419225, DOI 10.1016/j.ejc.2007.06.009
Wojciech Tadej and Karol Życzkowski, A concise guide to complex Hadamard matrices, Open Syst. Inf. Dyn. 13 (2006), no. 2, 133–177. MR 2244963, DOI 10.1007/s11080-006-8220-2
Richard J. Turyn, Complex Hadamard matrices, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 435–437. MR 0270938
R. F. Werner, All teleportation and dense coding schemes, J. Phys. A 34 (2001), no. 35, 7081–7094. Quantum information and computation. MR 1863141, DOI 10.1088/0305-4470/34/35/332
Arne Winterhof, On the non-existence of generalized Hadamard matrices, J. Statist. Plann. Inference 84 (2000), no. 1-2, 337–342. MR 1747512, DOI 10.1016/S0378-3758(99)00147-0