Hadamard Matrices

Emeritus Professor Mieko Yamada of Kanazawa University graduated from Tokyo Woman's Christian University and received her PhD from Kyusyu University in 1987. She has taught at Tokyo Woman's Christian University, Konan University, Kyushu University, and Kanazawa University. Her areas of research are combinatorics, especially Hadamard matrices, difference sets and codes. Her research approach for combinatorics is based on number theory and algebra. She is a foundation fellow of Institute of Combinatorics and its Applications (ICA). She is an author of 51 papers in combinatorics and number theory. Emeritus Professor Jennifer Seberry graduated from University of New South Wales and received her PhD in Computation Mathematics from La Trobe University in 1971. She has held positions at the Australian National University, The University of Sydney, University College, The Australian Defence Force Academy (ADFA), The University of New South Wales, and University of Wollongong. She served as a head of Department of Computer Science of ADFA and a director of Centre for Computer Security Research of ADFA at University of Wollongong. She has published over 450 papers and eight books in Hadamard matrices, orthogonal designs, statistical designs, cryptology, and computer security.

• List of Tables xiiiList of Figures xvPreface xviiAcknowledgments xixAcronyms xxiIntroduction xxiii1 Basic Definitions 11.1 Notations 11.2 Finite Fields 11.2.1 A Residue Class Ring 11.2.2 Properties of Finite Fields 41.2.3 Traces and Norms 41.2.4 Characters of Finite Fields 61.3 Group Rings and Their Characters 81.4 Type 1 and Type 2 Matrices 91.5 Hadamard Matrices 141.5.1 Definition and Properties of an Hadamard Matrix 141.5.2 Kronecker Product and the Sylvester Hadamard Matrices 171.5.2.1 Remarks on Sylvester Hadamard Matrices 181.5.3 Inequivalence Classes 191.6 Paley Core Matrices 201.7 Amicable Hadamard Matrices 221.8 The Additive Property and Four Plug-In Matrices 261.8.1 Computer Construction 261.8.2 Skew Hadamard Matrices 271.8.3 Symmetric Hadamard Matrices 271.9 Difference Sets, Supplementary Difference Sets, and Partial Difference Sets 281.9.1 Difference Sets 281.9.2 Supplementary Difference Sets 301.9.3 Partial Difference Sets 311.10 Sequences and Autocorrelation Function 331.10.1 Multiplication of NPAF Sequences 351.10.2 Golay Sequences 361.11 Excess 371.12 Balanced Incomplete Block Designs 391.13 Hadamard Matrices and SBIBDs 411.14 Cyclotomic Numbers 411.15 Orthogonal Designs and Weighing Matrices 461.16 T-matrices, T-sequences, and Turyn Sequences 471.16.1 Turyn Sequences 482 Gauss Sums, Jacobi Sums, and Relative Gauss Sums 492.1 Notations 492.2 Gauss Sums 492.3 Jacobi Sums 512.3.1 Congruence Relations 522.3.2 Jacobi Sums of Order 4 522.3.3 Jacobi Sums of Order 8 572.4 Cyclotomic Numbers and Jacobi Sums 602.4.1 Cyclotomic Numbers for e = 2 622.4.2 Cyclotomic Numbers for e = 4 632.4.3 Cyclotomic Numbers for e = 8 642.5 Relative Gauss Sums 692.6 Prime Ideal Factorization of Gauss Sums 722.6.1 Prime Ideal Factorization of a Primep 722.6.2 Stickelberger’s Theorem 722.6.3 Prime Ideal Factorization of the Gauss Sum in Q(𝜁q−1) 732.6.4 Prime Ideal Factorization of the Gauss Sums in Q(𝜁m) 743 Plug-In Matrices 773.1 Notations 773.2 Williamson Type and Williamson Matrices 773.3 Plug-In Matrices 823.3.1 The Ito Array 823.3.2 Good Matrices : A Variation of Williamson Matrices 823.3.3 The Goethals–Seidel Array 833.3.4 Symmetric Hadamard Variation 843.4 Eight Plug-In Matrices 843.4.1 The Kharaghani Array 843.5 More T-sequences and T-matrices 853.6 Construction of T-matrices of Order 6m + 1 873.7 Williamson Hadamard Matrices and Paley Type II Hadamard Matrices 903.7.1 Whiteman’s Construction 903.7.2 Williamson Equation from Relative Gauss Sums 943.8 Hadamard Matrices of Generalized Quaternion Type 973.8.1 Definitions 973.8.2 Paley Core Type I Matrices 993.8.3 Infinite Families of Hadamard Matrices of GQ Type and Relative Gauss Sums 993.9 Supplementary Difference Sets and Williamson Matrices 1003.9.1 Supplementary Difference Sets from Cyclotomic Classes 1003.9.2 Constructions of an Hadamard 4-sds 1023.9.3 Construction from (q; x, y)-Partitions 1053.10 Relative Difference Sets and Williamson-Type Matrices over Abelian Groups 1103.11 Computer Construction of Williamson Matrices 1124 Arrays: Matrices to Plug-Into 1154.1 Notations 1154.2 Orthogonal Designs 1154.2.1 Baumert–Hall Arrays and Welch Arrays 1164.3 Welch and Ono–Sawade–Yamamoto Arrays 1214.4 Regular Representation of a Group and BHW(G) 1225 Sequences 1255.1 Notations 1255.2 PAF and NPAF 1255.3 Suitable Single Sequences 1265.3.1 Thoughts on the Nonexistence of Circulant Hadamard Matrices for Orders >4 1265.3.2 SBIBD Implications 1275.3.3 From ±1 Matrices to ±A,±B Matrices 1275.3.4 Matrix Specifics 1295.3.5 Counting Two Ways 1295.3.6 For m Odd: Orthogonal Design Implications 1305.3.7 The Case for Order 16 1305.4 Suitable Pairs of NPAF Sequences: Golay Sequences 1315.5 Current Results for Golay Pairs 1315.6 Recent Results for Periodic Golay Pairs 1335.7 More on Four Complementary Sequences 1335.8 6-Turyn-Type Sequences 1365.9 Base Sequences 1375.10 Yang-Sequences 1375.10.1 On Yang’s Theorems on T-sequences 1405.10.2 Multiplying by 2g + 1, g the Length of a Golay Sequence 1425.10.3 Multiplying by 7 and 13 1435.10.4 Koukouvinos and Kounias Number 1446 M-structures 1456.1 Notations 1456.2 The Strong Kronecker Product 1456.3 Reducing the Powers of 2 1476.4 Multiplication Theorems Using M-structures 1496.5 Miyamoto’s Theorem and Corollaries via M-structures 1517 Menon Hadamard Difference Sets and Regular Hadamard Matrices 1597.1 Notations 1597.2 Menon Hadamard Difference Sets and Exponent Bound 1597.3 Menon Hadamard Difference Sets and Regular Hadamard Matrices 1607.4 The Constructions from Cyclotomy 1617.5 The Constructions Using Projective Sets 1657.5.1 Graphical Hadamard Matrices 1697.6 The Construction Based on Galois Rings 1707.6.1 Galois Rings 1707.6.2 Additive Characters of Galois Rings 1707.6.3 A New Operation 1717.6.4 Gauss Sums Over GR(2n+1, s) 1717.6.5 Menon Hadamard Difference Sets Over GR(2n+1, s) 1727.6.6 Menon Hadamard Difference Sets Over GR(22, s) 1738 Paley Hadamard Difference Sets and Paley Type Partial Difference Sets 1758.1 Notations 1758.2 Paley Core Matrices and Gauss Sums 1758.3 Paley Hadamard Difference Sets 1788.3.1 Stanton–Sprott Difference Sets 1798.3.2 Paley Hadamard Difference Sets Obtained from Relative Gauss Sums 1808.3.3 Gordon–Mills–Welch Extension 1818.4 Paley Type Partial Difference Set 1828.5 The Construction of Paley Type PDS from a Covering Extended Building Set 1838.6 Constructing Paley Hadamard Difference Sets 1919 Skew Hadamard, Amicable, and Symmetric Matrices 1939.1 Notations 1939.2 Introduction 1939.3 Skew Hadamard Matrices 1939.3.1 Summary of Skew Hadamard Orders 1949.4 Constructions for Skew Hadamard Matrices 1959.4.1 The Goethals–Seidel Type 1969.4.2 An Adaption of Wallis–Whiteman Array 1979.5 Szekeres Difference Sets 2009.5.1 The Construction by Cyclotomic Numbers 2029.6 Amicable Hadamard Matrices 2049.7 Amicable Cores 2079.8 Construction for Amicable Hadamard Matrices of Order 2t 2089.9 Construction of Amicable Hadamard Matrices Using Cores 2099.10 Symmetric Hadamard Matrices 2119.10.1 Symmetric Hadamard Matrices Via Computer Construction 2129.10.2 Luchshie Matrices Known Results 21210 Skew Hadamard Difference Sets 21510.1 Notations 21510.2 Skew Hadamard Difference Sets 21510.3 The Construction by Planar Functions Over a Finite Field 21510.3.1 Planar Functions and Dickson Polynomials 21510.4 The Construction by Using Index 2 Gauss Sums 21810.4.1 Index 2 Gauss Sums 21810.4.2 The Case that p1 ≡ 7 (mod 8) 21910.4.3 The Case that p1 ≡ 3 (mod 8) 22110.5 The Construction by Using Normalized Relative Gauss Sums 22610.5.1 More on Ideal Factorization of the Gauss Sum 22610.5.2 Determination of Normalized Relative Gauss Sums 22610.5.3 A Family of Skew Hadamard Difference Sets 22811 Asymptotic Existence of Hadamard Matrices 23311.1 Notations 23311.2 Introduction 23311.2.1 de Launey’s Theorem 23311.3 Seberry’s Theorem 23311.4 Craigen’s Theorem 23411.4.1 Signed Groups and Their Representations 23411.4.2 A Construction for Signed Group Hadamard Matrices 23611.4.3 A Construction for Hadamard Matrices 23811.4.4 Comments on Orthogonal Matrices Over Signed Groups 24011.4.5 Some Calculations 24111.5 More Asymptotic Theorems 24311.6 Skew Hadamard and Regular Hadamard 24312 More on Maximal Determinant Matrices 24512.1 Notations 24512.2 E-Equivalence: The Smith Normal Form 24512.3 E-Equivalence: The Number of Small Invariants 24712.4 E-Equivalence: Skew Hadamard and Symmetric Conference Matrices 25012.5 Smith Normal Form for Powers of 2 25212.6 Matrices with Elements (1,−1) and Maximal Determinant 25312.7 D-Optimal Matrices Embedded in Hadamard Matrices 25412.7.1 Embedding of D5 in H8 25412.7.2 Embedding of D6 in H8 25512.7.3 Embedding of D7 in H8 25512.7.4 Other Embeddings 25512.8 Embedding of Hadamard Matrices within Hadamard Matrices 25712.9 Embedding Properties Via Minors 25712.10 Embeddability of Hadamard Matrices 25912.11 Embeddability of Hadamard Matrices of Order n − 8 26012.12 Embeddability of Hadamard Matrices of Order n −k 26112.12.1 Embeddability–Extendability of Hadamard Matrices 26212.12.2 Available Determinant Spectrum and Verification 26312.13 Growth Problem for Hadamard Matrices 265A Hadamard Matrices 271A.1 Hadamard Matrices 271A.1.1 Amicable Hadamard Matrices 271A.1.2 Skew Hadamard Matrices 271A.1.3 Spence Hadamard Matrices 272A.1.4 Conference Matrices Give Symmetric Hadamard Matrices 272A.1.5 Hadamard Matrices from Williamson Matrices 273A.1.6 OD Hadamard Matrices 273A.1.7 Yamada Hadamard Matrices 273A.1.8 Miyamoto Hadamard Matrices 273A.1.9 Koukouvinos and Kounias 273A.1.10 Yang Numbers 274A.1.11 Agaian Multiplication 274A.1.12 Craigen–Seberry–Zhang 274A.1.13 de Launey 274A.1.14 Seberry/Craigen Asymptotic Theorems 275A.1.15 Yang’s Theorems and –Dokovic´ Updates 275A.1.16 Computation by –Dokovic´ 275A.2 Index of Williamson Matrices 275A.3 Tables of Hadamard Matrices 276B List of sds from Cyclotomy 295B.1 Introduction 295B.2 List of n − { q; k1,…, kn ∶ 𝜆} sds 295C Further Research Questions 301C.1 Research Questions for Future Investigation 301C.1.1 Matrices 301C.1.2 Base Sequences 301C.1.3 Partial Difference Sets 301C.1.4 de Launey’s Four Questions 301C.1.5 Embedding Sub-matrices 302C.1.6 Pivot Structures 302C.1.7 Trimming and Bordering 302C.1.8 Arrays 302References 303Index 313