A Fourier-analytic approach to counting partial Hadamard matrices

DOI10.1007/S12095-010-0033-ZMaRDI QIDQ601111zbMATH OpenOpenAlexFDO

Authors David A. Levin, Warwick de Launey

Publication date 3 November 2010

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

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

zbMATH Keywords

partial Hadamard matricesrandom walks

Mathematics Subject Classification ID

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

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.

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

Cites work

• A comment on the Hadamard conjecture
• Asymptotic enumeration by degree sequence of graphs of high degree
• Asymptotic enumeration of correlation-immune Boolean functions
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• scientific article; zbMATH DE number 3560403 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• On RSA moduli with almost half of the bits prescribed
• Signed groups, sequences, and the asymptotic existence of Hadamard matrices

Cited in

(13)

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

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)