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
    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

2

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.

  • 0
    @anne, it is known that the problem of deciding, whether a given code has a non-zero word of Hamming weight below a prescribed bound is NP-hard. That pretty much kills all hope of deciding, whether your probability is exactly one or something less than that. If you would be satisfied with a rough estimate, then that it is easier. The weight distribution of a random linear code follows the binomial distribution very closely. That might enable you to give a ballpark figure. But taking everything into account is still quite a task.2012-04-04