2
$\begingroup$

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.

  • 0
    I don't think there's enough information to give an answer. For example, if the last $n-k$ columns are all zeros then the probability is very small; for a different matrix of the same size, the probability could be 1.2012-04-03
  • 0
    I am actually talking about a generator matrix of a linear channel code in which the first k columns are the identity matrix and the next n-k columns contain the parity bits. G = [ I | P ]. I have updated my question as well. Thanks for your comment.2012-04-03
  • 1
    I don't know what restrictions there are on $P$, but I suspect it's still the case that even if you fix $k,n,u$ the answer will depend on $P$. Take the case where $n-k=1$; the answer will (for some values of $u$) depend on how many ones there are in $P$.2012-04-03
  • 0
    Let's say P does not contain any all zero column vectors. Each column of P will be a linear combination of any of the k columns. I do not understand how the answer will depend on the number of ones in P. Thanks again...2012-04-03

1 Answers 1