12
$\begingroup$

Sample $n^2$ integers $a_{11},\dots,a_{nn}$ in $\{-d,\dots,-1,0,1\dots,d\}$ uniformly.

What is the probability that the resulting matrix $[a_{ij}]$ has rank $r$?

Is there a nice parametrization of such matrices that helps us generate such a rank $r$ matrix quickly deterministically?

In general what is a good strategy?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ I'm assuming this is for $d\neq 0$. $\endgroup$
    – Set
    Commented Dec 11, 2015 at 8:59
  • $\begingroup$ The parametrization is the Grassmanian $\endgroup$
    – Set
    Commented Dec 11, 2015 at 9:04
  • $\begingroup$ @BloodPudding that is true but that does not help getting away to sample deterministically. $\endgroup$
    – Turbo
    Commented Dec 11, 2015 at 9:06
  • $\begingroup$ @BloodPudding that should help in probability calculation though right? $\endgroup$
    – Turbo
    Commented Dec 11, 2015 at 9:07
  • 1
    $\begingroup$ @kodlu I think it is pretty clear what is being asked. Q1: given $n^2$ integer of absolute value smaller than $d$, what are the odds that the matrix they generate has rank $r$? And Q2, what is an efficient algorithm for uniformly sampling from the set of $n \times n$ matrices with entries < $d$ and rank $r$? Deterministic only means that the algorithm should not be probabilistic in the sense of giving the right answer only with probability $> 1 - \epsilon$ for a priori choice of $\epsilon$. $\endgroup$
    – Vidit Nanda
    Commented Dec 12, 2015 at 19:34

1 Answer 1

Reset to default
4
$\begingroup$

The case $r=n$ is considered in this paper by Martin and Wong. They prove that for every $n \geq 2$ and every $\epsilon >0$, the probability that a random $n \times n$ matrix with entries from $\{-k, \dots, 0, \dots, k\}$ is singular is $\ll \frac{1}{k^{2-\epsilon}}$. See Lemma $1$. The discussion following Lemma $1$ shows that this is tight for $n=2$, but not for $n >2$. By a deep theorem of Katznelson, the true probability decays as $\frac{\log (k)}{k^n}$, which is not far from $\frac{1}{k^n}$ (the probability that a random matrix contains a row of zeros).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Singular means rank < n, not rank = 0. What definition of rank are you using which even allows rank = 0? $\endgroup$
    – Mark L. Stone
    Commented Dec 13, 2015 at 0:24
  • $\begingroup$ nice. but you're allowing 0 as an entry which the OP didn't want. $\endgroup$
    – kodlu
    Commented Dec 13, 2015 at 0:47
  • $\begingroup$ In the latest edit the OP does allow zero as an entry. $\endgroup$
    – Tony Huynh
    Commented Dec 13, 2015 at 15:29
  • $\begingroup$ I have always allowed 0 (notations were quite messy) $\endgroup$
    – Turbo
    Commented Dec 13, 2015 at 17:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .