Random block-angular matrices for distributed data storage
Paulo J. S. G. Ferreira, Bruno Jesus, Jose M. N. Vieira, Armando J. Pinho · 2011
Random binary matrices have found many applications in signal processing and coding. Rateless codes, for example, are based on the random generation of code words by means of inner products between the data and random binary vectors. But the usefulness of random binary matrices is not limited to coding: they are also well suited to distributed data storage applications. In this context, random binary matrices with block-angular structure are of particular interest because they allow co operative encoding and decentralized models for coding and decoding, with a built-in degree of parallelism. Lin ear programming, LU factorization and QR factorization are some of the problems for which the coarse-grain parallelization inherent in the block-angular structure is of interest. This paper studies one of the most important characteristics of block-angular matrices, their rank. More precisely, we study the rank distribution and full rank probability of rectangular random binary matrices and block-angular matrices in GF(2).