2011/03/14 by Peter Heinig, Heinig, Peter Christian
Mathematics · #05C22 #11C20 #15B35 #15B52 #5C50 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.1103.2717
openalex publication_date 2011/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This is to suggest a new approach to the old and open problem of counting the number fn of Z-singular n x n matrices with entries from -1,+1: Comparison of two measures, none of them the uniform measure, one of them closely related to it, the other asymptotically under control by a recent theorem of Bourgain, Vu and Wood. We will define a measure Pchio on the set -1,0,+1^([n-1]2) of all (n-1)x(n-1)-matrices with entries from -1,0,+1 which (owing to a determinant identity published by M. F. Chio in 1853) is closely related to the uniform measures on -1,+1^([n]2) and 0,1^([n-1]2) and at the same time it intriguingly mimics the so-called lazy coin flip distribution Plcf on -1,0,+1^([n-1]2), with the resemblance fading more and more as the events get smaller. This is relevant in view of a recent theorem of J. Bourgain, V. H. Vu and P. M. Wood (J. Funct. Anal. 258 (2010), 559--603) which proves that if the entries of an n x n matrix whose -1,0,+1-entries are governed by Plcf and fully independent (they are not when governed by Pchio), then an asymptotically optimal bound on the singularity probability over Z can be proved. We will characterize Pchio graph-theoretically and use the characterization to prove that given a B in -1,0,+1^([n-1]2), deciding whether Pchio[B] = Plcf[B] is equivalent to deciding an evasive graph property, hence the time complexity of this decision is Omega(n2). Moreover, we will prove k-wise independence properties of Pchio. Many questions suggest themselves that call for further work. In particular, the present paper will close with more constrained equivalent formulations of the conjecture fn/2^(n2) ~ (1/2 + o(1))n.