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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.