Spectral Distribution of Random Matrices From Binary Linear Block Codes

Let C be a binary linear block code of length n, dimension k and minimum Hamming distance d over GF(2)(n). Let d(perpendicular to) denote the minimum Hamming distance of the dual code of C over GF(2)(n). Let epsilon : GF(2)(n) bar right arrow {-1, 1}(n) be the component-wise mapping epsilon(v(i)):=(-1)(vi), for v = (v(1), v(2), ..., v(n)) is an element of GF(2)(n). Finally, for p < n, let Phi(C) be a p x n random matrix whose rows are obtained by mapping a uniformly drawn set of size p of the codewords of C under epsilon. It is shown that for d(perpendicular to) large enough and y:=p/n is an element of (0, 1) fixed, as n -> infinity the empirical spectral distribution of the Gram matrix of 1/root n Phi(C) resembles that of a random i.i.d. Rademacher matrix (i.e., the Marchenko-Pastur distribution). Moreover, an explicit asymptotic uniform bound on the distance of the empirical spectral distribution of the Gram matrix of 1/root n Phi(C) to the Marchenko-Pastur distribution as a function of y and d(perpendicular to) is presented.