A new approach to the excess problem of Hadamard matrices

Hirasaka, Mitsugu; Momihara, Koji; Suda, Sho

doi:10.5802/alco.33

Hirasaka, Mitsugu ¹; Momihara, Koji ²; Suda, Sho ³

¹ Department of Mathematics, Pusan National University, Busan 609-735, Republic of Korea
² Division of Natural Science, Faculty of Advanced Science and Technology, Kumamoto University, 2-40-1 Kurokami, Kumamoto 860-8555, Japan
³ Department of Mathematics Education, Aichi University of Education, 1 Hirosawa, Igaya-cho, Kariya, Aichi 448-8542, Japan

Algebraic Combinatorics, Volume 1 (2018) no. 5, pp. 697-722.

Abstract

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 ${(2 m + 1)}^{2} + 2$ or $m^{2} + {(m + 1)}^{2}$ is a prime power, then there exists a biregular Hadamard matrix of order $n = {(2 m + 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

MR Zbl

DOI: 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

Author's affiliations:

Hirasaka, Mitsugu ¹; Momihara, Koji ²; Suda, Sho ³

¹ Department of Mathematics, Pusan National University, Busan 609-735, Republic of Korea
² Division of Natural Science, Faculty of Advanced Science and Technology, Kumamoto University, 2-40-1 Kurokami, Kumamoto 860-8555, Japan
³ Department of Mathematics Education, Aichi University of Education, 1 Hirosawa, Igaya-cho, Kariya, Aichi 448-8542, Japan

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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},
     pages = {697--722},
     publisher = {MathOA foundation},
     volume = {1},
     number = {5},
     year = {2018},
     doi = {10.5802/alco.33},
     mrnumber = {3887408},
     zbl = {1401.05054},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.33/}
}

TY  - JOUR
AU  - Hirasaka, Mitsugu
AU  - Momihara, Koji
AU  - Suda, Sho
TI  - A new approach to the excess problem of Hadamard matrices
JO  - Algebraic Combinatorics
PY  - 2018
SP  - 697
EP  - 722
VL  - 1
IS  - 5
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.33/
DO  - 10.5802/alco.33
LA  - en
ID  - ALCO_2018__1_5_697_0
ER  -

%0 Journal Article
%A Hirasaka, Mitsugu
%A Momihara, Koji
%A Suda, Sho
%T A new approach to the excess problem of Hadamard matrices
%J Algebraic Combinatorics
%D 2018
%P 697-722
%V 1
%N 5
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.33/
%R 10.5802/alco.33
%G en
%F 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/articles/10.5802/alco.33/

References
Cited by

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

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

[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

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | Zbl

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

[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 | DOI | MR | Zbl

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

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

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

[15] Koukouvinos, Christos; Seberry, Jennifer Hadamard matrices of order $\equiv 8 (mod 16)$ with maximal excess, Discrete Math., Volume 92 (1991) no. 1-3, pp. 173-176 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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

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

[21] Seberry, Jennifer Existence of SBIBD $(4 k^{2}, 2 k^{2} \pm k, k^{2} \pm k)$ and Hadamard matrices with maximal excess, Australas. J. Comb., Volume 4 (1991), pp. 87-91 | MR | Zbl

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

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

Cited by Sources: