A Fourier-analytic approach to counting partial Hadamard matrices

DOI10.1007/S12095-010-0033-ZzbMATH Open1225.05056arXiv1003.4003OpenAlexW1996500474MaRDI QIDQ601111FDOQ601111

Authors: David A. Levin, Warwick de Launey 

Publication date: 3 November 2010

Published in: Cryptography and Communications (Search for Journal in Brave)

Abstract: In this paper, we study a family of lattice walks which are related to the Hadamard conjecture. There is a bijection between paths of these walks which originate and terminate at the origin and equivalence classes of partial Hadamard matrices. Therefore, the existence of partial Hadamard matrices can be proved by showing that there is positive probability of a random walk returning to the origin after a specified number of steps. Moreover, the number of these designs can be approximated by estimating the return probabilities. We use the inversion formula for the Fourier transform of the random walk to provide such estimates. We also include here an upper bound, derived by elementary methods, on the number of partial Hadamard.

Full work available at URL: https://arxiv.org/abs/1003.4003

Recommendations

• On the asymptotic existence of partial complex Hadamard matrices and related combinatorial objects
• Analytic aspects of the circulant Hadamard conjecture
• Generating binary partial Hadamard matrices
• A Walsh-Fourier approach to the circulant Hadamard conjecture
• On the existence of complex Hadamard submatrices of the Fourier matrices

zbMATH Keywords

random walkspartial Hadamard matrices

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Boolean and Hadamard matrices (15B34) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Orthogonal matrices (15B10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic enumeration by degree sequence of graphs of high degree
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• Asymptotic enumeration of correlation-immune Boolean functions
• On RSA moduli with almost half of the bits prescribed
• Signed groups, sequences, and the asymptotic existence of Hadamard matrices
• A comment on the Hadamard conjecture

Cited In (13)

• Probabilistic existence of regular combinatorial structures
• Analytic aspects of the circulant Hadamard conjecture
• Counting results for thin Butson matrices
• A practical algorithm for completing half-Hadamard matrices using LLL
• The Hunt for Weighing Matrices of Small Orders
• Generating binary partial Hadamard matrices
• Optimal quantum tomography with constrained measurements arising from unitary bases
• Connecting unextendible maximally entangled base with partial Hadamard matrices
• On the number of Hadamard matrices via anti-concentration
• Asymptotic enumeration of difference matrices over cyclic groups
• Structured Hadamard conjecture
• The quantum algebra of partial Hadamard matrices
• Part-Frequency Matrices, II: Recent Work

This page was built for publication: A Fourier-analytic approach to counting partial Hadamard matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q601111)