Return to Answer

replaced http://math.stackexchange.com/ with https://math.stackexchange.com/

Source Link

edited Apr 13, 2017 at 12:19

1
2
3

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

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

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

Source Link

created Dec 25, 2013 at 19:30

126
2

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