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

• For your first question, you might check the more general question about matroids (your case is a binary matroid). – Yuval Filmus Feb 23 '16 at 22:05
• @YuvalFilmus I will investigate it further, but I wouldn't not have guessed that formulating it as a matroid would simplify the problem... – Benjamin Lindqvist Feb 24 '16 at 6:43
• The question involves the matroid structure of your matrix. I answer your first question below. The rule here is one question per post, so I suggest you move the second question to a new post (after attempting first to solve it yourself). – Yuval Filmus Feb 24 '16 at 22:09

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