Hadamard Matrices and Their Applications

In Hadamard Matrices and Their Applications, K. J. Horadam provides the first unified account of cocyclic Hadamard matrices and their applications in signal and data processing. This original work is based on the development of an algebraic link between Hadamard matrices and the cohomology of finite groups that was discovered fifteen years ago. The book translates physical applications into terms a pure mathematician will appreciate, and theoretical structures into ones an applied mathematician, computer scientist, or communications engineer can adapt and use.





The first half of the book explains the state of our knowledge of Hadamard matrices and two important generalizations: matrices with group entries and multidimensional Hadamard arrays. It focuses on their applications in engineering and computer science, as signal transforms, spreading sequences, error-correcting codes, and cryptographic primitives.





The book's second half presents the new results in cocyclic Hadamard matrices and their applications. Full expression of this theory has been realized only recently, in the Five-fold Constellation. This identifies cocyclic generalized Hadamard matrices with particular "stars" in four other areas of mathematics and engineering: group cohomology, incidence structures, combinatorics, and signal correlation.





Pointing the way to possible new developments in a field ripe for further research, this book formulates and discusses ninety open questions.

Preface xi Chapter 1. Introduction 1 PART 1. HADAMARD MATRICES, THEIR APPLICATIONS AND GENERALISATIONS 7 Chapter 2. Hadamard Matrices 9 2.1 Classical Constructions 10 2.1.1 Sylvester Hadamard matrices 11 2.1.2 Paley Hadamard matrices 11 2.1.3 Hadamard designs 12 2.1.4Williamson Hadamard matrices 15 2.2 Equivalence Classes 16 2.3 The First Link: Group Developed Constructions 20 2.3.1 Menon Hadamard matrices 21 2.3.2 Ito Hadamard matrices 23 2.4 Towards the Hadamard Conjecture 25 Chapter 3. Applications in Signal Processing, Coding and Cryptography 27 3.1 Spectroscopy: Walsh-Hadamard Transforms 28 3.1.1 Signal analysis and synthesis 28 3.1.2 The Walsh-Hadamard Transform 29 3.1.3 The Fast Hadamard Transform 33 3.1.4 Hadamard spectroscopy 33 3.2 Error Correction: Hadamard Codes 35 3.2.1 Error-correcting codes 36 3.2.2 Hadamard codes 39 3.3 Signal Modulation and Separation: Hadamard Codes 43 3.3.1 CDMA for mobile, wireless and optical communications 45 3.3.2 3-D holographic memory for data storage and retrieval 47 3.4 Signal Correlation: Perfect Sequences and Arrays 48 3.4.1 Timing and synchronisation: Perfect binary sequences 49 3.4.2 Signal array correlation: Perfect binary arrays 50 3.5 Cryptography: Nonlinear Functions 53 3.5.1 Binary bent functions and maximally nonlinear functions 55 3.5.2 Perfect and almost perfect nonlinear functions 59 Chapter 4. Generalised Hadamard Matrices 62 4.1 Butson Matrices 63 4.2 Complex Hadamard Matrices 66 4.2.1 Quaternary complex Hadamard matrices 67 4.2.2 Unimodular complex Hadamard matrices 69 4.3 Generalised Hadamard Matrices 70 4.3.1 Generalised Hadamard matrix constructions 71 4.3.2 Generalised Hadamard matrices and Butson matrices 73 4.3.3 Generalised Hadamard matrices and class regular divisible designs 74 4.3.4 Group developed GH(w; v=w) and semiregular relative difference sets 75 4.4 Applications of Complex and Generalised Hadamard Matrices 78 4.4.1 Quaternary complex Hadamard transforms 78 4.4.2 Perfect quaternary sequences and arrays 79 4.4.3 Quaternary error-correcting codes 81 4.4.4 Generalised Hadamard matrices and Hadamard codes 83 4.5 Unification: Generalised Butson Hadamard Matrices and Transforms 84 4.5.1 The jacket matrix construction 85 4.5.2 The Generalised Hadamard Transform 90 Chapter 5. Higher Dimensional Hadamard Matrices 92 5.1 Classical Constructions 94 5.1.1 Boolean function construction for order 2 95 5.1.2 Product construction 97 5.1.3 Group developed construction 97 5.1.4 Perfect binary array construction 98 5.2 Equivalence Classes 99 5.3 Applications in Spectroscopy, Coding and Cryptography 100 5.3.1 Multidimensional Walsh Hadamard transforms 101 5.3.2 Error-correcting array codes 102 5.3.3 Cryptography: bent functions and the strict avalanche criterion 105 5.4 The Second Link: Cocyclic Construction 106 PART 2. COCYCLIC HADAMARD MATRICES 111 Chapter 6. Cocycles and Cocyclic Hadamard Matrices 113 6.1 Cocycles and Group Cohomology 114 6.2 Cocycles are Everywhere! 116 6.2.1 Examples of cocycles 116 6.2.2 New from old 117 6.2.3 Characteristic properties 119 6.2.4 Orthogonality and its inheritance 121 6.3 Computation of Cocycles 122 6.3.1 Algorithm 1-- abelian groups 124 6.3.2 Algorithm 2-- MAGMA implementation 126 6.3.3 Algorithm 3-- Homological perturbation 127 6.4 Cocyclic Hadamard Matrices 128 6.4.1 Sylvester Hadamard matrices 128 6.4.2 Menon Hadamard matrices 129 6.4.3Williamson Hadamard matrices 129 6.4.4 Ito Hadamard matrices 129 6.4.5 Generalisations of Ito Hadamard matrices 130 6.4.6 Numerical results 131 6.5 The Cocyclic Hadamard Conjecture 133 6.5.1 Noncocyclic Hadamard matrix constructions? 134 6.5.2 Status report--research problems in cocyclic Hadamard matrices 137 Chapter 7. The Five-fold Constellation 139 7.1 Factor Pairs and Extensions 139 7.2 Orthogonality for Factor Pairs 143 7.3 All the Cocyclic Generalised Hadamard Matrices 146 7.3.1 Cocyclic generalised Hadamard matrix constructions 149 7.4 The Five-fold Constellation 151 7.4.1 Restrictions on existence of cocyclic generalised Hadamard matrices 158 7.4.2 Two approaches 160 Chapter 8. Bundles and Shift Action 162 8.1 Bundles and the Five-fold Constellation 163 8.1.1 Equivalence of transversals 163 8.1.2 Bundles of factor pairs 165 8.2 Bundles of Functions--The Splitting Case 170 8.3 Bundles of Cocycles--The Central Case 174 8.3.1 Automorphism action versus shift action 174 8.3.2 A taxonomy for central semiregular RDSs 176 8.3.3 Bundles with trivial shift action--the multiplicative cocycles 178 8.4 Shift Action--The Central Case 181 8.4.1 Orbit structure for cyclic groups 184 8.4.2 Relationship between orbit structures in distinct cohomology classes 185 8.5 Shift Orbits--The Central Splitting Case 185 8.5.1 When C is an elementary abelian p-group 187 8.5.2 When C is an elementary abelian p-group and G is a p-group 188 Chapter 9. The Future: Novel Constructions and Applications 192 9.1 New Applications of Cocycles 192 9.1.1 Computation in Galois rings 192 9.1.2 Elliptic curve cryptosystems 195 9.1.3 Cocyclic codes 197 9.1.4 Cocyclic Butson matrices and codes 202 9.2 New Group Developed Generalised Hadamard Matrices 204 9.2.1 Group developed GH matrices and PN functions 204 9.2.2 PN functions and a theory of highly nonlinear functions 208 9.3 New Cocyclic Generalised Hadamard Matrices 212 9.3.1 Direct sum constructions 212 9.3.2 Multiplicative orthogonal cocycles and presemifields 216 9.3.3 Swing action 224 9.4 New Hadamard Codes 225 9.4.1 Class A cocyclic Hadamard codes 225 9.4.2 Class B cocyclic Hadamard codes 227 9.4.3 Class C cocyclic Hadamard codes 229 9.5 New Highly Nonlinear Functions 230 9.5.1 1-D differential uniformity 230 9.5.2 Differential 2-row uniformity and APN functions 233 9.5.3 2-D total differential uniformity 235 Bibliography 238 Index 259