# Random sparse and invertible matrices

Let $$n\leq m$$ and $$0\leq k\leq (n\times m - \min\{n,m\})$$ be in $$\mathbb{N}$$. Let $$\mu$$ be a probability measure dominated by the Lebesgue measure on $$\mathbb{R}$$ and generate a random $$n\times m$$ matrix $$A$$ as follows: $$A_{i,j} \sim \mu$$ and set exactly $$k$$ elements of $$A$$ equal to $$0$$ where the indices of the zero entries are chosen uniformly at random.

What is the probability that $$A$$ has full rank?

For example, if $$n=m$$, $$k=0$$ and $$\mu$$ is Gaussian then $$det(A)\neq 0$$ with probability $$1$$. So $$A$$ has full rank... but what about in general?

• From the bounds you have in the question, maybe you know this already? It’s just the probability that the pattern of non-zero entries contains a subset of the form $(1,j_1),\ldots,(n,j_n)$ with distinct j’s. For any fixed pattern satisfying this, the probability that the matrix obtained by filling the entries is full rank is 1 (just take a sub-determinant). – Anthony Quas Apr 1 at 13:54
• Actually, I didn't know this. Do you have a reference? – AnnieLeKatsu Apr 1 at 13:56
• I indicated the proof. Consider the subdeterminant. Condition on all the entries except for the n entries I identified. Then with probability 1, the product of the n entries is not the exact number needed to make the subdeterminant vanish. – Anthony Quas Apr 1 at 13:59
• Yes but how to compute this probability? – AnnieLeKatsu Apr 1 at 14:20
• I know how to compute it for small values of $k$ and for large values of $k$, but the point of my previous comment is that it reduces to a counting problem: out of the $\binom{mn}{k}$ arrangements, how many "contain" an "injection"? In particular for $k<m$, the probability is 1. If $k=mn-m$, then probability is $m(m-1)\ldots (m-n+1)/\binom{mn}{n}$. – Anthony Quas Apr 1 at 16:14