# On rank of random $0/1$ matrices

It is known that a $0/1$ matrix picked from uniform distribution from $\{0,1\}^{n\times n}$ is non-singular with probability $1-o(1)$.

Fix an integer $t$.

Consider a random matrix formed the following way.

Take an all $1$ vector and represent it as a random sum of $t$ $0/1$ vectors $v_1,\dots,v_t$. That is $v_i\in\{0,1\}^{n}$ and $\sum_iv_i$ is all $1$ vector.

Stack them and form a matrix of size $t\times n$. Repeat the random procedure $\frac nt$ times (assume $t|n$) and keep stacking the resulting matrices to get a $0/1$ matrix of size $n\times n$.

Is this matrix non-singular with probability $1-o(1)$? If so how does the distribution depend on $n$ and $t$?

This is negative.

Consider two constructions:

$(1)$ After stacking take a random $\{-1,+1\}^{t}$ vector and left multiply the vector with the stack to get a $\{-1,+1\}^n$ vector. Now repeat the procedure $n$ times to get $n$ $\{-1,+1\}^n$ vectors and apply map $-1\rightarrow+1$ and $+1\rightarrow0$ and stack them to get a $\{0,1\}^{n\times n}$ matrix.

$(2)$ Say we have $(\frac nt)^\alpha$ stacks of height $t$ each for some $\alpha>1$. Choose random $n$ rows from them and form a $\{0,1\}^{n\times n}$ matrix.

In each of the two cases is the resulting matrix non-singular with probability $1-o(1)$? If so how does the distribution depend on $n$ and $t$?

• @RobertIsrael because each column has only one $1$. – user94040 Dec 16 '16 at 18:36

As soon as you have two stacks, each summing to the same all-1 vector, your matrix is going to be singular. So, unless I misunderstand you, the probability is $0$.

• oops ok..... thank you . let me modify a bit which is also sufficient for me. – user94040 Dec 16 '16 at 2:10
• modified the problem which suffices for me. – user94040 Dec 16 '16 at 2:13