Mathematics – Combinatorics
Scientific paper
2011-03-14
Mathematics
Combinatorics
43 pages, no figures; substantially improved version. Some improvements are: Generalized graph-theoretical characterization of
Scientific paper
This is to suggest a new approach to the old and open problem of counting the number f_n 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 P_chio 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 P_lcf 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 P_lcf and fully independent (they are not when governed by P_chio), then an asymptotically optimal bound on the singularity probability over Z can be proved. We will characterize P_chio graph-theoretically and use the characterization to prove that given a B in {-1,0,+1}^([n-1]^2), deciding whether P_chio[B] = P_lcf[B] is equivalent to deciding an evasive graph property, hence the time complexity of this decision is Omega(n^2). Moreover, we will prove k-wise independence properties of P_chio. Many questions suggest themselves that call for further work. In particular, the present paper will close with more constrained equivalent formulations of the conjecture f_n/2^(n^2) ~ (1/2 + o(1))^n.
No associations
LandOfFree
Chio Condensation and Random Sign Matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Chio Condensation and Random Sign Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chio Condensation and Random Sign Matrices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-259928