Probability of full rank of a random matrix. Suppose, $G$ is a $k \times n$ binary matrix with $\operatorname{rank}(G) = k$. The first $k$ columns of $G$ are linearly independent and the next $n-k$ columns are linear combinations of the first $k$ columns.
$G$ matrix can be a generator matrix of a linear code where the fist $k$ columns are the $k \times k$ identity matrix and the next $n-k$ column contain the parity bits and these columns are linear combinations if the first $k$ columns.
I am choosing $u$ number of columns randomly from $G$ to form the matrix $G_u$, where $u<=k$.
I want to find the probability that $\operatorname{rank}(G_u) = u$ for any random sub-matrix.
Really appreciate any suggestions to solve this problem.
Thanks in advance.
 A: As an example showing, why the answer depends on $P$, consider the matrices ($n=4$, $k=u=2$)
$$
G_1=\pmatrix{1&0&1&1\cr0&1&0&0\cr},\quad G_2=\pmatrix{1&0&1&0\cr0&1&0&1},\quad G_3=\pmatrix{1&0&1&1\cr0&1&0&1}.
$$
Two columns of $G_1$ will be linearly independent, iff the second column is among them. There the probability of a full rank submatrix is $3/6=1/2$. OTOH two columns of $G_2$ will be linearly independent unless you happened to pick 1st and 3rd or 2nd and 4th, so the probability of full rank is $4/6=2/3$. As the last case, two columns of $G_3$ will be linearly independent iff they are distinct, so the only pair violating that condition is 1st and 3rd. Therefore the probability of full rank has gone up to $5/6$.
It is easy to prove that with this set of parameters: $N=4, k=u=2$ it is impossible that the probability of a full rank submatrix would be equal to $1.$ Probability of full rank can be $1$ only, if the minimum Hamming distance of the dual code is $>u$ (and this is not possible for many choices of $n,k,u$). The way to see this is to view $G$ as a parity check matrix. If some $u$ columns are linearly dependent, then some subset of those columns sums to zero. Putting 1s in the positions of that subset we get a non-zero word of the dual code that has weight $\le u$. If the minimum Hamming distance of the dual code is $>u$, such sets do not exist, and the probability of full rank is equal to $1$.
So it all comes down to finding the minimum Hamming distance of the dual code.
