Let $M$ be an $m \times n$ tall ($m > n$) matrix over $\mbox{GF}(2)$. Let $M^{'}$ be an $r \times n$ submatrix of $M$ (where $r \leq m$) whose rows are randomly selected from $M$. Is it possible that the $M^{'}$ is full row-rank?
If it is, why?
If it is not, how about the case where $r < m$?
I have run some experiments on Matlab. In experiments, I first randomly generated $10^{6}$ matrices over $\mbox{GF}(2)$. Each matrix has $m = 288$ rows and $n = 216$ columns. Turn out they all have the rank of $216$. Then, I randomly generated $10^{6}$ matrices over GF(2). Each matrix has $m = 84$ rows and $n = 216$ columns. Turn out they all have the rank of $84$. So I am very confused now.
Best Answer
Note that a matrix can only have full row-rank if the number of rows it has is greater than or equal to the number of columns. So, $M'$ can only have full row-rank if $r \leq n$.
That being said: because $M$ has full column-rank (according to your title), there is necessarily at least one $n \times n$ submatrix of $M$ that is invertible (full row and column rank), and every submatrix taken by choosing rows from the invertible submatrix will have full row rank.
As I note here, if both matrices are randomly selected, then the probability that either fails to have full row-rank is smaller than $10^{-20}$, which in practice means that both matrices will "almost always" have full rank.