A sensitive algorithm for detecting the inequivalence of Hadamard matrices

Fang, Kai-Tai; Ge, Gennian

doi:10.1090/S0025-5718-03-01539-4

A sensitive algorithm for detecting the inequivalence of Hadamard matrices
HTML articles powered by AMS MathViewer

by Kai-Tai Fang and Gennian Ge PDF

Math. Comp. 73 (2004), 843-851 Request permission

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

J. B. Clark and A. M. Dean, Equivalence of fractional factorial designs, Statistica Sinica 11 (2001), 537–547.
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, DOI 10.1201/9781420049954
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
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, DOI 10.1006/jsco.2001.0451
K. T. Fang and G. Ge, An efficient algorithm for the classification of Hadamard matrices, Technical Report MATH-298, Hong Kong Baptist University, 2001.
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, DOI 10.1016/S0378-3758(02)00221-5
M. Hall, Jr., Hadamard matrices of order 16, J.P.L. Research Summary 36-10, 1 (1961), 21–26.
M. Hall, Jr., Hadamard matrices of order 20, J.P.L. Technical Report, 32-761, 1965.
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.
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.
H. Kimura, New Hadamard matrices of order 24, Graphs Combin. 5 (1989), 236–242.
Hiroshi Kimura, Classification of Hadamard matrices of order $28$ with Hall sets, Discrete Math. 128 (1994), no. 1-3, 257–268. MR 1271869, DOI 10.1016/0012-365X(94)90117-1
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
Hiroshi Kimura and Hiroyuki Ohmori, Construction of Hadamard matrices of order $28$, Graphs Combin. 2 (1986), no. 3, 247–257. MR 951569, DOI 10.1007/BF01788099
C. Lin, W. D. Wallis and L. Zhu, Extended $4$-profiles of Hadamard matrices, Ann. Discrete Math. 51 (1992), 175–180.
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
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
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, DOI 10.1006/jcom.2000.0569
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, DOI 10.1137/1.9781611970081
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
Edward Spence, Regular two-graphs on $36$ vertices, Linear Algebra Appl. 226/228 (1995), 459–497. MR 1344580, DOI 10.1016/0024-3795(95)00158-N
Vladimir D. Tonchev, Hadamard matrices of order $36$ with automorphisms of order $17$, Nagoya Math. J. 104 (1986), 163–174. MR 868443, DOI 10.1017/S002776300002273X