Finding Hadamard and (epsilon,delta)-Quasi-Hadamard Matrices with Optimization Techniques

Abstract

Existence problems (proving that a set is nonempty) abound in mathematics, so we look for generally applicable solutions (such as optimization techniques). To test and improve these techniques, we apply them to the Hadamard Conjecture (proving that Hadamard matrices exist in dimensions divisible by 4), which is a good example to study since Hadamard matrices have interesting applications (communication theory, quantum information theory, experiment design, etc.), are challenging to find, are easily distinguished from other matrices, are known to exist for many dimensions, etc.. In this thesis we study optimization algorithms (Exhaustive search, Hill Climbing, Metropolis, Gradient methods, generalizations thereof, etc.), improve their performance (when using a Graphical Processing Unit), and use them to attempt to find Hadamard matrices (real, and complex). Finally, we give an algorithm to prove non-trivial lower bounds on the Hamming distance between any given matrix with elements in {+1,-1} and the set of Hadamard matrices, then we use this algorithm to study matrices with similar properties to Hadamard matrices, but which are far away (with respect to the Hamming distance) from them.