I believe this should be some standard result in random matrices theory, but my initial search failed to find a definitive answer. 


The question is given a random sparse matrix $M\in\mathbb{R}^{n\times m}$ (in general $m\geq n$ having as any of its entries either 0 with probability $1/2$ and a positive number with probability $1/2$, what is the expected rank ? Precisely speaking, I have in mind a matrix construction procedure, where all of the entries in the matrix are independently drafted from a zero mean Gaussian, having the negatives truncated to $0$.


Also is the rank of this type of matrix equivalent to the corresponding binary matrix (all of the nonzero entries replaced with $1$) ?


My intuition is that those type of matrices are full-rank with very high probability, especially in the case $m\gg n$ and large $n$ that is also confirmed by my numerical experiments.


Best, Jacek



Rank of a random sparse matrix with nonnegative reals
For $m$ large and $n < m$, such a matrix will have full rank with probability approximately $1 - n/2^m$. If $n = m$, then it will have full rank with probability approximately $1 - 2m/2^m$.


It turns out that your question is equivalent to the following:



> 
> What is the expected size of the maximum matching in a random bipartite graph on vertex sets $U$ and $V$ with $|U| = n$ and $|V| = m$ where each edge is present independently with probability $1/2$?
> 
> 
> 


Here is a proof of the equivalence of these questions.



> 
> Imagine creating your random matrix in two steps. First, we decide which entries will be 0, leaving the other entries as variables. Call this matrix $M^\prime$. Then we create $M$ by assigning a random positive value to each variable in $M^\prime$.
> 
> 
> Given $M^\prime$, we can define $G$ to be the bipartite graph on vertices $u\_1, \ldots, u\_n$ and $v\_1, \ldots, v\_m$, where there is an edge between $u\_i$ and $v\_j$ if and only if the $(i,j)$-entry of $M^\prime$ is nonzero. Note that a matching of size $k$ in $G$ corresponds to a set of $k$ nonzero entries in $M^\prime$, all in different rows and columns.
> 
> 
> I claim that the size of the maximum matching in $G$ is equal to the rank of $M$ with probability 1.
> 
> 
> We'll show that if the rank of $M$ is $k$, then there exists a matching of size $k$ or greater in $G$, and conversely, if there is a matching of size $k$ in $G$, then the rank of $M$ is at least $k$ (with probability 1). In both parts of the proof, we'll use the fact that the rank of a matrix is equal to the largest $k$ such that there exists a $k \times k$ submatrix with nonzero determinant.
> 
> 
> First, suppose the rank of $M$ is $k$. Then there is a $k \times k$ submatrix with nonzero determinant. So there must be some transversal of that submatrix which avoids zeros. This transversal corresponds to a matching of size $k$ in $G$.
> 
> 
> Now suppose there is a matching of size $k$ in $G$. Consider the $k \times k$ submatrix of $M^\prime$ that those entries define. The determinant of this submatrix is a degree-$k$ polynomial in our variables, and the existence of the matching tells us one particular term that exists in the polynomial, hence the determinant is not identically zero as a polynomial. The determinant of this submatrix in $M$ *could* be zero if the values of the variables happen to make it so, but this is a probability-0 event. So with probability 1, this $k \times k$ submatrix has nonzero determinant, so the rank of $M$ is at least $k$.
> 
> 
> So the rank of $M$ is almost surely equal to the size of the maximum matching in $G$.
> 
> 
> 


According to Hall's Marriage Theorem, $G$ will have a matching of size $n$ if and only if for each subset $W \subset U$, $|N(W)| \geq |W|$ (where $N(W)$ denotes the set of neighbors of $W$). Or put another way, there fails to be a matching of size $n$ if and only if there exists a subset $W \subset U$ with $|N(W)| < |W|$. Letting $X = V - N(W)$, this is equivalent to the existence of sets $W \subset U$ and $X \subset V$ such that $|W|+|X| > m$, and there are no edges between $W$ and $X$.


In the context of the matrix, $M$ will (with probability 1) have full rank unless there exists a submatrix of zeros of size $a \times b$, with $a+b > m$.


I'm not sure if there's a closed form for the probability of this, but for $m$ large and $n < m$, by far the most likely way for this to happen is for a single row ($1 \times m$ submatrix) to be all 0. The probability of this is about $n/2^m$ (I'm ignoring terms on the order of $2^{-2m}$). If $n = m$, then an all-0 column ($m \times 1$ submatrix) is another equally likely case we need to consider, leading to a probability of about $2m/2^m$. Of course, if $m$ is not large, these estimates will be off, but in such a case, one could presumably compute the probability of such an all-zero submatrix exactly.


