Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What can be said about the null space of random $(0,1)$ rectangular binary matrices? In particular, I am interested in the probability that there is any non-zero vector with only integer coordinates in the null space. Is this a known problem and/or is there a known approach for tackling it?

share|cite|improve this question

closed as off-topic by Will Jagy, Boris Bukh, Daniel Moskovich, Ricardo Andrade, Stefan Kohl Dec 26 '13 at 11:26

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Will Jagy, Boris Bukh, Daniel Moskovich, Ricardo Andrade, Stefan Kohl
If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer 1

up vote 1 down vote accepted

I would comment this but I don't yet have enough reputation. Your question is equivalent to asking the odds that the rank of a $(0,1)$ matrix is full. If your matrix has more columns than rows then you are certain to have non zero vectors in the null space. If you have more rows than columns then you can zero out some rows and reduce to the square case.

For the square matrix case there is an excellent answer here in which they answer both for the case where you are asking over $\mathbb{F}_2$ and over $\mathbb{Q}$.

Pulling from that answer, the rank of the matrix is the dimension of the column space and the number of columns minus the rank is the dimension of the null space. So in the case of $\mathbb{Q}$ the rank tends towards full which means your probability tends to 0. In the case of $\mathbb{F}_2$ the odds of non-trivial null space tends to one, specifically the odds that an $n \times n$ $(0,1)$ matrix has full rank is $ \Pi_{1 \leq k \leq n} (1 - 2^{-k})$ (thus your probability is $1 - \Pi_{1 \leq k \leq n} (1 - 2^{-k})$).

share|cite|improve this answer
I am not sure it is the same. I am asking if there is a non-zero vector with only integer coordinates in the null space. In my case all operations are over $\mathbb{Z}$ and I don't see the mapping to your examples. – user117230 Dec 25 '13 at 19:31
If you have a rational vector in your null space you can just multiply by the lcm of the denominators and have an integer vector in the null space. A scalar times a null space vector is still in the null space. – Andy Novocin Dec 25 '13 at 19:32
That's very interesting, thank you. Just for my interest, which non-zero integer vector is in the null space of $ M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 1\ \end{pmatrix}.$ ? – user117230 Dec 25 '13 at 19:46
Lattices are more restrictive than vector spaces (less scalars to work with), further $\mathbb{Q}^n$ contains $\mathbb{Z}^n$, so if there is no answer in $\mathbb{Q}^n$ then there is no answer in $\mathbb{Z}^n$. If there is an answer in $\mathbb{Q}^n$ then there is an answer in $\mathbb{Z}^n$. – Andy Novocin Dec 25 '13 at 19:51
I see what is going on now. (The answer to my question is (4,2,-2,-2)). Thank you. – user117230 Dec 25 '13 at 19:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.