2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ math.stackexchange.com/a/324260/822 $\endgroup$ – Nate Eldredge May 3 at 23:23
  • 1
    $\begingroup$ When you say the nonzero entries are all "a positive number", do you mean that they are all the same positive number (in which case it might as well be 1), or that they are sampled from some distribution on the positive real numbers (what distribution? are they independent?) $\endgroup$ – Nate Eldredge May 3 at 23:25
  • $\begingroup$ @NateEldredge thanks for pointing out, I updated the question, and explained the procedure I have in mind precisely $\endgroup$ – jaco May 4 at 16:59
  • 1
    $\begingroup$ @NateEldredge Before the clarification I thought that they were fixed but possibly different positive numbers, and I still do not know the proof in that case. Do you? $\endgroup$ – fedja May 8 at 12:14
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I just ran across your post. Note that for $n=m$ the exponential tail of the probability that the matrix is singular was only recently settled, see Theorem A in Tikhomirov's paper arxiv.org/pdf/1812.09016.pdf (in the case here, $s=0$). Your solution seems to give this effortlessly... The issue is in the claim ``M will (with probability 1) have full rank unless there exists a submatrix of zeros of size a×b, with a+b>m.''. This is of course false, as the matrix of all ones shows. On the other hand, Tikhomirov's result settles the case $m=n$, which settles the general case as well. $\endgroup$ – ofer zeitouni May 20 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.