3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For your first question, you might check the more general question about matroids (your case is a binary matroid). $\endgroup$ – Yuval Filmus Feb 23 '16 at 22:05
  • $\begingroup$ @YuvalFilmus I will investigate it further, but I wouldn't not have guessed that formulating it as a matroid would simplify the problem... $\endgroup$ – Benjamin Lindqvist Feb 24 '16 at 6:43
  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus Feb 24 '16 at 22:09
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I would be grateful for an online reference stating the recurrence for the Whitney rank polynomial. $\endgroup$ – Yuval Filmus Feb 24 '16 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.