Rank of random binary matrix subset

I have a problem that smells like it is NP-complete, but at the same time it feels like maybe you can solve it by just keeping track of column-wise Hamming distance or something, or that it's equivalent to some spanning tree-like problem. The problem is as follows.

We have some binary matrix $M \in \mathbb{F}_2^{n\times k}$ with rank $n$. Let $S_i$ be the matrix constructed by sampling the rows of M $i$ times without replacement. I would like to find

• the expected rank of $S_i$

• a vector $x \in \mathbb{F}_2^k$ such that appending $x$ to $M$ prior

to sampling will maximize the expected rank of $S_i$.

Any ideas on sources that cover similar problems would also be appreciated.

The Whitney rank polynomial, an analog of the well-known Tutte polynomial of graphs, enumerates the number of subsets of a matroid of given size and rank. It can be computed using a deletion-contraction recurrence essentially the same as the recurrence for the Tutte polynomial. You can find the details in Welsh's Matroid Theory, §15.4. From the rank polynomial it is easy to read off the expected rank of $S_i$.

Granted, this algorithm takes exponential time, which is not necessarily better than direct counting. Computing the coefficients of the rank polynomial is #P-hard, which suggests that computing the expectation might be hard as well. You can estimate it to your heart's content by sampling, though.

StackExchange Computer Science Q#53540, answer score: 3