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.



Singularity of sparse random matrices
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](http://arxiv.org/abs/0907.4244)) 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](http://arxiv.org/abs/cond-mat/0102011)) 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. 


