1
$\begingroup$

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$?

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

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy