Rank deficiency in sparse random GF[2] matrices

作者：Darling R W R^*; Penrose Mathew D; Wade Andrew R; Zabell Sandy L

来源：Electronic Journal of Probability, 2014, 19(0): 83.

DOI：10.1214/EJP.v19-2458

• Random sparse matrix
• null vector
• hypercycle
• random allocation
• XORSAT
• phase transition
• hypergraph core
• large deviations
• Ehrenfest model

Let M be a random m x 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 -%26gt; infinity , with m/n -%26gt; alpha %26gt; 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. %26lt;br%26gt;We identify two thresholds alpha* and (alpha) under bar 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 E [N(n, m)] converges to a positive limit, while (alpha) under bar 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. %26lt;br%26gt;We have 1/2 %26lt;= alpha* %26lt;= (alpha) under bar %26lt;= 1, and typically these inequalities are strict; for example when W = 3 almost surely, alpha* approximate to 0.8895 and (alpha) under bar approximate to 0.9179. The threshold of values of alpha for which N(n, m) %26gt;= 2 in probability lies in [alpha*, (alpha) under bar] and is conjectured to equal (alpha) under bar. 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.

• 出版日期2014-9-14
• 单位西北大学