Hadamard Matrices Constructions using Number Theory and Linear Algebra

by Seberry, Jennifer; Yamada, Mieko

• ISBN13: 9781119520245
• ISBN10: 111952024X
• Edition: 1st
• Format: Hardcover
• Copyright: 2020-08-25
• Publisher: Wiley

Summary

Up-to-date resource on Hadamard matrices

Hadamard Matrices: Constructions using Number Theory and Algebra provides students with a discussion of the basic definitions used for Hadamard Matrices as well as more advanced topics in the subject, including:

• Gauss sums, Jacobi sums and relative Gauss sums
• Cyclotomic numbers
• Plug-in matrices, arrays, sequences and M-structure
• Galois rings and Menon Hadamard differences sets
• Paley difference sets and Paley type partial difference sets
• Symmetric Hadamard matrices, skew Hadamard matrices and amicable Hadamard matrices
• A discussion of asymptotic existence of Hadamard matrices
• Maximal determinant matrices, embeddability of Hadamard matrices and growth problem for Hadamard matrices

The book can be used as a textbook for graduate courses in combinatorics, or as a reference for researchers studying Hadamard matrices.

Utilized in the fields of signal processing and design experiments, Hadamard matrices have been used for 150 years, and remain practical today. Hadamard Matrices combines a thorough discussion of the basic concepts underlying the subject matter with more advanced applications that will be of interest to experts in the area.

Author Biography

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.

Table of Contents

Preface xxv

Acknowledgments xxvii

Acronyms xxix

Introduction iii

1 Basic Definitions 1

1.1 Notations 1

1.2 Finite Fields 5

1.2.1 A Residue Class Ring 5

1.2.2 Properties of Finite Fields 7

1.2.3 Traces and Norms 8

1.2.4 Characters of Finite Fields 12

1.3 Group Rings and Their Characters 16

1.4 Type 1 and Type 2 Matrices 17

1.5 Hadamard Matrices 25

1.5.1 Definition and Properties of an Hadamard Matrix 25

1.5.2 Kronecker Product and the Sylvester Hadamard Matrices 31

1.5.3 Inequivalence Classes 36

1.6 Paley Core Matrices 36

1.7 Amicable Hadamard Matrices 40

1.8 The Additive Property and Four Plug-in Matrices 46

1.8.1 Computer Construction 48

1.8.2 Skew Hadamard Matrices 48

1.8.3 Symmetric Hadamard Matrices 49

1.9 Difference Sets, SDS and Partial Difference Sets 51

1.9.1 Difference Sets 51

1.9.2 Supplementary Difference Sets 54

1.9.3 Partial Difference Sets 57

1.10 Sequences and Autocorrelation Function 59

1.10.1 Multiplication of NPAF Sequences 63

1.10.2 Golay Sequences 65

1.11 Excess 68

1.12 Balanced Incomplete Block Designs 70

1.13 Hadamard Matrices and SBIBDs 73

1.14 Cyclotomic Numbers 75

The case where e = 2 76

The case where e = 4 and f is even 77

The case where e = 4 and f is odd 78

The case where e = 8 and f is odd 79

The case where e = 8 and f is even 81

1.15 Orthogonal Designs and Weighing Matrices 83

1.16 T -matrices, T -sequences and Turyn Sequences 84

1.16.1 Turyn Sequences 86

2 Gauss Sums, Jacobi Sums and Relative Gauss Sums 89

2.1 Notations 89

2.2 Gauss Sums 89

2.3 Jacobi Sums 93

2.3.1 Congruence Relations 94

2.3.2 Jacobi Sums of Order 4 95

2.3.3 Jacobi Sums of Order 8 101

2.4 Cyclotomic Numbers and Jacobi Sums 106

2.4.1 Cyclotomic Numbers for e = 2 110

2.4.2 Cyclotomic Numbers for e = 4 111

2.4.3 Cyclotomic Numbers for e = 8 113

2.5 Relative Gauss Sums 120

2.6 Prime Ideal Factorization of Gauss Sums 126

2.6.1 Prime Ideal Factorization of a Prime p 126

2.6.2 Stickelberger’s Theorem 126

2.6.3 Prime Ideal Factorization of the Gauss Sum in Q(ζq−1) 128

2.6.4 Prime Ideal Factorization of the Gauss Sums in Q(ζm) 130

3 Plug-In Matrices 133

3.1 Notations 133

3.2 Williamson Type and Williamson Matrices 135

3.3 Plug-in Matrices 143

3.3.1 The Ito Array 144

3.3.2 Good Matrices : a Variation of Williamson Matrices 144

3.3.3 The Goethals-Seidel Array 146

3.3.4 Symmetric Hadamard Variation 146

3.4 Eight Plug-in Matrices 147

3.4.1 The Kharaghani Array 148

