A sensitive algorithm for detecting the inequivalence of Hadamard matrices

Authors:
Kai-Tai Fang and Gennian Ge

Journal:
Math. Comp. **73** (2004), 843-851

MSC (2000):
Primary 68Q15, 05B20, 62K15

Published electronically:
September 2, 2003

MathSciNet review:
2031409

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A Hadamard matrix of side is an matrix with every entry either or , which satisfies . Two Hadamard matrices are called equivalent if one can be obtained from the other by some sequence of row and column permutations and negations. To identify the equivalence of two Hadamard matrices by a complete search is known to be an NP hard problem when increases. In this paper, a new algorithm for detecting inequivalence of two Hadamard matrices is proposed, which is more sensitive than those known in the literature and which has a close relation with several measures of uniformity. As an application, we apply the new algorithm to verify the inequivalence of the known inequivalent Hadamard matrices of order ; furthermore, we show that there are at least pairwise inequivalent Hadamard matrices of order . The latter is a new discovery.

**1.**J. B. Clark and A. M. Dean, Equivalence of fractional factorial designs,*Statistica Sinica***11**(2001), 537-547.**2.**Charles J. Colbourn and Jeffrey H. Dinitz (eds.),*The CRC handbook of combinatorial designs*, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1996. MR**1392993****3.**Joan Cooper, James Milas, and W. D. Wallis,*Hadamard equivalence*, Combinatorial mathematics (Proc. Internat. Conf. Combinatorial Theory, Australian Nat. Univ., Canberra, 1977) Lecture Notes in Math., vol. 686, Springer, Berlin, 1978, pp. 126–135. MR**526738****4.**Jean-Guillaume Dumas, B. David Saunders, and Gilles Villard,*On efficient sparse integer matrix Smith normal form computations*, J. Symbolic Comput.**32**(2001), no. 1-2, 71–99. Computer algebra and mechanized reasoning (St. Andrews, 2000). MR**1840386**, 10.1006/jsco.2001.0451**5.**K. T. Fang and G. Ge, An efficient algorithm for the classification of Hadamard matrices,*Technical Report MATH-298*, Hong Kong Baptist University, 2001.**6.**S. Georgiou, C. Koukouvinos, M. Mitrouli, and Jennifer Seberry,*Necessary and sufficient conditions for three and four variable orthogonal designs in order 36*, J. Statist. Plann. Inference**106**(2002), no. 1-2, 329–352. Experimental design and related combinatorics. MR**1927719**, 10.1016/S0378-3758(02)00221-5**7.**M. Hall, Jr., Hadamard matrices of order 16,*J.P.L. Research Summary*36-10,**1**(1961), 21-26.**8.**M. Hall, Jr., Hadamard matrices of order 20,*J.P.L. Technical Report*, 32-761, 1965.**9.**F. J. Hickernell, ``Lattice rules: how well do they measure up?" in Random and Quasi-Random Point Sets, Eds P. Hellekalek and G. Larcher, Springer-Verlag, 106-166, 1998.**10.**N. Ito, J. S. Leon and J. Q. Longyear, Classification of 3-(24,12,5) designs and 24-dimensional Hadamard matrices,*J. Combin. Theory Ser. A***27**(1979), 289-306.**11.**H. Kimura, New Hadamard matrices of order 24,*Graphs Combin.***5**(1989), 236-242.**12.**Hiroshi Kimura,*Classification of Hadamard matrices of order 28 with Hall sets*, Discrete Math.**128**(1994), no. 1-3, 257–268. MR**1271869**, 10.1016/0012-365X(94)90117-1**13.**Hiroshi Kimura,*Classification of Hadamard matrices of order 28*, Discrete Math.**133**(1994), no. 1-3, 171–180. MR**1298972**, 10.1016/0012-365X(94)90024-8**14.**Hiroshi Kimura and Hiroyuki Ohmori,*Construction of Hadamard matrices of order 28*, Graphs Combin.**2**(1986), no. 3, 247–257. MR**951569**, 10.1007/BF01788099**15.**C. Lin, W. D. Wallis and L. Zhu, Extended -profiles of Hadamard matrices,*Ann. Discrete Math.***51**(1992), 175-180.**16.**C. Lin, W. D. Wallis, and L. Zhu,*Generalized 4-profiles of Hadamard matrices*, J. Combin. Inform. System Sci.**18**(1993), no. 3-4, 397–400. MR**1317248****17.**Cantian Lin, W. D. Wallis, and Zhu Lie,*Equivalence classes of Hadamard matrices of order 32*, Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993), 1993, pp. 179–182. MR**1267290****18.**Chang-Xing Ma, Kai-Tai Fang, and Dennis K. J. Lin,*On the isomorphism of fractional factorial designs*, J. Complexity**17**(2001), no. 1, 86–97. MR**1817609**, 10.1006/jcom.2000.0569**19.**Harald Niederreiter,*Random number generation and quasi-Monte Carlo methods*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR**1172997****20.**Edward Spence,*Classification of Hadamard matrices of order 24 and 28*, Discrete Math.**140**(1995), no. 1-3, 185–243. MR**1333719**, 10.1016/0012-365X(93)E0169-5**21.**Edward Spence,*Regular two-graphs on 36 vertices*, Linear Algebra Appl.**226/228**(1995), 459–497. MR**1344580**, 10.1016/0024-3795(95)00158-N**22.**Vladimir D. Tonchev,*Hadamard matrices of order 36 with automorphisms of order 17*, Nagoya Math. J.**104**(1986), 163–174. MR**868443**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
68Q15,
05B20,
62K15

Retrieve articles in all journals with MSC (2000): 68Q15, 05B20, 62K15

Additional Information

**Kai-Tai Fang**

Affiliation:
Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong, China

Email:
ktfang@math.hkbu.edu.hk

**Gennian Ge**

Affiliation:
Department of Mathematics, Suzhou University, Suzhou, 215006, China

Address at time of publication:
Department of Mathematics, Zhejiang University, Hongzhou 310027, Zhejiang, China

Email:
gnge@public1.sz.js.cn

DOI:
https://doi.org/10.1090/S0025-5718-03-01539-4

Keywords:
Algorithm,
equivalence,
Hadamard matrix,
Hamming distance,
uniformity

Received by editor(s):
July 9, 2001

Received by editor(s) in revised form:
November 28, 2001

Published electronically:
September 2, 2003

Additional Notes:
This research was supported in part by the Hong Kong RGC grants HKBU RC/98-99/Gen-370 and HKBU 2044/02P. The second author was also supported by statistics Research and Consultancy Centre, Hong Kong Baptist University and the YNSFC Grant 10001026

Article copyright:
© Copyright 2003
American Mathematical Society