Singularity of sparse random matrices

Question

The following topic came up in conversation with my office-mate Lionel: Let $p$ be a fixed prime, $c$ a fixed positive real parameter and $n$ a large number. Consider a random $(0,1)$ matrix with entries in $Z/p$, where the probability of a $0$ is $1-\frac{c}{n}$ and that of a $1$ is $\frac{c}{n}$. As $n\rightarrow \infty$, what is the probability that this matrix is singular? UPDATE: As moonface points out, this probability is $1$. Furthermore, his argument points out that we should expect the corank to be something like $a*n$. So I'll ask more generally what we can say about the behavior of the rank as $n\rightarrow\infty$.

Actually, in our motivating example, the matrix is symmetric and the distribution on the diagonal is different than in the rest of the matrix. I left these details out, but please mention it if this point would strongly effect your answer.

Answer 1

A few observations:

-As n tends to infinity, the function corank/n is highly concentrated for each n -- for example, we can think of exposing the matrix minor by minor (looking at the upper left kxk matrix for k increasing towards n). Since changing what happens at each level of exposure can only affect the rank of the matrix by at most 2, it follows from Azuma's inequality that the rank is concentrated in an interval of width about Sqrt(n).

-A recent preprint of Bordenave and Lelarge (The rank of diluted random graphs) may be of relevance here.

There they consider a model which includes the adjacency matrices of Erdos-Renyi graphs with edge probability c/n and show that the ratio rank/n converges to an explicit function (which also turns out to be the size of the maximum matching in the graph).

The differences between their work and your model are

(1) They consider matrices over the reals instead of over a finite field.

and

(2) They make assumptions about the random graphs converging locally to a tree. Their results definitely apply if the diagonal entries are 0, and from interlacing their results should also hold if your distribution doesn't let too many of the diagonal entries become non-zero.

However, I would expect a drastically different corank if a positive proportion of the diagonal entries are non-zero. The main contribution to the corank in these graphs come from non-expanding sets of rows (sets of k rows which have nonzero entries in fewer than k columns). By adjusting the diagonal entries, I can remove THAT source of dependency, though at the same time I'll possibly be creating others. (EDIT: For example, if I set all of the diagonal entries equal to 1, I've created a new constant*n sources of dependency corresponding to the isolated edges in the graph.

Going back to assumption (1), my guess is that it would make only a small difference in the rank of the matrix. My intuition for this is twofold.

(1) If we consider non-symmetric dense matrices instead of sparse ones (e.g. by requiring the probability any entry takes on any one value to be bounded away from 1), then the probability the matrix has rank n-k is exponentially small in k

(2) If c is sufficiently small, then (as observed by Bauer and Golinelli) we can get a good estimate on the rank of the random matrix by repeatedly following the following procedure: Locate a vertex with exactly one neighbor in the graph (a row and column with exactly one non-zero entry), and remove both that vertex and its neighbor from the graph. Doing so will reduce the rank of the matrix by exactly 2 regardless of the field we are working over. For c less than e, we can keep on following this procedure until o(n) non-isolated vertices remain, implying that the field we are working over will only affect the rank of the matrix by o(n). For c greater than e, I see no reason to expect any different behavior.

Note that the argument in (2) here is, again, heavily dependent on the distribution of the diagonal entries and breaks down if the entries are nonzero. Still, I wouldn't expect it to matter too much.

Answer 2

A few words of caution about random matrices over finite fields: it takes very little deviation from the zero distribution to force the spectral properties of a random matrix to look like one chosen with a uniform distribution.

For example, take the field to be Z/pZ and consider the distribution where each entry is 0 with probability 1 - (log n)^2/n and 1 with probability (log n)^2/n. The probability that the random matrix is non-singular then converges to (1 - 1/p)(1 - 1/p^2)(1 - 1/p^3)...(1-1/p^n), which is the same probability as a uniformly chosen matrix from M(n,Z/pZ) being non-singular. In other words, the singularity probability will converge to a constant about 1/p, not to zero or to one, and the probability that the matrix has corank k is about 1/p^k. This phenomena will hold as long as the distribution you choose is not concentrated more than about 1 - log n/n; otherwise, we do indeed expect the matrix to be almost surely singular as n -> infty, as is the case for the random matrix in the original post.

The key point seems to be bounding the probability that a row is all zeros or that the matrix has multiple equal rows. If you can show that the probability of such an event goes to zero as n -> infty, then I would expect the asymptotics I mentioned above to take over.

Answer 3

A couple of minutes of numerics tentatively suggests that there exists f=f(c) so that the corank/n approaches f(c) with probability 1. Curiously, in the very few examples I tried, f(c) seemed not to depend on p and the answer may be the same replacing Z/pZ with Z. (This makes intuitive sense: If you take an integral matrix, its rank mod p might be lower, but it is very unlikely to be much lower.)

I think one can easily give lower and upper bounds which are linear in n (again, with high probability), but I don't see how to get them to converge. I'm interested to know the source of this nice question.