Combinatorics of Complex Maximal Determinant Matrices

Nunez, Guillermo

Etd

Combinatorics of Complex Maximal Determinant Matrices

Public Deposited

In this dissertation, we study a wide range of topics in algebraic combinatorics. In the first part, we give an introduction to the arithmetic theory of quadratic forms aimed toward combinatorialists, and give new proofs of two classical non-existence results for combinatorial designs: the Bruck-Ryser-Chowla Theorem and the Bose-Connor Theorem. We unify both proofs using techniques from the theory of association schemes. Then we turn to the theory of Hermitian forms, and its applications in combinatorics. Here, we obtain new non-existence results for certain classes of complex Hadamard matrices. The second part of this dissertation is devoted to complex maximal determinant matrices. Here we survey Butson-type Hadamard matrices: we include (1) a discussion of an unpublished construction of de Launey on Butson-type matrices over the third roots, (2) a morphism from a non-Butson class of Hadamard matrices to real Hadamard matrices, and (3) an improvement on the asymptotic existence results of de Launey and Dawson for BH(12p,p) matrices. In particular, we reduce the lower bound on p from 104857600 to 263. Then we turn to the main original contribution of this dissertation, which consists of a study of the maximal determinant of matrices with entries over the complex roots of unity. We identify the cases of the third and fourth roots of unity as particularly interesting, and for this reason, we study them in detail. Among the results presented, we give upper and lower bounds for the determinant, an infinite family of maximal determinant matrices over the fourth roots, and a study of maximal determinant matrices of small order. We also discuss a computational method, using Gröbner bases, to find maximal determinant matrices over the Bose-Mesner algebra of an association scheme. The last part of this dissertation includes an application of finite geometry to privacy in communications: we consider the problem of user-private information retrieval (UPIR) and show that the previously considered schemes, based on projective planes, are vulnerable to a coalition of users of bounded size. We propose instead a scheme based on generalized quadrangles, which improves significantly on the degree of privacy provided.

Creator