MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.

The problem is to partition the columns of $A$ into at most $m$ subsets each of size at most $b$ such that the number of "critical subset's" is minimized, where a critical subset is a subset of the set of columns such that if we remove it from $A$ the reduced matrix has rank less than $n.$

The problem seems to be NP-Complete to me but I am not able to understand from which problem we should try to reduce.

The elaborate problem definition/relevant discussion can be found at:

I am defining it here in some abstract way. Also, I wanted to post it under the NP-Complete tag.

share|cite|improve this question
Are you sure you want B to have "no non-zero rows or columns"? – François G. Dorais Aug 28 '11 at 14:03
This question was also posted here:… – Martin Sleziak Aug 28 '11 at 14:07
Prasenjit: to expand on Martin's remark, it is considered extremely poor form to post identical questions on MO and SE at the same time. The recommended course of action is to post it on SE, and then only repost on MO after about a week, if it looks like the SE question is going nowhere. – Thierry Zell Aug 28 '11 at 14:46
@Martin and Thierry: Sorry for posting it twice. I will keep in mind what you have said next time I post. – aaaaaa Aug 28 '11 at 17:08
@Prasenjit: I assume that Francois interpreted "no non-zero rows or columns" the same way I did, which would mean that B is the zero matrix. (A row or column (or any other sort of vector) is non-zero if at least one entry is non-zero.) I also assume that you meant something else. Please tell us what you meant. – Andreas Blass Aug 28 '11 at 21:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.