Rank deficiency in sparse random GF$[2]$ matrices

Richard W. R. Darling (National Security Agency)
Mathew D. Penrose (University of Bath)
Andrew R. Wade (University of Durham)
Sandy L. Zabell (Northwestern University)

Abstract


Let $M$ be a random $m \times 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 $\mathcal{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 \to \infty$, with $m/n \to \alpha > 0$, while the weight distribution converges weakly to that of a random variable $W$ on $\{3, 4, 5, \ldots\}$. 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 $\alpha^*$ and $\underline{\alpha\mkern-4mu}\mkern4mu$, and describe them analytically in terms of the distribution of $W$. Threshold $\alpha^*$ marks the infimum of values of $\alpha$ at which $n^{-1} \log{\mathbb{E}[\mathcal{N} (n,m)}]$ converges to a positive limit, while $\underline{\alpha\mkern-4mu}\mkern4mu$ marks the infimum of values of $\alpha$ 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 \leq \alpha^* \leq \underline{\alpha\mkern-4mu}\mkern4mu \leq 1$, and typically these inequalities are strict; for example when $W = 3$ almost surely, $\alpha^* \approx 0.8895$ and $\underline{\alpha\mkern-4mu}\mkern4mu \approx 0.9179$. The threshold of values of $\alpha$ for which $\mathcal{N}(n,m) \geq 2$ in probability lies in $[\alpha^*,\underline{\alpha\mkern-4mu}\mkern4mu]$ and is conjectured to equal $\underline{\alpha\mkern-4mu}\mkern4mu$. 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.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-36

Publication Date: September 14, 2014

DOI: 10.1214/EJP.v19-2458

References

  • Alamino, R. C.; Saad, D. Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach. Phys. Rev. E (3) 77 (2008), no. 6, 061123, 12 pp. MR2496138
  • Balakin, G. V.; Kolchin, V. F.; Khokhlov, V. I. Hypercycles in a random hypergraph. (Russian) Diskret. Mat. 3 (1991), no. 3, 102--108; translation in Discrete Math. Appl. 2 (1992), no. 5, 563--570 MR1138095
  • Calkin, N. J. Dependent sets of constant weight binary vectors. Combin. Probab. Comput. 6 (1997), no. 3, 263--271. MR1464565
  • Cooper, C. Asymptotics for dependent sums of random vectors. Random Structures Algorithms 14 (1999), no. 3, 267--292. MR1680224
  • Cooper, C. The cores of random hypergraphs with a given degree sequence. Random Structures Algorithms 25 (2004), no. 4, 353--375. MR2099209
  • Costello, K. P.; Vu, V. On the rank of random sparse matrices. Combin. Probab. Comput. 19 (2010), no. 3, 321--342. MR2607371
  • Darling, R. W. R.; Levin, D. A.; Norris, J. R. Continuous and discontinuous phase transitions in hypergraph processes. Random Structures Algorithms 24 (2004), no. 4, 397--419. MR2060628
  • Darling, R. W. R.; Norris, J. R. Structure of large random hypergraphs. Ann. Appl. Probab. 15 (2005), no. 1A, 125--152. MR2115039
  • Darling, R. W. R.; Norris, J. R. Differential equation approximations for Markov chains. Probab. Surv. 5 (2008), 37--79. MR2395153
  • Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R. and Rink, M.: Tight thresholds for cuckoo hashing via XORSAT. Proc. 37th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 2010, Volume 6198/2010, Springer, pp. 213--225.
  • Dubois, O.; Mandler, J. The 3-XORSAT threshold. C. R. Math. Acad. Sci. Paris 335 (2002), no. 11, 963--966. MR1952558
  • Feller, W. An Introduction to Probability Theory and Its Applications. Vol. I. Third edition John Wiley & Sons, Inc., New York-London-Sydney 1968 xviii+509 pp. MR0228020
  • Ibrahimi, M., Kanoria, Y., Kraning, M. and Montanari, A.: The set of solutions of random XORSAT formulae. SODA `12 Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, pp. 760--779.
  • Kolchin, V. F.: Cycles in random graphs and hypergraphs (abstract). Adv. in Appl. Probab. 24, (1992), 768.
  • Kolchin, V. F. Random graphs and systems of linear equations in finite fields. Proceedings of the Fifth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science (Poznań, 1991). Random Structures Algorithms 5 (1994), no. 1, 135--146. MR1248181
  • Kolchin, V. F. Random Graphs. Cambridge University Press, Cambridge, 1999. xii+252 pp. ISBN: 0-521-44081-5 MR1728076
  • Kolchin, V. F.; Sevastʹyanov, B. A.; Chistyakov, V. P. Random Allocations. Translated from the Russian. Translation edited by A. V. Balakrishnan. V. H. Winston & Sons, Washington, D.C. 1978. xi+262 pp. ISBN: 0-470-99394-4 MR0471016
  • Kovalenko, I. N.; Levitskaya, A. A. Stochastic properties of systems of random linear equations over finite algebraic structures. Probabilistic methods in discrete mathematics (Petrozavodsk, 1992), 64--70, Progr. Pure Appl. Discrete Math., 1, VSP, Utrecht, 1993. MR1383129
  • Levitskaya, A. A. Systems of random equations over finite algebraic structures. (Russian) Kibernet. Sistem. Anal. 41 (2005), no. 1, 82--116, 190; translation in Cybernet. Systems Anal. 41 (2005), no. 1, 67--93 MR2188375
  • Mahmoud, H. M. Pólya Urn Models. CRC Press, Boca Raton, FL, 2009. xii+290 pp. ISBN: 978-1-4200-5983-0 MR2435823
  • Mézard, M., Parisi, G. and Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297 (2002), 812--815.
  • Muetze, T. Generalized switch-setting problems. Discrete Math. 307 (2007), no. 22, 2755--2770. MR2362960
  • Talagrand, M. Spin Glasses: A Challenge for Mathematicians. Springer-Verlag, Berlin, 2003. x+586 pp. ISBN: 3-540-00356-8 MR1993891


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.