<p>How to efficiently generate a random $n\!\times\!n$ $0$-$1$ matrix of rank $k&lt;n$?</p>

CC BY-SA 3.0
2016-01-28T00:19:44.600Z
Rank as a matrix over $\mathbb{R}$, or over $\mathbb{F}_2$?
David Eppstein
CC BY-SA 3.0
2016-01-28T03:02:12.800Z
Pick a fixed rank k matrix and multiply it with a random rank n matrix.
Kaveh
CC BY-SA 3.0
2016-01-28T15:29:38.123Z
@DavidEppstein the base field is $\mathbb{F}_2$.
Nado
CC BY-SA 3.0
2016-01-28T15:32:48.277Z
@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
CC BY-SA 3.0
2016-01-28T15:53:03.360Z
@DavidEppstein  Can we state that the distribution of $A\begin{pmatrix}I_k&0\\0&0\end{pmatrix}B$ is uniform over the set of matrices of rank $k$, if $A$ and $B$ are uniformly picked at random from the set of non-singular $n\!\times\!n$ matrices over $\mathbb{F}_2$?
Nado
CC BY-SA 3.0
2016-01-28T16:58:38.357Z
The random matrix is not singular whp over $\mathbb{F}_2$, only with constant probability (see e.g. the answer in http://math.stackexchange.com/questions/54246/probability-that-a-random-binary-matrix-is-invertible), but that's good enough to do rejection sampling.
David Eppstein
<ds.algorithms><graph-theory><linear-algebra><randomized-algorithms><matrices>
How to efficiently generate a random 0-1 matrix of a given rank
Nado
# How to efficiently generate a random 0-1 matrix of a given rank

(Asked by: username_0 on 2016-01-27)

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

**Tags:** ds.algorithms, graph-theory, linear-algebra, randomized-algorithms, matrices
> **Comments:**
> **username_1**: Rank as a matrix over $\mathbb{R}$, or over $\mathbb{F}_2$?  
> **username_2**: Pick a fixed rank k matrix and multiply it with a random rank n matrix.  
> **username_0**: @DavidEppstein the base field is $\mathbb{F}_2$.  
> **username_0**: @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}$  
> **username_0**: @DavidEppstein  Can we state that the distribution of $A\begin{pmatrix}I_k&0\\0&0\end{pmatrix}B$ is uniform over the set of matrices of rank $k$, if $A$ and $B$ are uniformly picked at random from the set of non-singular $n\!\times\!n$ matrices over $\mathbb{F}_2$?  
> **username_1**: The random matrix is not singular whp over $\mathbb{F}_2$, only with constant probability (see e.g. the answer in http://math.stackexchange.com/questions/54246/probability-that-a-random-binary-matrix-is-invertible), but that's good enough to do rejection sampling.  

---

## 0 answers

