How to efficiently generate a random $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$?

  • 5
    $\begingroup$ Rank as a matrix over $\mathbb{R}$, or over $\mathbb{F}_2$? $\endgroup$ – David Eppstein Jan 28 '16 at 0:19
  • 2
    $\begingroup$ Pick a fixed rank k matrix and multiply it with a random rank n matrix. $\endgroup$ – Kaveh Jan 28 '16 at 3:02
  • $\begingroup$ @DavidEppstein the base field is $\mathbb{F}_2$. $\endgroup$ – Nado Jan 28 '16 at 15:29
  • $\begingroup$ @Kaveh A random $n\!\times\!n$ $M$ matrix of elements in $\mathbb{F}_2$ is non-singular with high probability, so I guess multiplying $M$ by $\begin{pmatrix} I_k & 0\\0&0\end{pmatrix}$ $\endgroup$ – Nado Jan 28 '16 at 15:32
  • 4
    $\begingroup$ The random matrix is not singular whp over $\mathbb{F}_2$, only with constant probability (see e.g. the answer in math.stackexchange.com/questions/54246/…), but that's good enough to do rejection sampling. $\endgroup$ – David Eppstein Jan 28 '16 at 16:58

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.