Random binary matrices appear in a variety of signal processing and encoding problems. They play an important role in rateless codes and in distributed storage applications. This paper focuses on block angular matrices, a class of random rectangular binary matrices that are particularly suited to distributed storage applications. We address one of the key issues regarding binary random matrices in general, and block angular matrices in particular: the probability of obtaining a full rank matrix, when drawing uniformly at random from the set of binary matrices with compatible structure. This paper gives a closed-form expression for this probability, as well as some bounds and approximations.

Random binary matrices have found many applications in signal processing and coding. Rateless codes, for example, are based on the random generation of codewords 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 cooperative encoding and decentralized models for coding and decoding, with a built-in degree of parallelism. Linear 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 over the binary field GF(2).

This paper explores a seemingly counter-intuitive idea: the possibility of accelerating the solution of certain linear equations by adding even more equations to the problem. The basic insight is to trade-off problem size by problem structure. We test this idea on Toeplitz equations, in which case the expense of a larger set of equations easily leads to circulant structure. The idea leads to a very simple iterative algorithm, which works for a certain class of Toeplitz matrices, each iteration requiring only two circular convolutions. In the symmetric definite case, numerical experiments show that the method can compete with the preconditioned conjugate gradient method (PCG), which achieves O (n log n) performance. Because the iteration does not converge for all Toeplitz matrices, we give necessary and sufficient conditions to ensure convergence (for not necessarily symmetric matrices), and suggest an efficient convergence test. In the positive definite case we determine the value of the free parameter of the circulant that leads to the fastest convergence, as well as the corresponding value for the spectral radius of the iteration matrix. Although the usefulness of the proposed iteration is limited in the case of ill-conditioned matrices, we believe that the results show that the problem size/problem structure trade-off deserves further study.

This paper introduces and analyzes a new preconditioner for Toeplitz matrices that exhibits excellent spectral properties: the eigenvalues of the preconditioned matrix are highly clustered around the unity. When used with the preconditioned conjugate gradient method this results in very fast convergence. The new preconditioner can be regarded as a refinement of preconditioners built by embedding the Toeplitz matrix in a positive definite circulant. Necessary and sufficient conditions that ensure that the positive definite embedding is possible are given.

This paper explores the relationship between Toeplitz and circulant matrices. Upper and lower bounds for all eigenvalues of Hermitian Toeplitz matrices are given, capitalizing on the possibility of embedding a Toeplitz matrix in a circulant, and of expressing any Toeplitz matrix as a sum of two matrices with known eigenvalues. The bounds can be simultaneously found using a single discrete Fourier transform evaluation. Simulation results indicate that the bounds are sharper than other known bounds.