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?

  • $\begingroup$ 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). $\endgroup$ – Anthony Quas Apr 1 '20 at 13:54
  • $\begingroup$ Actually, I didn't know this. Do you have a reference? $\endgroup$ – BLBA Apr 1 '20 at 13:56
  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Apr 1 '20 at 13:59
  • $\begingroup$ Yes but how to compute this probability? $\endgroup$ – BLBA Apr 1 '20 at 14:20
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Anthony Quas Apr 1 '20 at 16:14

Your Answer

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

Browse other questions tagged or ask your own question.