3.5 More T -sequences and T -matrices 149

3.6 Construction of T -matrices of Order 6m+ 1 153

3.7 Williamson Hadamard Matrices and Paley Type II Hadamard Matrices 159

3.7.1 Whiteman’s Construction 159

3.7.2 Williamson Equation from Relative Gauss Sums 164

3.8 Hadamard Matrices of Generalized Quaternion Type 169

3.8.1 Definitions 169

3.8.2 Paley Core Type I Matrices 172

3.8.3 Hadamard Matrices of GQ Type and Relative Gauss Sums 172

3.9 Supplementary Difference Sets and Williamson Matrices 174

3.9.1 Supplementary Difference Sets from Cyclotomic Classes 174

3.9.2 Constructions of an Hadamard 4-sds 177

3.9.3 Construction from (q; x, y)-Partitions 183

3.10 Relative DS and Williamson-Type Matrices over Abelian Groups 191

3.11 Computer Construction of Williamson Matrices 196

4 Arrays: Matrices to Plug-Into 199

4.1 Notations 199

4.2 Orthogonal Designs 200

4.2.1 Baumert-Hall Arrays and Welch Arrays 201

4.3 Welch and Ono-Sawade-Yamamoto Arrays 210

4.4 Regular Representation of a Group and BHW(G) 212

5 Sequences 217

5.1 Notations 217

5.2 PAF and NPAF 219

5.3 Suitable Single Sequences 220

5.3.1 On Circulant Hadamard matrices for Orders >4 220

5.3.2 SBIBD Implications 221

5.3.3 From ±1 Matrices to ±A, ±B Matrices 222

5.3.4 Matrix Specifics 224

5.3.5 Counting Two Ways 225

5.3.6 For m Odd: Orthogonal Design Implications 227

5.3.7 The Case for Order 16 228

5.4 Suitable Pairs of NPAF Sequences: Golay Sequences 229

5.5 Current Results for Golay Pairs 229

5.6 Recent Results for Periodic Golay Pairs 232

5.7 More on Four Complementary Sequences 232

5.8 6-Turyn-type Sequences 237

5.9 Base Sequences 238

5.10 Yang-Sequences 240

5.10.1 On Yang’s Theorems on T -sequences 247

5.10.2 Multiplying by 2g + 1, g the Length of a Golay Sequence 248

5.10.3 Multiplying by 7 and 13 249

5.10.4 Koukouvinos and Kounias Number 251

6 M-structures 257

6.1 Notations 257

6.2 The Strong Kronecker Product 258

6.3 Reducing the Powers of Two 261

6.4 Multiplication Theorems Using M-structures 265

6.5 Miyamoto’s Theorem and Corollaries via M-structures 269

7 Menon Hadamard Difference Sets 283

7.1 Notations 283

7.2 Menon Hadamard Difference Sets and Exponent Bound 285

7.3 Menon Hadamard Difference Sets and Relative Hadamard Matrices 286

7.4 The Constructions from Cyclotomy 288

7.5 The Constructions Using Projective Sets 294

7.5.1 Graphical Hadamard Matrices 301

7.6 The Construction Based on Galois Rings 303

7.6.1 Galois Rings 303

7.6.2 Additive Characters of Galois Rings 304

7.6.3 A New Operation 306

7.6.4 Gauss Sums over GR(2ⁿ⁺¹, s) 306

7.6.5 Menon Hadamard Difference Sets over GR(2ⁿ⁺¹, s) 307

7.6.6 Menon Hadamard Difference Sets over GR(2², s) 309

8 Paley Hadamard Difference Sets and Partial Difference Sets 311

8.1 Notations 311

8.2 Paley Core Matrices and Gauss Sums 313

8.3 Paley Hadamard Difference Sets 317

8.3.1 Stanton-Sprott Difference Sets 318

8.3.2 Paley Hadamard Difference Sets and Relative Gauss Sums 320

8.3.3 Gordon-Mills-Welch Extension 323

8.4 Paley Type Partial Difference Set 324

8.5 Paley Type PDS from EBS 326

8.6 Constructing Paley Hadamard Difference Sets 341

9 Skew Hadamard, Amicable and Symmetric Matrices 345

9.1 Notations 345

9.2 Introduction 346

9.3 Skew Hadamard Matrices 347

9.3.1 Summary of Skew Hadamard Orders 347

9.4 Constructions for Skew Hadamard Matrices 349

9.4.1 The Goethals-Seidel Type 352

9.4.2 An Adaption of Wallis–Whiteman Array 353

9.5 Szekeres Difference Sets 359

9.5.1 The Construction by Cyclotomic Numbers 362

9.6 Amicable Hadamard Matrices 365

9.7 Amicable Cores 370

9.8 Construction for Amicable Hadamard Matrices of Order 2^t 372

