# How to efficiently generate a random 0-1 matrix of a given rank

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

• Rank as a matrix over $\mathbb{R}$, or over $\mathbb{F}_2$? – David Eppstein Jan 28 '16 at 0:19
• Pick a fixed rank k matrix and multiply it with a random rank n matrix. – Kaveh Jan 28 '16 at 3:02
• @DavidEppstein the base field is $\mathbb{F}_2$. – Nado Jan 28 '16 at 15:29
• @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}$ – Nado Jan 28 '16 at 15:32
• 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. – David Eppstein Jan 28 '16 at 16:58