Richard W.R. Darling
Rank deficiency in sparse random GF[2] matrices
Darling, Richard W.R.; Penrose, Mathew D.; Wade, Andrew R.; Zabell, Sandy L.
Abstract
Let M be a random m×n matrix with binary entries and i.i.d. rows. The weight (i.e., number of ones) of a row has a specified probability distribution, with the row chosen uniformly at random given its weight. Let N(n,m) denote the number of left null vectors in {0,1}m for M (including the zero vector), where addition is mod 2. We take n,m→∞, with m/n→α>0, while the weight distribution converges weakly to that of a random variable W on {3,4,5,…}. Identifying M with a hypergraph on n vertices, we define the 2-core of M as the terminal state of an iterative algorithm that deletes every row incident to a column of degree 1. We identify two thresholds α∗ and α−, and describe them analytically in terms of the distribution of W. Threshold α∗ marks the infimum of values of α at which n−1logE[N(n,m)] converges to a positive limit, while α− marks the infimum of values of α at which there is a 2-core of non-negligible size compared to n having more rows than non-empty columns. We have 1/2≤α∗≤α−≤1, and typically these inequalities are strict; for example when W=3 almost surely, α∗≈0.8895 and α−≈0.9179. The threshold of values of α for which N(n,m)≥2 in probability lies in [α∗,α−] and is conjectured to equal α−. The random row-weight setting gives rise to interesting new phenomena not present in the case of non-random W that has been the focus of previous work.
Citation
Darling, R. W., Penrose, M. D., Wade, A. R., & Zabell, S. L. (2014). Rank deficiency in sparse random GF[2] matrices. Electronic Journal of Probability, 19, Article 83. https://doi.org/10.1214/ejp.v19-2458
Journal Article Type | Article |
---|---|
Acceptance Date | Sep 4, 2014 |
Online Publication Date | Sep 14, 2014 |
Publication Date | Sep 14, 2014 |
Deposit Date | Oct 5, 2014 |
Publicly Available Date | Oct 6, 2014 |
Journal | Electronic Journal of Probability |
Publisher | Institute of Mathematical Statistics |
Peer Reviewed | Peer Reviewed |
Volume | 19 |
Article Number | 83 |
DOI | https://doi.org/10.1214/ejp.v19-2458 |
Files
Published Journal Article
(741 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
This work is licensed under a Creative Commons Attribution 3.0 License (CC BY 3.0).
You might also like
Iterated-logarithm laws for convex hulls of random walks with drift
(2023)
Journal Article
Passage-times for partially-homogeneous reflected random walks on the quadrant
(2023)
Journal Article
Deposition, diffusion, and nucleation on an interval
(2022)
Journal Article
Cutpoints of non-homogeneous random walks
(2022)
Journal Article
Reflecting random walks in curvilinear wedges
(2021)
Book Chapter
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search