Loading...
Please wait, while we are loading the content...
Similar Documents
Rank deficiency in sparse random GF [ 2 ] matrices
| Content Provider | Semantic Scholar |
|---|---|
| Author | Darling, R. W. R. Penrose, Mathew D. Wade, Andrew R. Zabell, Sandy L. |
| Copyright Year | 2014 |
| 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} 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−1 logE[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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://purehost.bath.ac.uk/ws/portalfiles/portal/137231368/Rank_deficiency_in_sparse_random.pdf |
| Alternate Webpage(s) | http://www.univie.ac.at/EMIS/journals/EJP-ECP/article/download/2458/2458-18661-1-PB.pdf |
| Alternate Webpage(s) | http://emis.icm.edu.pl/journals/EJP-ECP/article/download/2458/2458-18661-1-PB.pdf |
| Alternate Webpage(s) | http://www.maths.soton.ac.uk/EMIS/journals/EJP-ECP/article/download/2458/2458-18661-1-PB.pdf |
| Alternate Webpage(s) | http://www.emis.de/journals/EJP-ECP/article/download/2458/2458-18661-1-PB.pdf |
| Alternate Webpage(s) | http://emis.mi.ras.ru/journals/EJP-ECP/article/download/2458/2458-18661-1-PB.pdf |
| Alternate Webpage(s) | http://www.maths.tcd.ie/EMIS/journals/EJP-ECP/article/download/2458/2458-18661-1-PB.pdf |
| Alternate Webpage(s) | http://emis.maths.tcd.ie/EMIS/journals/EJP-ECP/article/download/2458/2458-18661-1-PB.pdf |
| Alternate Webpage(s) | http://siba-sinmemis.unile.it/journals/EJP-ECP/article/download/2458/2458-18661-1-PB.pdf |
| Alternate Webpage(s) | http://dro.dur.ac.uk/13559/1/13559.pdf?DDD21+lvbn47+d700tmt |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Algorithm Angular defect Arabic numeral 0 Column (database) Gram-Force Grammatical Framework Iterative method Null Value Randomness Sparse matrix |
| Content Type | Text |
| Resource Type | Article |