9.9 Construction of Amicable Hadamard Matrices Using Cores 374

9.10 Symmetric Hadamard Matrices 378

9.10.1 Symmetric Hadamard Matrices via Computer Construction 379

9.10.2 Luchshie Matrices Known Results 380

10 Skew Hadamard Difference Sets 383

10.1 Notations 383

10.2 Skew Hadamard Difference Sets 383

10.3 The Construction by Planar Functions over a Finite Field 385

10.3.1 Planar Functions and Dickson Polynomials 385

10.4 The Construction by Using Index 2 Gauss Sums 388

10.4.1 Index 2 Gauss Sums 388

10.4.2 The Case that p1 ≡ 7 (mod 8) 390

10.4.3 The Case that p1 ≡ 3 (mod 8) 394

Case 1 396

Case 2 396

Case 3 396

Case 4 397

Case 5 397

10.5 The Construction by using Normalized Relative Gauss Sums 402

10.5.1 More on Ideal Factorization of the Gauss Sum 402

10.5.2 Determination of Normalized Relative Gauss Sums 403

10.5.3 A Family of Skew Hadamard Difference Sets 407

11 Asymptotic Existence of Hadamard Matrices 411

11.1 Notations 411

11.2 Introduction 412

11.2.1 de Launey’s Theorem 412

11.3 Seberry’s Theorem 412

11.4 Craigen’s Theorem 413

11.4.1 Signed Groups and Their Representations 414

11.4.2 A Construction for Signed Group Hadamard Matrices 417

11.4.3 A Construction for Hadamard Matrices 421

11.4.4 Comments on Orthogonal Matrices Over Signed Groups 424

11.4.5 Some Calculations 426

11.5 More Asymptotic Theorems 431

11.6 Skew Hadamard and Regular Hadamard 431

12 More on Maximal Determinant Matrices 433

12.1 Notations 433

12.2 E-Equivalence: The Smith Normal Form 434

12.3 E-Equivalence: The Number of Small Invariants 438

12.4 E-Equivalence: Skew Hadamard and Symmetric Conference Matrices 443

12.5 Smith Normal Form for Powers of 2 446

12.6 Matrices with Elements (1,−1) and Maximal Determinant 448

12.7 D-optimal Matrices Embedded in Hadamard Matrices 449

12.7.1 Embedding of D₅ in H₈ 451

12.7.2 Embedding of D₆ in H₈ 451

12.7.3 Embedding of D₇ in H₈ 452

12.7.4 Other Embeddings 453

12.8 Embedding of Hadamard Matrices within Hadamard Matrices 455

12.9 Embedding Properties via Minors 456

12.10Embeddability of Hadamard Matrices 459

12.11Embeddability of Hadamard Matrices of Order n − 8 461

12.12Embeddability of Hadamard Matrices of Order n − k 464

12.12.1Embeddability—Extendability of Hadamard Matrices 467

12.12.2Available Determinant Spectrum and Verification 468

12.13Growth Problem for Hadamard Matrices 472

The Pivot Structure of H₈ 474

The Pivot Structure of H₁₂ 475

The Pivot Structure of H₁₆ 476

A Hadamard Matrices 479

A.1 Hadamard Matrices 479

A.1.1 Amicable Hadamard Matrices 479

A.1.2 Skew Hadamard Matrices 480

A.1.3 Spence Hadamard Matrices 480

A.1.4 Conference Matrices Give Symmetric Hadamard Matrices 481

A.1.5 Hadamard Matrices from Williamson Matrices 481

A.1.6 OD Hadamard Matrices 481

A.1.7 Yamada Hadamard Matrices 482

A.1.8 Miyamoto Hadamard Matrices 482

A.1.9 Koukouvinos and Kounias 483

A.1.10 Yang Numbers 483

A.1.11 Agaian Multiplication 483

A.1.12 Craigen-Seberry-Zhang 483

A.1.13 de Launey 483

A.1.14 Seberry/Craigen Asymptotic Theorems 484

A.1.15 Yang’s Theorems and okovi´c updates 484

A.1.16 Computation by okovi´c 484

A.2 Index of Williamson Matrices 486

A.3 Tables of Hadamard Matrices 499

B List of sds from Cyclotomy 515

B.1 Introduction 515

B.2 List of n − {q; k₁, , k_n: λ} sds. 515

C Further Research Questions 525

C.1 Research Questions for Future Investigation 525

C.1.1 Matrices 525

C.1.2 Base Sequences 525

C.1.3 Partial Difference Sets 526

C.1.4 de Launey’s Four Questions 526

C.1.5 Embedding Sub-matrices 527

C.1.6 Pivot Structures 527

C.1.7 Trimming and Bordering 527

C.1.8 Arrays 527

Index 553