Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Abstract | References | Similar Articles | Additional Information

Abstract: A Hadamard matrix of side $n$ is an $n \times n$ matrix with every entry either $1$ or $-1$, which satisfies $HH^{T}=nI$. 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 $n$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 $60$ inequivalent Hadamard matrices of order $24$; furthermore, we show that there are at least $382$ pairwise inequivalent Hadamard matrices of order $36$. The latter is a new discovery.

References [Enhancements On Off] (What's this?)

  • 1. J. B. Clark and A. M. Dean, Equivalence of fractional factorial designs, Statistica Sinica 11 (2001), 537-547.
  • 2. C. J. Colbourn and J. H. Dinitz, CRC Handbook of Combinatorial Designs, CRC Press Inc., Boca Raton, 1996. MR 97a:05001
  • 3. J. Cooper, J. Milas and W. D. Wallis, Hadamard equivalence, Comb. Math., Proc. Int. Conf., Canberra 1977, Lect. Notes Math. 686 (1978), 126-135. MR 80c:05043
  • 4. J. G. Dumas, B. D. Saunders and G. Villard, On efficient sparse integer matrix Smith normal form computations, J. Symb. Comput. 32 (2001), 71-100. MR 2002d:65042
  • 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 J. Seberry, Necessary and sufficient conditions for three and four variable orthogonal designs in order 36, J. Statist. Plann. Inference 106 (2002), 329-352.MR 2003g:62132
  • 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. H. Kimura, Classification of Hadamard matrices of order $28$ with Hall sets, Discrete Math. 128 (1994), 257-268. MR 94m:05046
  • 13. H. Kimura, Classification of Hadamard matrices of order 28, Discrete Math. 133 (1994), 171-180. MR 95i:05040
  • 14. H. Kimura and H. Ohmori, Construction of Hadamard matrices of order 28, Graphs Combin. 2 (1986), 247-257. MR 89h:05019
  • 15. C. Lin, W. D. Wallis and L. Zhu, Extended $4$-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. Comb. Inf. Syst. Sci. 18 (1993), 397-400. MR 96a:05032
  • 17. C. Lin, W. D. Wallis and L. Zhu, Equivalence classes of Hadamard matrices of order 32, Congr. Numerantium 95 (1993), 179-182. MR 94m:05047
  • 18. C. X. Ma, K. T. Fang and D. K. J. Lin, On isomorphism of fractional factorial designs, J. Complexity 17 (2001), 86-97. MR 2002b:05021
  • 19. H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, Philadelphia, 1992. MR 93h:65008
  • 20. E. Spence, Classification of Hadamard matrices of order 24 and 28, Discrete Math. 140 (1995), 185-243. MR 96b:05040
  • 21. E. Spence, Regular two-graphs on $36$ vertices, Lin. Alg. and its App. 226-228 (1995), 459-497. MR 96c:05167
  • 22. V. D. Tonchev, Hadamard matrices of order $36$ with automorphism of order 17, Nagoya Math. J. 104 (1986), 163-174. MR 88a:05032

Similar Articles

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

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

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

American Mathematical Society