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:

http://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code.

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

nonon-zero rows or columns"? – François G. Dorais♦ Aug 28 '11 at 14:03