Application of the Discrete Fourier Transform to the Search for Generalised Legendre Pairs and Hadamard Matrices

We introduce Legendre sequences and generalised Legendre pairs (GL-pairs). We show how to construct a Hadamard matrix of order 2ℓ + 2 from a GL—pair of length ℓ. We review the known constructions for GL-pairs and use the discrete Fourier transform (DFT) and power spectral density (PSD) to enable an exhaustive search for GL-pairs for lengths ℓ ≤ 45 and partial results for other ℓ.