RANDOM BOOLEAN MATRIX BLOCK STRUCTURE

E. R. Domilovsky, V. N. Piskunov
VANT. Ser. Metodiki i Programmy Chislennogo Resheniya Zadach Matematicheskoy Fiziki 1985. Вып.1. С. 49-52.

      We analyze a block structure of a random mxn matrix, A, with r nonzero elements in the asymptotic limit, m, n → ∞, r(mn)^-1/2→τ. For τ = 1, a block is shown to occur having a dimension similar to that of the whole A matrix. We discuss the suitability of results obtained to study the block structure of incidence matrices in mathematical programming problems.