ALGEBRAIC COMBINATORICS

no. 5
A new approach to the excess problem of Hadamard matrices
Algebraic Combinatorics, Volume 1 (2018) no. 5, pp. 697-722.

In this paper, we give a new technique to find families of Hadamard matrices with maximum excess. In particular, we find regular or biregular Hadamard matrices with maximum excess by negating some rows and columns of known Hadamard matrices obtained from quadratic residues of finite fields. More precisely, we show that if either (2m+1) 2 +2 or m 2 +(m+1) 2 is a prime power, then there exists a biregular Hadamard matrix of order n=(2m+1) 2 +3 with maximum excess. Furthermore, we give a sufficient condition for Hadamard matrices obtained from quadratic residues being transformed to regular ones in terms of four-class translation association schemes on finite fields. The core part of this paper is how to find “switching” sets of rows and columns.

Received: 2018-03-06
Revised: 2018-07-10
Accepted: 2018-07-10
Published online: 2018-11-30
DOI: https://doi.org/10.5802/alco.33
Classification: 05B20,  05B05,  05E30,  11T22,  11T24
Keywords: Hadamard matrix, Regular Hadamard matrix, Biregular Hadamard matrix, Excess, Association scheme, t-intersection set, Block design 
@article{ALCO_2018__1_5_697_0,
     author = {Hirasaka, Mitsugu and Momihara, Koji and Suda, Sho},
     title = {A new approach to the excess problem of Hadamard matrices},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {1},
     number = {5},
     year = {2018},
     pages = {697-722},
     doi = {10.5802/alco.33},
     zbl = {1401.05054},
     mrnumber = {3887408},
     language = {en},
     url = {alco.centre-mersenne.org/item/ALCO_2018__1_5_697_0/}
}
Hirasaka, Mitsugu; Momihara, Koji; Suda, Sho. A new approach to the excess problem of Hadamard matrices. Algebraic Combinatorics, Volume 1 (2018) no. 5, pp. 697-722. doi : 10.5802/alco.33. https://alco.centre-mersenne.org/item/ALCO_2018__1_5_697_0/

[1] Bannai, Eiichi Subschemes of some association schemes, J. Algebra, Volume 144 (1991) no. 1, pp. 167-188 | Article | MR 1136902 | Zbl 0762.20004

[2] Bannai, Eiichi; Ito, Tatsuro Algebraic Combinatorics I. Association Schemes, Mathematics Lecture Note Series, Benjamin/Cumming Publishing Company, 1984, xxiv+425 pages | Zbl 0555.05019

[3] Berndt, Bruce C.; Evans, Ronald J.; Williams, Kenneth S. Gauss and Jacobi Sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, Wiley, 1997, xi+583 pages | Zbl 0906.11001

[4] Best, Marc R. The excess of Hadamard matrix, Indagationes Math., Volume 80 (1977), pp. 357-361 | Article | MR 460152 | Zbl 0366.05016

[5] Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried Design Theory, vol. 1, 2, Encyclopedia of Mathematics and Its Applications, Volume 69, 78, Cambridge University Press, 1999 | Zbl 0945.05004

[6] Brouwer, Andries E.; Wilson, Richard M.; Xiang, Qing Cyclotomy and strongly regular graphs, J. Algebr. Comb., Volume 10 (1999) no. 1, pp. 25-28 | Article | MR 1701281 | Zbl 0929.05094

[7] Craigen, Robert; Kharaghani, Hadi Weaving Hadamard matrices with maximum excess and classes with small excess, J. Combin. Des., Volume 12 (2004) no. 4, pp. 233-255 | Article | MR 2063259 | Zbl 1045.05023

[8] Farmakis, Nikos; Kounias, Stratis The excess of Hadamard matrices and optimal designs, Discrete Math., Volume 67 (1987), pp. 165-176 | Article | MR 913182 | Zbl 0652.05006

[9] Hammer, Joseph; Levingston, Richard; Seberry, Jennifer A remark on the excess of Hadamard matrices and orthogonal designs, Ars Comb., Volume 5 (1978), pp. 237-254 | MR 491241 | Zbl 0427.05019

[10] Holzmann, Wolfgang H.; Kharaghani, Hadi On the excess of Hadamard matrices, Congr. Numer., Volume 92 (1993), pp. 257-260 | MR 1278970

[11] Holzmann, Wolfgang H.; Kharaghani, Hadi; Lavassani, M. T. The excess problem and some excess inequivalent matrices of order 32, J. Stat. Plann. Inference, Volume 72 (1998) no. 1-2, pp. 381-391 | Article | MR 1655204 | Zbl 0941.05015

[12] Kharaghani, Hadi An infinite class of Hadamard matrices of maximal excess, Discrete Math., Volume 89 (1991), pp. 307-312 | Article | MR 1112448 | Zbl 0734.05028

[13] Koukouvinos, Christos; Kounias, Stratis Construction of some Hadamard matrices with maximum excess, Discrete Math., Volume 85 (1990) no. 3, pp. 295-300 | Article | MR 1081837 | Zbl 0732.05016

[14] Koukouvinos, Christos; Kounias, Stratis; Seberry, Jennifer Supplementary difference sets and optimal designs, Discrete Math., Volume 88 (1991) no. 1, pp. 49-58 | Article | MR 1099267 | Zbl 0756.05032

[15] Koukouvinos, Christos; Seberry, Jennifer Hadamard matrices of order ≡8(mod16) with maximal excess, Discrete Math., Volume 92 (1991) no. 1-3, pp. 173-176 | Article | MR 1140584 | Zbl 0762.05024

[16] Kounias, Stratis; Farmakis, Nikos On the excess of Hadamard matrices, Discrete Math., Volume 68 (1988) no. 1, pp. 59-69 | Article | MR 921730 | Zbl 0667.05013

[17] Lidl, Rudolf; Niederreiter, Harald Finite Fields, Encyclopedia of Mathematics and Its Applications, Volume 20, Cambridge University Press, 1997, xiv+755 pages | MR 1429394 | Zbl 0866.11069

[18] Meijer, Paul; van der Vlugt, Marcel The evaluation of Gauss sums for characters of 2-power order, J. Number Theory, Volume 100 (2003) no. 2, pp. 381-395 | Article | MR 1978463 | Zbl 1030.11067

[19] Momihara, Koji; Suda, Sho Conference matrices with maximum excess and two-intersection sets, Integers, Volume 17 (2017), A30, 15 pages | MR 3671792 | Zbl 1414.05051

[20] Muzychuk, Mikhail E. V-rings of permutation groups with invariant metric (1987) (Ph. D. Thesis)

[21] Seberry, Jennifer Existence of SBIBD(4k 2 ,2k 2 ±k,k 2 ±k) and Hadamard matrices with maximal excess, Australas. J. Comb., Volume 4 (1991), pp. 87-91 | MR 1129270 | Zbl 0763.05016

[22] Storer, Thomas Cyclotomy and Difference Sets, Markham Publishing Company, 1967, vii+134 pages | MR 217033 | Zbl 0157.03301

[23] Xia, Tianbing; Xia, Mingyuan; Seberry, Jennifer Regular Hadamard matrix, maximum excess and SBIBD, Australas. J. Comb., Volume 27 (2003), pp. 263-275 | MR 1955407 | Zbl 1027.05009